पिछले कुछ हफ्तों से, मैं सी ++ में फॉर्च्यून के एल्गोरिथ्म को लागू करने पर काम कर रहा हूं। यह एल्गोरिथ्म बहुत सारे 2 डी अंक लेता है और उनसे एक वोरोनोई आरेख बनाता है । यदि आप नहीं जानते कि वोरोनोई आरेख क्या है, तो एक नज़र डालें:


प्रत्येक प्रविष्टि बिंदु के लिए, जिसे "साइट" कहा जाता है, हमें कई बिंदुओं को खोजने की आवश्यकता है जो इस स्थान के करीब हैं बाकी सभी की तुलना में। डॉट्स के ऐसे सेट ऊपर की छवि में दिखाई गई कोशिकाओं को बनाते हैं।

फॉर्च्यून के एल्गोरिथ्म में यह उल्लेखनीय है कि वह समय में इस तरह के आरेख बनाता है $$$O (n \ log n)$ (जो एक तुलना एल्गोरिथ्म के लिए इष्टतम है), जहां $$$एन$ स्थानों की संख्या है।

मैं यह लेख इसलिए लिख रहा हूं क्योंकि मैं इस एल्गोरिथ्म के कार्यान्वयन को बहुत कठिन कार्य मानता हूं। फिलहाल, यह एल्गोरिदम का सबसे जटिल है जिसे मुझे लागू करना था। इसलिए, मैं उन समस्याओं को साझा करना चाहता हूं जो मुझे सामना करना पड़ा, और उन्हें कैसे हल करना है।

हमेशा की तरह, कोड को जीथब पर पोस्ट किया गया है, और मेरे द्वारा उपयोग की जाने वाली सभी संदर्भ सामग्री लेख के अंत में सूचीबद्ध हैं।

फॉर्च्यून एल्गोरिथम विवरण

मैं यह नहीं बताऊंगा कि एल्गोरिथ्म कैसे काम करता है, क्योंकि अन्य लोग पहले ही इसे अच्छी तरह से कर चुके हैं। मैं इन दो लेखों का अध्ययन करने की सिफारिश कर सकता हूं: यहां और यहां । दूसरा बहुत दिलचस्प है - लेखक ने जावास्क्रिप्ट में एक इंटरैक्टिव डेमो लिखा, जो एल्गोरिथ्म के संचालन को समझने के लिए उपयोगी है। यदि आपको सभी सबूतों के साथ अधिक औपचारिक दृष्टिकोण की आवश्यकता है, तो मैं कम्प्यूटेशनल ज्यामिति के अध्याय 7 , 3 संस्करण को पढ़ने की सलाह देता हूं।

इसके अलावा, मैं कार्यान्वयन विवरणों से निपटना पसंद करता हूं जो अच्छी तरह से प्रलेखित नहीं हैं। और यह वे हैं जो एल्गोरिथ्म के कार्यान्वयन को इतना जटिल बनाते हैं। विशेष रूप से, मैं उपयोग किए गए डेटा संरचनाओं पर ध्यान केंद्रित करूंगा।

मैंने अभी कलन विधि का छद्म कोड लिखा है ताकि आपको इसकी वैश्विक संरचना का अंदाजा हो:

  प्रत्येक स्थान के लिए ईवेंट कतार में एक स्थान ईवेंट जोड़ें
 जब तक कि घटना कतार खाली न हो जाए
     शीर्ष घटना पुनः प्राप्त करें
     अगर घटना एक जगह घटना है
         समुद्र तट में एक नया चाप डालें
         नए सर्कल ईवेंट की जांच करें
     अन्यथा
         आरेख में एक शीर्ष बनाएँ
         हम समुद्र तट से एक कड़ा हुआ चाप निकालते हैं
         अमान्य घटनाओं को हटाएं
         नए सर्कल ईवेंट की जांच करें 

चार्ट डेटा संरचना

मुझे जो पहली समस्या आई वह थी वोरोनोई आरेख को संग्रहीत करने का तरीका चुनना।

मैंने एक डेटा संरचना का उपयोग करने का निर्णय लिया जो व्यापक रूप से कम्प्यूटेशनल ज्यामिति में उपयोग किया जाता है जिसे दोगुनी कनेक्टेड एज लिस्ट (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 को Vertex वर्ग द्वारा दर्शाया जाता है, उनके पास केवल एक समन्वय क्षेत्र होता है:

 struct Vertex { Vector2 point; }; 

यहाँ आधे किनारों का कार्यान्वयन है:

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

आप आश्चर्यचकित हो सकते हैं कि एक आधा रिब क्या है? वोरोनोई आरेख में एक किनारे दो पड़ोसी कोशिकाओं के लिए आम है। DCEL डेटा संरचना में, हम इन किनारों को दो अर्ध-किनारों में विभाजित करते हैं, प्रत्येक सेल के लिए एक, और वे एक twin सूचक द्वारा जुड़े हुए हैं। इसके अलावा, आधे छोर में एक शुरुआती और समाप्ति बिंदु है। incidentFace क्षेत्र फ़ील्ड उस चेहरे को इंगित करता है जिसके किनारे आधे हैं। DCEL में कोशिकाओं को आधे किनारों की चक्रीय दोगुनी लिंक की गई सूची के रूप में कार्यान्वित किया जाता है, जिसमें आसन्न आधे किनारे एक साथ जुड़े होते हैं। इसलिए, prev और next फ़ील्ड सेल में पिछले और अगले आधे किनारों को इंगित करते हैं।

नीचे दिया गया आंकड़ा इन सभी क्षेत्रों को लाल आधे किनारे के लिए दिखाता है:


अंत में, 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 फील्ड आर्क के सबसे बाएं बिंदु द्वारा खींचे गए आधे किनारे को इंगित करता है। और rightHalfEdge चरम दाहिने बिंदु द्वारा खींचे गए आधे किनारे पर है। दो बिंदुओं, prev और next का उपयोग तटरेखा के पिछले और अगले चाप तक सीधी पहुंच के लिए किया जाता है। इसके अलावा, वे आपको एक दोहरी लिंक की गई सूची के रूप में समुद्र तट को बायपास करने की भी अनुमति देते हैं। अंत में, प्रत्येक चाप में एक रंग होता है जिसका उपयोग तटरेखा को संतुलित करने के लिए किया जाता है।

समुद्र तट को संतुलित करने के लिए, मैंने एक लाल-काली योजना का उपयोग करने का निर्णय लिया। कोड लिखते समय, मैं पुस्तक इंट्रोडक्शन टू अल्गोरिदम से प्रेरित था। अध्याय 13 में दो दिलचस्प एल्गोरिदम, insertFixup और insertFixup वर्णन है, जो प्रविष्टि या विलोपन के बाद पेड़ को संतुलित करता है।

हालाँकि, मैं पुस्तक में दर्शाई गई insert विधि का उपयोग नहीं कर सकता, क्योंकि नोड के सम्मिलन बिंदु को खोजने के लिए कुंजियों का उपयोग किया जाता है। फॉर्च्यून के एल्गोरिथ्म में कोई कुंजी नहीं है, हम केवल यह जानते हैं कि हमें समुद्र तट से पहले या बाद में एक चाप सम्मिलित करने की आवश्यकता है। इसे कार्यान्वित करने के लिए, मैंने insertBefore और 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); } 

x तीन चरणों में करने से पहले y सम्मिलित करना:

1. नया नोड सम्मिलित करने के लिए एक स्थान खोजें। ऐसा करने के लिए, मैंने निम्नलिखित अवलोकन का उपयोग किया: बाएं बच्चा x या दायाँ बच्चा x->prev है Nil , और एक जो Nil है x से पहले और x->prev बाद x->prev ।
2. समुद्र तट के अंदर, हम एक दोहरी लिंक की गई सूची की संरचना को बनाए रखते हैं, इसलिए हमें तदनुसार x->prev , y और x तत्वों के x->prev और next बिंदुओं को अपडेट करना चाहिए।
3. अंत में, हम बस पेड़ को संतुलित करने के लिए पुस्तक में वर्णित insertFixup विधि को कहते हैं।

insertAfter जाता है।

पुस्तक से ली गई निष्कासन विधि को बिना बदलाव के लागू किया जा सकता है।

चार्ट की सीमा

यहाँ फॉर्च्यून के एल्गोरिथ्म से उत्पादन ऊपर वर्णित है:


छवि की सीमा पर कोशिकाओं के कुछ किनारों के साथ एक छोटी सी समस्या है: वे खींची नहीं जाती हैं क्योंकि वे अनंत हैं।

इससे भी बदतर, एक सेल एक टुकड़ा नहीं हो सकता है। उदाहरण के लिए, यदि हम तीन बिंदुओं को लेते हैं जो एक ही रेखा पर हैं, तो मध्य बिंदु में दो अनंत आधे-किनारे होंगे जो एक साथ जुड़े नहीं हैं। यह हमें बहुत सूट नहीं करता है, क्योंकि हम आधे किनारों में से एक का उपयोग नहीं कर पाएंगे, क्योंकि सेल किनारों की एक सूचीबद्ध सूची है।

इन समस्याओं को हल करने के लिए, हम आरेख को सीमित करेंगे। इससे मेरा मतलब है कि हम आरेख के प्रत्येक सेल को सीमित करेंगे ताकि उनके पास अनंत किनारे न हों और प्रत्येक सेल एक बंद बहुभुज हो।

सौभाग्य से, फॉर्च्यून का एल्गोरिथ्म हमें जल्दी से अंतहीन किनारों को खोजने की अनुमति देता है: वे एल्गोरिथ्म के अंत में समुद्र तट में अभी भी आधे किनारों के अनुरूप हैं।

मेरा प्रतिबंध एल्गोरिथ्म इनपुट के रूप में एक बॉक्स प्राप्त करता है और इसमें तीन चरण होते हैं:

1. यह आयत के अंदर आरेख के प्रत्येक शीर्ष को स्थान प्रदान करता है।
2. हर अनंत धार को काट दो।
3. कोशिकाओं को बंद कर देता है।

चरण 1 तुच्छ है - हमें केवल आयत का विस्तार करने की आवश्यकता है यदि इसमें एक शीर्ष नहीं है।

स्टेज 2 भी काफी सरल है - इसमें किरणों और आयत के बीच के चौराहों की गणना शामिल है।

स्टेज 3 भी बहुत जटिल नहीं है, केवल ध्यान देने की आवश्यकता है। मैं इसे दो चरणों में करता हूं। सबसे पहले, मैं आयताकार के कोने बिंदुओं को उन कोशिकाओं पर जोड़ता हूं, जिनके वे होने चाहिए। फिर मैं यह सुनिश्चित करता हूं कि सेल के सभी कोने आधे किनारों से जुड़े हुए हैं।

मेरा सुझाव है कि आप कोड का अध्ययन करें और सवाल पूछें कि क्या आपको इस भाग के बारे में विवरण की आवश्यकता है।

यहाँ आवर्ती एल्गोरिथ्म का आउटपुट आरेख है:


अब हम देखते हैं कि सभी किनारों को खींचा गया है। और यदि आप बाहर ज़ूम करते हैं, तो आप यह सुनिश्चित कर सकते हैं कि सभी सेल बंद हैं:

आयत के साथ अंतरविरोध

बहुत बढ़िया! लेकिन लेख की शुरुआत से पहली छवि बेहतर है, है ना?

कई अनुप्रयोगों में, वोरोनोई आरेख और आयत के बीच के अंतर को जोड़ना उपयोगी है, जैसा कि पहली छवि में दिखाया गया है।

अच्छी खबर यह है कि चार्ट को प्रतिबंधित करने के बाद, यह बहुत आसान है। बुरी खबर यह है कि यद्यपि एल्गोरिथ्म बहुत जटिल नहीं है, हमें सावधान रहने की आवश्यकता है।

विचार यह है: हम प्रत्येक सेल के आधे हिस्से के चारों ओर जाते हैं और आधे किनारे और आयत के बीच के अंतर को देखते हैं। पांच मामले संभव हैं:

1. आधा रिब पूरी तरह से आयत के अंदर होता है: हम ऐसे आधे रिब को बचाते हैं
2. आधा रिब पूरी तरह से आयत के बाहर है: हम इस तरह के एक आधे रिब को त्यागते हैं
3. आधा रिब आयत के बाहर जाता है: हम आधे रिब को काटते हैं और इसे अंतिम आधे रिब के रूप में बचाते हैं जो बाहर जाता है ।
4. आधा-रिब आयत के अंदर जाता है: हम इसे आधा रिब से जोड़ते हैं, इसे अंतिम हाफ-रिब से जोड़ते हैं जो बाहर निकल गया (हम इसे 3 या 5 के मामले में बचाते हैं)
5. आधी पसली दो बार आयत को पार करती है: हम आधी पसली को काटते हैं और इसे पिछली आधी पसली के साथ जोड़ने के लिए एक आधा पसली जोड़ते हैं जो बाहर चली गई थी , और फिर इसे नए अंतिम आधे पसली के रूप में सहेजें।

हां, कई मामले सामने आए हैं। मैंने उन सभी को दिखाने के लिए एक चित्र बनाया:


नारंगी बहुभुज मूल कोशिका है, और लाल छोटी कोशिका है। काटे गए आधे पसलियों को लाल रंग में चिह्नित किया गया है। हरी पसलियों को आधा पसलियों के साथ आयत में प्रवेश करने वाले आधे पसलियों को जोड़ने के लिए जोड़ा गया है।

इस एल्गोरिथ्म को एक बंधे आरेख पर लागू करने पर, हमें अपेक्षित परिणाम मिलता है:

निष्कर्ष

लेख काफी लंबा निकला। और मुझे यकीन है कि कई पहलू अभी भी आपके लिए स्पष्ट नहीं हैं। फिर भी, मुझे आशा है कि यह आपके लिए उपयोगी होगा। विवरण के लिए कोड की जाँच करें।

संक्षेप में और यह सुनिश्चित करने के लिए कि हमने व्यर्थ समय बर्बाद नहीं किया, मैंने अपने (सस्ते) लैपटॉप को अलग-अलग स्थानों के लिए वोरोनोई आरेख की गणना करने का समय मापा:

• $$$n = 1000$ : 2 मि
• $$$n = $ 10,00$ : 33 मि
• $$$n = $ 100,00$ : 450 मि
• $$$n = $ 1,000,00$ : 6600 मि

मेरे पास इन संकेतकों की तुलना करने के लिए कुछ भी नहीं है, लेकिन ऐसा लगता है कि यह अविश्वसनीय रूप से तेज़ है!

संदर्भ सामग्री

• स्टीफन फॉर्च्यून द्वारा मूल लेख
• कम्प्यूटेशनल ज्योमेट्री, मार्क डी बर्ग, ओटफ्राइड च्योंग, मार्क वैन क्रेवेल्ड और मार्क ओवरमार द्वारा तीसरा संस्करण
• भाग्य एल्गोरिथम: jacquesheunis.com पर एक सहज व्याख्या
• फॉर्च्यून की एल्गोरिथ्म और blog.ivank.net पर कार्यान्वयन
• एल्गोरिदम का परिचय, थॉमस एच। कोरमेन, चार्ल्स ई। लिसेरसन, रोनाल्ड एल। रिवेस्ट और क्लिफ स्टीन द्वारा तीसरा संस्करण