Delaunay त्रिभुज एल्गोरिथ्म स्वीपिंग लाइन विधि द्वारा

आपका दिन शुभ हो!

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

समस्या की परिभाषाएँ और कथन

ट्राईऐन्ग्युलेशंस

ऐसा कहा जाता है कि समतल पर बिंदुओं के सेट पर त्रिकोणासन दिया जाता है यदि कुछ जोड़ियों को एक किनारे से जोड़ा जाता है, तो परिणामस्वरूप ग्राफ में कोई भी परिमित चेहरा एक त्रिकोण बनाता है, किनारों को काटता नहीं है, और ग्राफ किनारों की संख्या में अधिकतम है।

Delaunay त्रिकोण

एक डेलॉनाय त्रिकोण एक त्रिभुज है जिसमें किसी भी त्रिभुज के लिए यह सच है कि इसके चारों ओर परिचालित सर्कल के अंदर मूल सेट से कोई अंक नहीं हैं।

नोट : अंकों के दिए गए सेट के लिए, जिसमें कोई भी 4 अंक एक ही सर्कल में नहीं है, बिल्कुल एक Delaunay त्रिकोण है।

द डेलॉयन कंडीशन

अंक के सेट पर त्रिकोणासन करने दें। हम कहते हैं कि अंकों का एक निश्चित सबसेट डेलॉनाय स्थिति को संतुष्ट करता है यदि इस उपसमुच्चय पर बंधे त्रिभुज उसके लिए Delaunay त्रिकोण है।

Delaunay त्रिकोण के लिए मानदंड

एक त्रिकोणासन में चतुष्कोण बनाने वाले सभी बिंदुओं के लिए डिलायने की स्थिति की पूर्ति इस तथ्य के बराबर है कि यह त्रिकोण एक Delaunay त्रिभुज है।

नोट : गैर-उत्तल चतुष्कोणों के लिए, डिलायने की स्थिति हमेशा पूरी होती है, और उत्तल चतुष्कोणों के लिए (जिनके वर्टिकल एक ही वृत्त पर नहीं होते हैं) बिल्कुल 2 संभावित त्रिकोण हैं (जिनमें से एक Delaunay त्रिभुज है)।

कार्य दिए गए बिंदुओं के लिए Delaunay त्रिभुज का निर्माण करना है।

एल्गोरिथम विवरण

दर्शनीय बिंदु और दृश्यमान किनारे

एक न्यूनतम उत्तल पतवार (इसके बाद, MBO) को बिंदुओं के एक सीमित सेट (कुछ बिंदुओं को जोड़ने वाले किनारों) से दिया जाता है ताकि वे एक बहुभुज का निर्माण करें जिसमें सेट के सभी बिंदु हों) और एक बिंदु पतवार के बाहर झूठ बोल रहा है। तब विमान के बिंदु को बिंदु A के लिए दृश्यमान कहा जाता है, यदि बिंदु A से जुड़ने वाला खंड MBO को नहीं काटता है।

एक बिंदु के लिए एक MBO बढ़त को बिंदु A के लिए दृश्यमान कहा जाता है, यदि इसके छोर A के लिए दृश्यमान हैं।

निम्नलिखित छवि में, लाल बिंदु के लिए दिखाई देने वाले किनारों को लाल रंग में चिह्नित किया गया है:

नोट : Delaunay triangulation समोच्च उन बिंदुओं के लिए MBO है जिन पर यह बनाया गया है।

टिप्पणी 2 : एल्गोरिथ्म में, जोड़े गए बिंदु के लिए दिखाई देने वाले किनारे एक श्रृंखला बनाते हैं, यानी एक पंक्ति में कई MBO किनारे

स्मृति में त्रिकोणीय संचय

कुछ मानक विधियाँ हैं जिनका वर्णन Skvortsov की पुस्तक में किया गया है [1]। एल्गोरिथ्म की बारीकियों के कारण, मैं अपने स्वयं के संस्करण की पेशकश करूंगा। चूंकि हम Delaunay स्थिति के लिए 4-गनों की जांच करना चाहते हैं, इसलिए हम उनकी संरचना पर विचार करते हैं। त्रिभुज में प्रत्येक चतुर्भुज 2 त्रिभुज होता है जिसमें एक सामान्य किनारा होता है। प्रत्येक किनारे के ठीक बगल में 2 त्रिकोण होते हैं। इस प्रकार, त्रिकोणीय में प्रत्येक चतुर्भुज एक किनारे और आसन्न त्रिकोण में किनारे के विपरीत दो कोने से उत्पन्न होता है।
चूंकि दो त्रिभुज और उनके आसन्न किनारे और दो कोने के साथ बहाल किए जाते हैं, हम ऐसी सभी संरचनाओं के लिए त्रिभुज को पुनर्स्थापित कर सकते हैं। तदनुसार, यह सेट में दो छोरों के साथ एक किनारे को स्टोर करने और किनारे के साथ एक खोज करने का आदेश दिया गया है (आदेशित जोड़ी का एक जोड़ा)।

एल्गोरिथ्म

स्वीपिंग लाइन का विचार यह है कि सभी बिंदुओं को एक दिशा में क्रमबद्ध किया जाता है, और फिर बदले में संसाधित किया जाता है।

1. समन्वय द्वारा सीधी रेखा के साथ सभी बिंदुओं को क्रमबद्ध करें $$$x$)।
2. हम पहले 3 बिंदुओं पर एक त्रिकोण बनाते हैं।
   
   इसके अलावा, प्रत्येक अगले बिंदु के लिए हम उन कदमों को उठाएंगे, जो कि हमलावर को संरक्षित करते हैं कि पहले से ही जोड़े गए अंकों के लिए एक डिलायना ट्राइग्यूलेशन है और तदनुसार, उनके लिए एक एमबीओ।
3. दृश्य किनारों और स्वयं बिंदु द्वारा गठित त्रिकोण जोड़ें (जो कि दिखाई देने वाले किनारों के सभी सिरों पर बिंदु से किनारों को जोड़ते हैं)।
4. हम दृश्य किनारों द्वारा उत्पन्न सभी चतुष्कोणों की Delaunay स्थिति की जांच करते हैं। यदि हालत कहीं पूरी नहीं हुई है, तो हम चतुर्भुज में त्रिकोणीकरण का पुनर्निर्माण करते हैं (मुझे याद है कि उनमें से केवल दो हैं) और वर्तमान चतुर्भुज के किनारों द्वारा उत्पन्न चतुष्कोणों के लिए चेक को फिर से चलाते हैं (क्योंकि उनके बाद ही डेलुनाय स्थिति का उल्लंघन हो सकता है)।

नोट : चरण में (4) एक पुनरावर्ती शुरुआत के दौरान, आप इस पुनरावृत्ति पर विचार किए गए बिंदु से आने वाले किनारों द्वारा उत्पन्न चतुष्कोणों की जांच नहीं कर सकते हैं (उनमें से चार में से हमेशा दो होते हैं)। सबसे अधिक बार वे गैर-उत्तल होंगे, उत्तल के लिए सबूत विशुद्ध रूप से ज्यामितीय है, मैं इसे पाठक पर छोड़ दूंगा। इसके अलावा, हम मानते हैं कि प्रत्येक पुनर्निर्माण के लिए केवल 2 पुनरावर्ती प्रारंभ किए जाते हैं।

एक Delaunay शर्त सत्यापित करना

Delaunay स्थिति के लिए चतुष्कोण परीक्षण करने के तरीके एक ही पुस्तक [1] में मिल सकते हैं। मैं केवल यह ध्यान देता हूं कि जब वहां से त्रिकोणमितीय कार्यों के साथ एक विधि का चयन किया जाता है, तो गलत तरीके से कार्यान्वयन के साथ, साइन के नकारात्मक मूल्य प्राप्त किए जा सकते हैं, यह उन्हें मॉडुलो लेने के लिए समझ में आता है।

दृश्यमान किनारों की खोज करें

यह समझने के लिए बना हुआ है कि प्रभावी रूप से दृश्यमान किनारों को कैसे पाया जाए। ध्यान दें कि पिछले जोड़ा बिंदु S वर्तमान पुनरावृत्ति पर MBO में है, क्योंकि इसमें सबसे बड़ा समन्वय है $$$x$, और वर्तमान बिंदु के लिए भी दिखाई देता है। फिर, यह देखते हुए कि दृश्य किनारों के छोर दृश्य बिंदुओं की एक सतत श्रृंखला बनाते हैं, हम बिंदु एस से एमबीओ के साथ दोनों दिशाओं में जा सकते हैं और किनारों को इकट्ठा कर सकते हैं जब वे दिखाई देते हैं (किनारे की दृश्यता की जाँच वेक्टर उत्पाद का उपयोग करके की जाती है)। इस प्रकार, एमबीओ को एक दोहरी रूप से जुड़ी सूची के रूप में संग्रहीत करना सुविधाजनक है, प्रत्येक पुनरावृत्ति पर दृश्य किनारों को हटाकर और माना बिंदु से 2 नए जोड़ते हैं।

एल्गोरिदम दृश्य

दो लाल डॉट्स - जोड़ा और पिछले। हर पल लाल किनारे कदम (4) से पुनरावृत्ति स्टैक बनाते हैं:

एल्गोरिथ्म शुद्धता

एल्गोरिथ्म की शुद्धता को साबित करने के लिए, चरण (3) और (4) में अपरिवर्तनीय के संरक्षण को साबित करने के लिए पर्याप्त है।

चरण (3)

चरण (3) के बाद, जाहिर है, हमें अंकों के वर्तमान सेट का कुछ त्रिकोणीयकरण प्राप्त होता है।

चरण (4)

चरण (4) की प्रक्रिया में, सभी चतुर्भुज जो डेलुनाय स्थिति को संतुष्ट नहीं करते हैं, वे पुनरावृत्ति के ढेर में हैं (विवरण से), जिसका अर्थ है कि चरण (4) के अंत में सभी चतुर्भुज Delaunay स्थिति को संतुष्ट करते हैं, अर्थात्, Delaunay त्रिभुज वास्तव में निर्मित होता है। फिर यह साबित होता है कि चरण (4) में प्रक्रिया किसी दिन समाप्त हो जाएगी। यह इस तथ्य से निम्नानुसार है कि पुनर्निर्माण के दौरान जोड़े गए सभी किनारों को प्रश्न में मौजूदा शीर्ष (यानी, चरण में) से आते हैं $$$k$से अधिक नहीं हैं $$$k-1$) और इस तथ्य से कि इन किनारों को जोड़ने के बाद हम उनके द्वारा उत्पन्न चतुष्कोणों पर विचार नहीं करेंगे (पिछली टिप्पणी देखें), जिसका अर्थ है कि हम एक से अधिक बार नहीं जोड़ेंगे।

समय की जटिलता

औसतन, एल्गोरिथ्म समान रूप से समान, सामान्य वितरण पर काम करता है (परिणाम नीचे दी गई तालिका में दिखाए गए हैं)। एक धारणा है कि इसका काम करने का समय है $$$O (NlogN)$। सबसे खराब स्थिति में, एक मूल्यांकन होता है $$$O (N ^ 2)$।

आइए भागों में काम करने के समय पर एक नज़र डालें और समझें कि किसका कुल समय पर सबसे अधिक प्रभाव पड़ता है:

दिशा के अनुसार क्रमबद्ध करें

छँटाई के लिए, हम अनुमान का उपयोग करेंगे $$$O (NlogN)$।

दृश्यमान किनारों की खोज करें

सबसे पहले, हम दिखाते हैं कि दिखाई देने वाले किनारों की खोज में बिताया गया कुल समय है $$$O (N)$। ध्यान दें कि प्रत्येक पुनरावृत्ति पर हम सभी दृश्य किनारों और 2 अधिक (पहले दिखाई नहीं देते हैं) रैखिक समय में पाते हैं। चरण (3) में, हम MBO में नए 2 किनारों को जोड़ते हैं। इस प्रकार, कुल मिलाकर, इससे अधिक नहीं $$$2N$पसलियों, इसलिए, और विभिन्न दिखाई पसलियों कोई और अधिक हो जाएगा $$$2N$। हम भी पा लेंगे $$$2N$किनारों जो दिखाई नहीं दे रहे हैं। इस प्रकार, कुल में और अधिक नहीं है $$$4N$पसलियों जो समय के साथ मेल खाती हैं $$$O (N)$।

नए त्रिकोण का निर्माण

पहले से ही दिखाई किनारों के साथ चरण (3) से त्रिकोणों के निर्माण के लिए कुल समय स्पष्ट रूप से है $$$O (N)$।

त्रिभुज का पुनर्निर्माण

यह चरण (4) से निपटने के लिए बनी हुई है। सबसे पहले, ध्यान दें कि डिलायने की स्थिति की जांच करना और अगर यह पूरा नहीं हुआ है तो पुनर्निर्माण करना काफी महंगा कार्य है (हालांकि वे इसके लिए काम करते हैं $$$O (1)$)। केवल Delaunay की स्थिति की जांच करने पर लगभग 28 अंकगणितीय ऑपरेशन हो सकते हैं। आइए इस चरण के दौरान औसत संख्या में पुनर्खरीद देखें। कुछ वितरणों पर व्यावहारिक परिणाम नीचे दिए गए हैं। उनके लिए मैं वास्तव में कहना चाहता हूं कि पुनर्व्यवस्था की औसत संख्या एक लघुगणक गति के साथ बढ़ती है, लेकिन हम इसे एक धारणा के रूप में छोड़ देते हैं।

यहां मैं यह भी नोट करना चाहता हूं कि प्रति पॉइंट की पुनर्व्यवस्था की संख्या उस दिशा से बहुत भिन्न हो सकती है जिसके साथ छंटनी की जाती है। तो, एक लाख के लिए समान रूप से 100000: 1 के एक पहलू अनुपात के साथ एक लंबी कम आयत पर वितरित किया जाता है, यह संख्या 1.2 से 24 तक भिन्न होती है (ये मान क्रमशः डेटा को क्षैतिज और ऊर्ध्वाधर रूप से सॉर्ट करते समय प्राप्त किए जाते हैं)। इसलिए, मैं मनमाने तरीके से (इस उदाहरण में, मनमाने ढंग से चयन के साथ, औसतन लगभग 2 पुनर्वित्त प्राप्त किया गया था) या मैन्युअल रूप से डेटा का अग्रिम रूप से ज्ञात होने पर इसका चयन करने के बिंदु को देखता हूं।

इस प्रकार, मुख्य समय कार्यक्रम आमतौर पर चरण (4) पर ले जाता है। यदि यह जल्दी से चलता है, तो यह छँटाई करने के बारे में सोचने के लिए समझ में आता है।

सबसे खराब मामला

सबसे खराब मामला $$$k$वें पुनरावृत्ति होती है $$$k-1$चरण (4) में पुनरावर्ती कॉल, अर्थात्, सभी पर संक्षेप में, हम सबसे खराब स्थिति में स्पर्शोन्मुख व्यवहार प्राप्त करते हैं $$$O (N ^ 2)$। निम्न चित्र एक सुंदर उदाहरण दिखाता है, जिस पर कार्यक्रम लंबे समय तक काम कर सकता है (10,000 अंक के इनपुट के साथ एक नया बिंदु जोड़ते समय औसतन 1100 पुनर्मिलन)।

केडी-ट्री का उपयोग करते हुए एक डिलायने त्रिकोण के निर्माण के लिए एक पुनरावृत्ति एल्गोरिथ्म के साथ तुलना

पुनरावृत्त एल्गोरिथ्म का वर्णन

मैं उपरोक्त एल्गोरिथ्म का संक्षेप में वर्णन करूंगा। जब अगला बिंदु आता है, तो हम केडी-ट्री का उपयोग करते हैं (मैं आपको इसके बारे में कहीं पढ़ने की सलाह देता हूं, यदि आप नहीं जानते हैं), तो हम एक त्रिकोण पाते हैं जो पहले से ही काफी करीब है। तब गहराई में जाकर हम एक त्रिभुज की तलाश करते हैं, जिसमें बिंदु स्वयं गिरता है। हम किनारों को मिलाए गए त्रिकोण के कोने तक बढ़ाते हैं और वास्तव में नए एल्गोरिदम के लिए हमारे एल्गोरिथ्म से चरण (4) करते हैं। चूंकि बिंदु त्रिभुज के बाहर हो सकता है, इसलिए सरलीकरण के लिए एक बड़े त्रिकोण के साथ सभी बिंदुओं को कवर करना प्रस्तावित है (अग्रिम में इसका निर्माण करने के लिए), इससे समस्या का समाधान होगा।

एल्गोरिदम की समानता

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

एल्गोरिथम अंतर

एक पुनरावृत्त एल्गोरिथ्म में, एक बिंदु का स्थानीयकरण (वांछित त्रिकोण के लिए खोज) औसतन ओवर होता है $$$O (logN)$उपरोक्त वितरण पर, औसतन, 3 पुनर्वितरण होते हैं (जैसा कि [1] में दिखाया गया है) अंकों की आपूर्ति के एक मनमाने क्रम के तहत। इस प्रकार, स्वीपिंग लाइन स्थानीयकरण में पुनरावृत्ति एल्गोरिथ्म के समय को जीतती है, लेकिन इसे पुनर्निर्माण में खो देती है (जो मुझे याद है, काफी कठिन हैं)। इसके अलावा, पुनरावृत्त एल्गोरिथ्म ऑनलाइन काम करता है, जो इसकी विशिष्ट विशेषता भी है।

निष्कर्ष

यहाँ मैं एल्गोरिथ्म के संचालन के परिणामस्वरूप कुछ दिलचस्प त्रिकोणताएँ दिखाता हूँ।

सुंदर पैटर्न

सामान्य वितरण, 1000 अंक

यहां तक ​​कि वितरण, 1000 अंक

रूस के सभी शहरों के स्थानों पर निर्मित त्रिकोणासन

यहाँ आप इस एल्गोरिथ्म के लिए मेरे कोड का एक उदाहरण देख सकते हैं:
github.com/Vemmy124/Delaunay-Triangulation-Algorithm

आपका ध्यान के लिए धन्यवाद!

साहित्य

[१] स्कोवर्त्सोव ए.वी. Delaunay त्रिकोण और इसके अनुप्रयोग। - टॉम्स्क: पब्लिशिंग हाउस टॉम। विश्वविद्यालय, 2002 ।-- 128 पी। आईएसबीएन 5-7511-1501-5