एल्गोरिदम हब के पन्नों के माध्यम से स्क्रॉल करते हुए, मैं एक बहुभुज में एक बिंदु को स्थानीय करने की समस्या को हल करने के लिए समर्पित एक विषय पर आया: एक बहुभुज दिया गया है (स्व-चौराहों के बिना एक बंद पॉलीलाइन), यह निर्धारित करना आवश्यक है कि एक दिया गया बिंदु इस बहुभुज के अंदर है या नहीं। विषय पर अंतिम टिप्पणियों में से एक में, विस्मय व्यक्त किया गया था कि इस तरह की विशुद्ध गणितीय समस्या एल्गोरिदम के सिद्धांत से कैसे संबंधित है। हस-है, और सबसे तत्काल। स्थानीयकरण समस्या कम्प्यूटेशनल ज्यामिति (कंप्यूटर ग्राफिक्स के साथ भ्रमित नहीं होना) का एक शास्त्रीय कार्य है। वार्म-अप के रूप में, दाईं ओर की तस्वीर को देखना प्रस्तावित है, जो पीनो कर्व (स्रोत [ 1 ]) की तरह एक बहुभुज दिखाता है, और सवाल का जवाब देने की कोशिश करता है - ~~क्या आपको~~ लाल डॉट ~~गोफर दिखाई देता है?~~ ~~और मैं नहीं देखता, लेकिन वह है!~~ क्या यह बहुभुज के अंदर या बाहर है? नीचे, हम (विशेष रूप से शैक्षिक उद्देश्यों के लिए) इस समस्या के एक साधारण बदलाव पर विचार करेंगे जब दिए गए बहुभुज उत्तल होते हैं।

यह स्पष्ट है कि यदि एक बहुभुज एक त्रिभुज या एक चतुर्भुज है, तो शब्द के पूर्ण अर्थ में कोई भी एल्गोरिदम उत्पन्न नहीं होता है, लेकिन तीन या चार सूत्र उत्पन्न होते हैं जिन्हें प्रोग्राम करने की आवश्यकता होती है। हालांकि, एक पूरी तरह से अलग कहानी शुरू होती है यदि बहुभुज के कोने की संख्या बड़ी है। उदाहरण के लिए, एक मिलियन या एक सौ मिलियन चोटियां। ऐसा कार्य पहले से ही अपने आप में काफी एल्गोरिदम लगता है। भोली एल्गोरिथ्म (किसी दिए गए बिंदु से एक किरण शुरू करना और बहुभुज के किनारों के साथ इसके चौराहों की संख्या की गिनती करना) बहुभुज n के कोने की संख्या में रैखिक है, क्योंकि हमें बहुभुज के सभी पक्षों के साथ किरण के प्रतिच्छेदन की जांच करनी चाहिए। तदनुसार, सवाल उठता है, क्या यह तेजी से करना संभव है, अर्थात। क्या इस कथन में स्थानीयकरण समस्या को हल करने के लिए एक उदासीन एल्गोरिथ्म है? इस प्रश्न का सही उत्तर है हां, समस्या को समय हे (लॉग ₂ एन) में हल किया जा सकता है। सामान्य मामले में समाधान का विवरण, जब बहुभुज को उत्तल नहीं होना पड़ता है, तो एक अद्भुत पुस्तक [ 2 ] में पाया जा सकता है। और नीचे हम देखेंगे कि आप एक उत्तल बहुभुज में एक बिंदु को स्थानीय करने की समस्या को द्विआधारी खोज एल्गोरिदम कैसे लागू कर सकते हैं।

छोटा शैक्षिक कार्यक्रम

तीन बिंदुओं A, B और C को दिए जाएं। मान लीजिए कि हम बिंदु A से बिंदु B की ओर देखते हैं। बिंदु C हमारे टकटकी की दिशा के संबंध में बिंदु से दाईं ओर या बाईं ओर मुड़ता है? इस सवाल का जवाब वैक्टर के वेक्टर उत्पाद की मदद से दिया जा सकता है a = AB और b = BC, अधिक सटीक रूप से ऐसे उत्पाद के z- समन्वय की सहायता से, जिसकी गणना सरल सूत्र z = a _x b _y -a _y _{x द्वारा की जाती है} । यदि z> 0 है, तो वांछित रोटेशन छोड़ दिया जाता है, यदि z <0 तो सही। यदि ~~सिक्का किनारे~~ z = 0 ~~पर गिरता है~~ , तो तीन बिंदु एक सीधी रेखा पर स्थित होते हैं (वे कहते हैं कि वैक्टर a और b टकरा रहे हैं)।

पायथन कोड रोटेशन की दिशा की गणना प्राथमिक है (अंक 2 लंबाई की सूची द्वारा दर्शाए गए हैं):

def rotate(A,B,C): return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])

इस तरह के एक उपयोगी कार्य करने के बाद, आप बहुत सारे अच्छे काम कर सकते हैं। उदाहरण के लिए, आप यह निर्धारित कर सकते हैं कि क्या दो दिए गए खंड AB और CD प्रतिच्छेद हैं? यह, वैसे, कम्प्यूटेशनल ज्यामिति का एक और बुनियादी संचालन है, और हमें भी जल्द ही इसकी आवश्यकता होगी (हालांकि केवल एक बार)। यह विचार सरल है - दो सेगमेंट यदि और केवल तभी एक सेगमेंट का अंत दूसरे के विपरीत पक्षों पर और इसके विपरीत होते हैं।

यह जाँचने के लिए कि अंक C और D खंड (वेक्टर) AB के सापेक्ष विपरीत दिशा में स्थित हैं, आपको घूर्णन (A, B, C) और घूर्णन (A, B, D) के घूर्णन दिशाओं को देखना होगा। यदि इन अभिव्यक्तियों के संकेत अलग-अलग हैं, तो लाइन एबी सेगमेंट सीडी (और आंतरिक बिंदु पर) को प्रतिच्छेद करती है। दो संख्याओं के संकेत अलग-अलग हैं, यदि और केवल यदि उनका उत्पाद नकारात्मक है। इसलिए, एबी और सीडी खंडों के प्रतिच्छेदन की कसौटी दो अभिव्यक्तियों की नकारात्मकता है (ए, बी, सी) * घुमाएं (ए, बी, डी) और घुमाएं (सी, डी, ए) * घुमाएं (सी, डी, बी)। यदि हम सख्त नकारात्मकता को गैर-संवेदनशीलता के साथ बदलते हैं, तो हम खंडों के अंतिम बिंदुओं पर अंतर-बिंदु को पकड़ सकते हैं। हमें कुछ मध्यवर्ती विकल्प की आवश्यकता होगी, अर्थात्, एक उत्पाद शून्य के साथ तुलना में सख्ती से किया जाएगा, दूसरा - सख्ती से:

 def intersect(A,B,C,D): return rotate(A,B,C)*rotate(A,B,D)<=0 and rotate(C,D,A)*rotate(C,D,B)<0

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

बाइनरी सर्च

अब हम स्थानीयकरण के लिए जाते हैं। एक उत्तल बहुभुज P को n कोने और एक बिंदु से मिलकर A को देखते हुए। यह माना जाता है कि P में कोने क्रमांकित वामावर्त हैं (वे कहते हैं कि P की परिधि के साथ ट्रैवर्सल की दिशा सकारात्मक है)।

एल्गोरिथ्म का विचार: बहुभुज P ₀ के पहले शीर्ष को लें और यह निर्धारित करने का प्रयास करें कि किस खंड (कोण) में P _i P P P _{i + 1} बिंदु A. सबसे पहले, देखें कि A खंड P _n-1 P ₀ P ₁ P में आता है यदि ऐसा नहीं है, तो ए को बहुभुज के बाहर झूठ बोलने की गारंटी है।

कोड:

 def pointloc(P,A): n = len(P) if rotate(P[0],P[1],A)<0 or rotate(P[0],P[n-1],A)>0: return False

फिर सब कुछ शास्त्रीय द्विआधारी खोज में है - हमने p = 1, r = n-1 (वर्तमान खंड की सीमाएं) निर्धारित की हैं, मध्य शीर्ष q q (p + r) / 2 की गणना करें, जहां वेक्टर वेक्टर ₀ P _{q के} सापेक्ष A स्थित है, वहां देखें बाएं, फिर r को q से बदलें, यदि दाईं ओर, तो p को q से बदलें।

हम इस प्रक्रिया को तब तक जारी रखते हैं जब तक कि यह आरपी = 1 न हो जाए:

  p, r = 1, n-1 while rp>1: q = (p+r)/2 if rotate(P[0],P[q],A)<0: r = q else: p = q

अब यह जांचना बाकी है कि क्या सेगमेंट P ₀ A और P _P P _आर इंटरसेक्ट है?
यदि वे प्रतिच्छेद करते हैं, तो बिंदु A बाहर स्थित है, यदि वे प्रतिच्छेद नहीं करते हैं, तो अंदर।

कोड:

  return not intersect(P[0],A,P[p],P[r])

बस इतना ही ...

परिणाम

यह सत्यापित करना आसान है कि एल्गोरिथ्म की जटिलता शास्त्रीय बाइनरी सर्च एल्गोरिदम - ओ (लॉग ₂ एन) के समान है। और सब कुछ बहुत अच्छा होगा यदि यह एल्गोरिथ्म उत्तल बहुभुज के लिए तेज नहीं किया गया था। निष्पक्षता में, हमने जिस एल्गोरिथ्म की जांच की है वह कुछ गैर-उत्तल बहुभुजों के साथ भी काम करता है, लेकिन एक बहुत ही विशिष्ट प्रकार का - ऐसे बहुभुजों में शून्य शीर्ष से आने वाले सभी विकर्ण बहुभुज के अंदर झूठ होना चाहिए:

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

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

पुनश्च: विषय के शीर्ष पर तस्वीर के साथ कार्य आसानी से किसी भी ग्राफिक्स संपादक में हल किया जाता है: भरण उपकरण का चयन करें, पृष्ठभूमि से एक अलग रंग लें, चित्र के किनारे पर क्लिक करें (बहुभुज के बाहर) और वॉइला!

साहित्य

पी। प्रिसिंकविक्ज़, ए। लिंडेनमायर, पौधों की एल्गोरिदमिक सुंदरता , 1996
एम। डी। बर्ग, ओ। चेयोंग, एम। वैन क्रेवेल्ड, एम। ओवरमर, कम्प्यूटेशनल ज्यामिति। एल्गोरिदम और अनुप्रयोग , 2008
एफ। प्रिपटाटा, एम। शेमोस, कम्प्यूटेशनल ज्यामिति , 1989

एक उत्तल बहुभुज में एक बिंदु का स्थानीयकरण

छोटा शैक्षिक कार्यक्रम

बाइनरी सर्च

परिणाम

साहित्य

More articles: