خلال الأسابيع القليلة الماضية ، كنت أعمل على تطبيق خوارزمية Fortune في لغة C ++. تأخذ هذه الخوارزمية الكثير من النقاط ثنائية الأبعاد وتبني رسمًا تخطيطيًا لها. إذا كنت لا تعرف ما هو مخطط Voronoi ، فألق نظرة على الشكل:


لكل نقطة دخول ، تسمى "موقع" ، نحتاج إلى العثور على العديد من النقاط القريبة من هذا المكان أكثر من أي شخص آخر. تشكل مجموعات النقاط هذه الخلايا الموضحة في الصورة أعلاه.

من الرائع في خوارزمية Fortune أنه بنى مثل هذه الرسوم البيانية في الوقت المناسب $$$O (n \ log n)$(وهو الأمثل لخوارزمية المقارنة) ، أين $$$ن$هو عدد الأماكن.

أكتب هذا المقال لأنني أعتبر تنفيذ هذه الخوارزمية مهمة صعبة للغاية. في الوقت الحالي ، هذه هي أكثر الخوارزميات تعقيدًا التي كان عليّ تنفيذها. لذلك ، أريد مشاركة المشاكل التي واجهتها ، وكيفية حلها.

كالعادة ، يتم نشر الرمز على github ، ويتم سرد جميع المواد المرجعية التي استخدمتها في نهاية المقالة.

وصف خوارزمية الثروة

لن أشرح كيف تعمل الخوارزمية ، لأن الآخرين قد فعلوا ذلك جيدًا بالفعل. يمكنني أن أوصي بدراسة هاتين المادتين: هنا وهنا . والثاني مثير للاهتمام للغاية - كتب المؤلف عرضًا تفاعليًا في جافا سكريبت ، وهو مفيد لفهم تشغيل الخوارزمية. إذا كنت بحاجة إلى نهج أكثر رسمية مع جميع الأدلة ، أوصي بقراءة الفصل 7 من الهندسة الحسابية ، الطبعة الثالثة .

علاوة على ذلك ، أفضل التعامل مع تفاصيل التنفيذ التي لم يتم توثيقها جيدًا. وهم هم الذين يجعلون تنفيذ الخوارزمية معقدًا للغاية. وسأركز بشكل خاص على هياكل البيانات المستخدمة.

لقد كتبت للتو كودًا زائفًا للخوارزمية حتى تحصل على فكرة عن هيكلها العالمي:

  أضف حدث مكان إلى قائمة انتظار الحدث لكل مكان
 حتى تكون قائمة انتظار الحدث فارغة
     استرداد الحدث العلوي
     إذا كان الحدث حدث مكان
         أدخل قوسًا جديدًا في الساحل
         تحقق من أحداث الدائرة الجديدة
     خلاف ذلك
         إنشاء قمة في الرسم التخطيطي
         نزيل من الشريط الساحلي قوسًا محكمًا
         حذف الأحداث غير الصالحة
         تحقق من أحداث الدائرة الجديدة 

هيكل بيانات الرسم البياني

كانت المشكلة الأولى التي واجهتها هي اختيار الطريقة لتخزين الرسم التخطيطي Voronoi.

قررت استخدام بنية بيانات يتم استخدامها على نطاق واسع في الهندسة الحسابية تسمى قائمة الحواف المتصلة بشكل مزدوج (DCEL).

يستخدم صف VoronoiDiagram أربع حاويات كحقول:

 class VoronoiDiagram { public: // ... private: std::vector<Site> mSites; std::vector<Face> mFaces; std::list<Vertex> mVertices; std::list<HalfEdge> mHalfEdges; } 

سأتحدث بالتفصيل عن كل منهم.

تصف فئة Site نقطة الدخول. يحتوي كل مكان على فهرس ، وهو مفيد لوضعه في قائمة الانتظار ، والإحداثيات ، ومؤشرًا للخلية ( face ):

 struct Site { std::size_t index; Vector2 point; Face* face; }; 

يتم تمثيل رؤوس الخلية بفئة Vertex ، ولا تحتوي إلا على حقل إحداثي:

 struct Vertex { Vector2 point; }; 

هنا تنفيذ حواف نصف:

 struct HalfEdge { Vertex* origin; Vertex* destination; HalfEdge* twin; Face* incidentFace; HalfEdge* prev; HalfEdge* next; }; 

قد تتساءل ، ما هو نصف الضلع؟ الحافة في الرسم البياني Voronoi شائعة بين خليتين متجاورتين. في بنية بيانات DCEL ، نقسم هذه الحواف إلى حافتين نصف ، واحدة لكل خلية ، وترتبط بمؤشر twin . علاوة على ذلك ، فإن نصف الحافة لها نقطة بداية ونهاية. يشير حقل eventFace إلى الوجه الذي تنتمي إليه نصف الحافة. يتم تنفيذ الخلايا في DCEL كقائمة نصفية مرتبطة بشكل مزدوج بنصف حواف ، حيث يتم توصيل نصف حواف متجاورة معًا. لذلك ، يشير الحقل السابق والحقل التالي إلى الحواف النصفية السابقة والتالية في الخلية.

يوضح الشكل أدناه جميع هذه الحقول للنصف الأحمر من الحافة:


وأخيرًا ، تحدد فئة Face الخلية. يحتوي ببساطة على مؤشر لمكانه وآخر لآخر من أضلاعه. لا يهم أي من الحواف النصفية محددة لأن الخلية مضلع مغلق. وبالتالي ، يمكننا الوصول إلى جميع الأنصاف أثناء اجتياز قائمة مرتبطة دوريًا.

 struct Face { Site* site; HalfEdge* outerComponent; }; 

قائمة انتظار الأحداث

الطريقة القياسية لتنفيذ قائمة انتظار الأحداث مع قائمة انتظار الأولوية. في عملية معالجة أحداث المكان والدائرة ، قد نحتاج إلى إزالة أحداث الدائرة من قائمة الانتظار لأنها لم تعد صالحة. لكن معظم تطبيقات قائمة انتظار الأولوية القياسية لا تسمح لك بحذف عنصر ليس في القمة. ينطبق هذا بشكل خاص على std::priority_queue .

هناك طريقتان لحل هذه المشكلة. الأول والأبسط هو إضافة علامة valid للأحداث. تم تعيين valid مبدئيًا على true . بعد ذلك ، بدلاً من إزالة حدث الدائرة من قائمة الانتظار ، يمكننا ببساطة تعيين علمه على false . أخيرًا ، عند معالجة جميع الأحداث في الحلقة الرئيسية ، نتحقق لمعرفة ما إذا كانت قيمة العلامة valid للحدث false ، وإذا كان الأمر كذلك ، فما عليك سوى تخطيها ومعالجة المرحلة التالية.

الطريقة الثانية التي طبقتها هي عدم استخدام std::priority_queue . بدلاً من ذلك ، قمت بتطبيق قائمة انتظار الأولوية الخاصة بي ، والتي تدعم إزالة أي عنصر موجود فيه. تنفيذ مثل هذا الطابور بسيط للغاية. لقد اخترت هذه الطريقة لأنها تجعل كود الخوارزمية أكثر نظافة.

الخط الساحلي

تعد بنية بيانات الشاطئ جزءًا معقدًا من الخوارزمية. في حالة التنفيذ غير الصحيح ، لا توجد ضمانات بأن الخوارزمية سيتم تنفيذها في $$$O (n \ log n)$. المفتاح للحصول على هذا التعقيد الزمني هو استخدام شجرة موازنة ذاتية. لكن القول أسهل من الفعل!

يُنصح بمعظم الموارد التي درستها (المادتان المذكورتان أعلاه وكتاب الهندسة الحسابية ) بتنفيذ الخط الساحلي باعتباره شجرة تشير فيها العقد الداخلية إلى نقاط الانقطاع والأوراق تشير إلى الأقواس. لكنهم لا يقولون شيئًا عن كيفية تحقيق التوازن بين الشجرة. أعتقد أن مثل هذا النموذج ليس هو الأفضل ، وإليك السبب:

• هناك معلومات زائدة فيه: نعلم أن هناك نقطة فاصل بين قوسين متجاورين ، لذلك ليس من الضروري تمثيل هذه النقاط كعقد
• وهي غير كافية لتحقيق التوازن الذاتي: فقط الشجرة الفرعية التي تشكلت بواسطة نقاط الاستراحة يمكن موازنتها. لا يمكننا حقًا موازنة الشجرة بأكملها ، وإلا فإن الأقواس يمكن أن تصبح عقدًا داخلية وأوراقًا لنقاط الاستراحة. تبدو كتابة خوارزمية لموازنة الشجرة الفرعية التي تتكون من العقد الداخلية بمثابة كابوس بالنسبة لي.

لذلك ، قررت تقديم الخط الساحلي بشكل مختلف. في تنفيذي ، الخط الساحلي هو أيضًا شجرة ، ولكن جميع العقد أقواس. مثل هذا النموذج لا يحتوي على أي من العيوب المذكورة.

فيما يلي تعريف Arc القوس في التنفيذ الخاص بي:

 struct Arc { enum class Color{RED, BLACK}; // Hierarchy Arc* parent; Arc* left; Arc* right; // Diagram VoronoiDiagram::Site* site; VoronoiDiagram::HalfEdge* leftHalfEdge; VoronoiDiagram::HalfEdge* rightHalfEdge; Event* event; // Optimizations Arc* prev; Arc* next; // Only for balancing Color color; }; 

يتم استخدام الحقول الثلاثة الأولى لتنظيم الشجرة. يشير حقل leftHalfEdge إلى نصف الحافة المرسومة بواسطة أقصى نقطة leftHalfEdge من القوس. و rightHalfEdge على نصف الحافة مرسومة بالنقطة اليمنى المتطرفة. يتم استخدام مؤشرين ، prev next للحصول على وصول مباشر إلى القوس السابق والقادم من خط الساحل. بالإضافة إلى ذلك ، فهي تسمح لك أيضًا بتجاوز الخط الساحلي كقائمة مرتبطة مضاعفة. وأخيرًا ، كل قوس له لون يستخدم لموازنة خط الساحل.

لموازنة الخط الساحلي ، قررت استخدام مخطط أحمر أسود . عند كتابة التعليمات البرمجية ، ألهمني كتاب مقدمة في الخوارزميات . يصف الفصل 13 خوارزميتين insertFixup للاهتمام ، insertFixup و deleteFixup ، التي توازن الشجرة بعد الإدراج أو الحذف.

ومع ذلك ، لا يمكنني استخدام طريقة insert الموضحة في الكتاب ، لأن المفاتيح تُستخدم للعثور على نقطة إدخال العقدة. لا توجد مفاتيح في خوارزمية Fortune ، نحن نعلم فقط أننا بحاجة إلى إدخال قوس قبل أو بعد آخر في الخط الساحلي. لتنفيذ ذلك ، أنشأت insertAfter و insertAfter :

 void Beachline::insertBefore(Arc* x, Arc* y) { // Find the right place if (isNil(x->left)) { x->left = y; y->parent = x; } else { x->prev->right = y; y->parent = x->prev; } // Set the pointers y->prev = x->prev; if (!isNil(y->prev)) y->prev->next = y; y->next = x; x->prev = y; // Balance the tree insertFixup(y); } 

يتم إدراج y قبل x بثلاث خطوات:

1. ابحث عن مكان لإدراج عقدة جديدة. للقيام بذلك ، استخدمت الملاحظة التالية: الطفل الأيسر x أو الطفل الأيمن x->prev هو Nil ، والطفل الذي هو Nil يكون قبل x وبعد x->prev .
2. داخل الخط الساحلي ، نحافظ على بنية قائمة مرتبطة بشكل مزدوج ، لذلك يجب علينا تحديث المؤشرات prev والعناصر next للعناصر x->prev و y و x .
3. أخيرًا ، نسمي ببساطة طريقة insertFixup الموضحة في الكتاب لتحقيق التوازن بين الشجرة.

يتم تنفيذ insertAfter بالمثل.

يمكن تنفيذ طريقة الإزالة المأخوذة من الكتاب بدون تغييرات.

حد الرسم البياني

فيما يلي الإخراج من خوارزمية Fortune الموصوفة أعلاه:


توجد مشكلة صغيرة في بعض حواف الخلايا على حدود الصورة: فهي غير مرسومة لأنها لانهائية.

الأسوأ من ذلك ، قد لا تكون الخلية جزءًا واحدًا. على سبيل المثال ، إذا أخذنا ثلاث نقاط على نفس الخط ، فستكون لنقطة المنتصف حافتان نصف نهائيتان غير متصلتين معًا. هذا لا يناسبنا كثيرًا ، لأننا لن نتمكن من الوصول إلى أحد الحواف النصف ، لأن الخلية هي قائمة حواف مرتبطة.

لحل هذه المشاكل ، سنحدد الرسم التخطيطي. أعني بهذا أننا سنحد من كل خلية في الرسم التخطيطي بحيث لم تعد لها حواف لا نهائية وكل خلية هي مضلع مغلق.

لحسن الحظ ، تسمح لنا خوارزمية Fortune بالعثور بسرعة على حواف لا نهاية لها: فهي تتوافق مع نصف الحواف التي لا تزال في الشريط الساحلي في نهاية الخوارزمية.

تتلقى خوارزمية التقييد مربعًا كمدخلات وتتكون من ثلاث خطوات:

1. يوفر موضع كل قمة للرسم داخل المستطيل.
2. اقطع كل حافة غير محدودة.
3. يغلق الخلايا.

المرحلة 1 تافهة - نحتاج فقط إلى توسيع المستطيل إذا لم يكن يحتوي على قمة.

المرحلة 2 بسيطة للغاية أيضًا - فهي تتكون من حساب التقاطعات بين الأشعة والمستطيل.

المرحلة 3 ليست معقدة أيضًا ، فهي تتطلب الاهتمام فقط. أقوم بها على مرحلتين. أولاً ، أقوم بإضافة نقاط الزاوية للمستطيل إلى الخلايا عند الذروات التي يجب أن تكون. ثم أتأكد من أن جميع رؤوس الخلية متصلة بنصف حواف.

أوصي بدراسة الرمز وطرح الأسئلة إذا كنت بحاجة إلى تفاصيل حول هذا الجزء.

فيما يلي مخطط إخراج خوارزمية الإحاطة:


الآن نرى أن جميع الحواف مرسومة. وإذا قمت بالتصغير ، يمكنك التأكد من إغلاق جميع الخلايا:

تقاطع مع مستطيل

عظيم! لكن الصورة الأولى من بداية المقال أفضل ، أليس كذلك؟

في العديد من التطبيقات ، من المفيد أن يكون هناك تقاطع بين مخطط Voronoi والمستطيل ، كما هو موضح في الصورة الأولى.

الخبر السار هو أنه بعد تقييد الرسم البياني ، هذا أسهل بكثير. الأخبار السيئة هي أنه على الرغم من أن الخوارزمية ليست معقدة للغاية ، إلا أننا بحاجة إلى توخي الحذر.

الفكرة هي: نذهب حول نصف الحافة لكل خلية ونتحقق من التقاطع بين نصف الحافة والمستطيل. هناك خمس حالات ممكنة:

1. نصف الضلع موجود تمامًا داخل المستطيل: نحفظ مثل هذا الضلع النصف
2. نصف الضلع خارج المستطيل تمامًا: نتخلص من نصف الضلع هذا
3. يخرج نصف الضلع خارج المستطيل: نقوم باقتطاع نصف الضلع وحفظه على أنه آخر نصف ضلع يخرج .
4. يدخل نصف الضلع داخل المستطيل: نقوم باقتطاع نصف الضلع لربطه بآخر نصف ضلع خرج (نحفظه في حالة 3 أو 5)
5. يعبر نصف الضلع المستطيل مرتين: نقوم باقتطاع نصف الضلع وإضافة نصف ضلع لربطه بنصف الضلع الأخير الذي خرج ، ثم نحفظه على أنه آخر نصف ضلع آخر خرج .

نعم ، كانت هناك العديد من الحالات. لقد أنشأت صورة لأظهر لهم جميعًا:


المضلع البرتقالي هو الخلية الأصلية ، والأحمر هو الخلية المقطوعة. يتم تمييز نصف الأضلاع المقطوعة باللون الأحمر. تمت إضافة الأضلاع الخضراء لربط نصف الأضلاع التي تدخل المستطيل بنصف الأضلاع الخارجة.

بتطبيق هذه الخوارزمية على رسم بياني محدد ، نحصل على النتيجة المتوقعة:

الخلاصة

تبين أن المقالة طويلة جدًا. وأنا متأكد من أن العديد من الجوانب لا تزال غير واضحة لك. ومع ذلك ، آمل أن يكون مفيدا لك. افحص الرمز للحصول على التفاصيل.

لتلخيص والتأكد من أننا لم نضيع الوقت دون جدوى ، قمت بقياس الوقت على جهاز الكمبيوتر المحمول (الرخيص) الخاص بي لحساب الرسم البياني Voronoi لعدد مختلف من الأماكن:

• $$$n = 1000$: 2 مللي ثانية
• $$ : 33 مللي ثانية
• $$ : 450 مللي ثانية
• $$$n = $ 1،000،00$: 6600 مللي ثانية

ليس لدي شيء للمقارنة بين هذه المؤشرات ، ولكن يبدو أنها سريعة بشكل لا يصدق!

المراجع

• المقالة الأصلية لستيفن فورتشن
• الهندسة الحسابية ، الطبعة الثالثة من تأليف مارك دي بيرج ، أوتفريد تشيونج ، مارك فان كريفيلد ومارك أوفرمارس
• خوارزمية Fortunes: شرح بديهي على jacquesheunis.com
• خوارزمية Fortune وتنفيذها على blog.ivank.net
• مقدمة للخوارزميات ، الطبعة الثالثة من قبل توماس هـ. كورمين ، تشارلز إي ليزرسون ، رونالد ل. ريفيست وكليفورد شتاين