गोल बाधाओं के बीच एक रास्ता ढूँढना

वन नेविगेशन

एक * पथ खोजक एल्गोरिथ्म जल्दी से इष्टतम पथ बनाने के लिए एक शक्तिशाली उपकरण है। आमतौर पर A * को ग्रिड से मैप नेविगेट करते समय दिखाया जाता है, लेकिन इसका उपयोग न केवल ग्रिड के लिए किया जा सकता है! यह किसी भी ग्राफ के साथ काम कर सकता है। आप गोल बाधाओं की दुनिया में अपना रास्ता खोजने के लिए A * का उपयोग कर सकते हैं।


मूल लेख में, सभी चित्र इंटरैक्टिव हैं।

एक एल्गोरिथ्म इन दोनों समस्याओं को कैसे हल करता है? आइए एक संक्षिप्त विवरण के साथ शुरू करें कि A * कैसे काम करता है।

एल्गोरिथम ए *

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

एल्गोरिथ्म के प्रत्येक चरण में, A * आंशिक पथों के सेट का मूल्यांकन करता है और नए पथ उत्पन्न करता है, जो सेट से बाहर सबसे होनहार पथ का विस्तार करता है। ऐसा करने के लिए, A * एक अनुमानित कतार में आंशिक पथों को संग्रहीत करता है, अनुमानित लंबाई द्वारा क्रमबद्ध - सही मापी गई पथ लंबाई और लक्ष्य के लिए अनुमानित शेष दूरी। इस अनुमान को कम करके आंका जाना चाहिए; यही है, सन्निकटन सही दूरी से कम हो सकता है, लेकिन इससे अधिक नहीं। अधिकांश पथ खोजने वाले कार्यों में, एक अच्छा समझे जाने वाला अनुमान आंशिक पथ के अंत से अंत बिंदु तक एक सीधी रेखा में ज्यामितीय दूरी है। आंशिक पथ के अंत से लक्ष्य के लिए सही सर्वोत्तम मार्ग इस सीधी रेखा की दूरी से अधिक लंबा हो सकता है, लेकिन इसे छोटा नहीं किया जा सकता है।

जब A * शुरू होता है, तो प्राथमिकता कतार में केवल एक आंशिक पथ होता है: प्रारंभिक बिंदु। एल्गोरिथ्म बार-बार प्राथमिकता कतार से सबसे आशाजनक पथ को हटाता है, अर्थात सबसे छोटी अनुमानित लंबाई वाला पथ। यदि यह पथ समाप्ति बिंदु पर समाप्त होता है, तो एल्गोरिथ्म ने कार्य पूरा कर लिया है - प्राथमिकता कतार सुनिश्चित करती है कि कोई अन्य मार्ग बेहतर नहीं हो सकता है। अन्यथा, कतार से हटाए गए आंशिक पथ के अंत से शुरू करके, A * कई और नए पथ बनाता है, सभी संभव दिशाओं में इकाई कदम उठाता है। वह इन नए रास्तों को प्राथमिकता कतार में रखता है और फिर से प्रक्रिया शुरू करता है।

राजा

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

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

एक ग्राफ के माध्यम से एक मार्ग किनारों से जुड़े नोड्स की एक श्रृंखला है:


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

अगला, हम एक ग्राफ में बाधाओं के साथ एक जंगल को बदलने का एक सरल तरीका तलाशेंगे: हम सभी संभव संक्रमण किनारों और किनारों के लिफाफे उत्पन्न करेंगे।

संक्रमण एज जनरेशन

हलकों की एक जोड़ी के बीच संक्रमण के किनारों पर लाइन सेगमेंट होते हैं जो दोनों मंडलियों को मुश्किल से छूते हैं; इस तरह के खंडों को दो बिंदुओं पर स्पर्शरेखा कहा जाता है, और प्रत्येक जोड़ी मंडलियों के लिए चार ऐसे स्पर्शरेखाएँ हैं। दो बिंदुओं के लिए स्पर्शरेखा जो कि वृत्तों के बीच अंतर को दो बिंदुओं को आंतरिक स्पर्शरेखा कहते हैं , और जो बाहर से गुजरती हैं उन्हें बाहरी कहा जाता है।

दो बिंदुओं को आंतरिक स्पर्शरेखा

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


जैसा कि यह निकला, केंद्रों के साथ हलकों के लिए $$$ए$ और $$$ब$ और रेडी $$$r_A$ और $$$r_B$ की दूरी पर जिनके केंद्र हैं $$$ड$ :

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

परिभाषित करने $$$$ थीटा$ हम आसानी से अंक पा सकते हैं $$$सी$ । $$$डी$ । $$$ई$ और $$$एफ$ ।

बाहरी स्पर्शरेखा दो बिंदुओं तक

बाहरी स्पर्शरेखा का निर्माण करते समय (यह पल्स का कार्य है ), एक समान तकनीक का उपयोग किया जाता है।


बाहरी स्पर्शरेखा के लिए हम पा सकते हैं $$$$ थीटा$ निम्नानुसार है:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

इससे कोई फर्क नहीं पड़ता कि कौन सा मंडल बड़ा है, A या B, लेकिन जैसा कि आप चित्र से देख सकते हैं, $$$$ थीटा$ किनारे पर A से B के पास स्थित है, लेकिन A से B की ओर सबसे दूर है।

दृष्टि की रेखा

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


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

एक बिंदु से दूरी की गणना करने के लिए $$$सी$ एक सीधी रेखा खंड में $$$\ overline {AB}$ हम निम्नलिखित विधि का उपयोग करेंगे:

सबसे पहले, हम गणना करते हैं $$$यू$ - खंड के साथ दूरी का हिस्सा $$$\ overline {AB}$ जहाँ लम्ब बिंदु को काटता है $$$सी$ :

$$

$$u = {(C - A) \ cdot (B-A) \ over (B-A) \ cdot (B-A)}$$

फिर हम स्थिति की गणना करते हैं $$$ई$ पर $$$\ overline {AB}$ :

$$

$$E = A + \ _ mathrm {clamp} (u, 0, 1) * (B - A)$$

दूरी $$$ड$ से $$$सी$ काटने के लिए $$$\ overline {AB}$ से दूरी है $$$सी$ को $$$ई$ :

$$

$$d = \ | ई - सी \ _$$

क्योंकि $$$d <r$ सर्कल की दृष्टि की रेखा को ओवरलैप करता है $$$ए$ में $$$ब$ , और किनारे को छोड़ दिया जाना चाहिए। अगर $$$d \ ge r$ तब की दृष्टि की रेखा $$$ए$ में $$$ब$ मौजूद है और रिब को छोड़ दिया जाना चाहिए।

एज एनवलप जनरेशन

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


एक सर्कल के किनारों के लिफाफे के सेट को खोजने के लिए, हम पहले संक्रमण के सभी किनारों को पाते हैं जो सर्कल के स्पर्शरेखा हैं। फिर सर्कल पर संक्रमण किनारों के सभी अंत बिंदुओं के बीच किनारों के लिफाफे बनाएं।

यह सब एक साथ रखना

उत्पन्न संक्रमण किनारों, किनारों और नोड्स के लिफाफे, और फिर सभी ओवरलैप किए गए संक्रमण किनारों को त्यागकर, हम एक ग्राफ बना सकते हैं और ए * एल्गोरिथ्म का उपयोग करके पथ की खोज शुरू कर सकते हैं।

सुधार

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

बाधाएं जो एक-दूसरे की चिंता करती हैं

आपने देखा होगा कि ऊपर दिखाए गए उदाहरणों में, गोल बाधाएँ ओवरलैप नहीं हुईं और स्पर्श भी नहीं हुईं। यह मानते हुए कि मंडलियां एक-दूसरे को छू सकती हैं, इससे पथ खोजने का कार्य जटिल हो जाता है

दो बिंदु स्पर्शरेखा

याद रखें कि दो बिंदुओं पर स्पर्शरेखा को आंतरिक स्पर्शरेखा के लिए इस सूत्र का उपयोग करके पाया जा सकता है:

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

और बाहरी स्पर्शरेखा के लिए सूत्र:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

जब दो वृत्त एक दूसरे को स्पर्श करते हैं या काटते हैं, तो उनके बीच कोई आंतरिक स्पर्शरेखा नहीं होती है। उस मामले में $$${r_A + r_B} \ over d$ एक से अधिक। चूंकि आर्कोसिन का मान परिभाषा के डोमेन के बाहर है $$$[- १, १]$ परिभाषित नहीं, आर्कोसिन खोजने से पहले हलकों के चौराहे की जांच करना महत्वपूर्ण है।

इसी तरह, यदि एक सर्कल दूसरे में पूरी तरह से स्थित है, तो उनके बीच कोई बाहरी स्पर्शरेखा नहीं होगी। उस मामले में $$${r_A - r_B} \ over d$ सीमा से बाहर $$$[- १, १]$ , यानी इसमें आर्कोसिन नहीं है।

ट्रांजिशन एज विजिबिलिटी की लाइन

यदि हम बाधाओं को छूने या पार करने की संभावना रखते हैं, तो संक्रमण के किनारों की दृष्टि की रेखा की गणना में नए मामले सामने आते हैं।

गणना याद करें $$$यू$ - संक्रमण के किनारे के साथ दूरी का हिस्सा जिस पर बिंदु के लंबवत किनारे को छूता है। यदि मंडलियों को छूने की अनुमति नहीं है, तो मूल्य $$$यू$ सीमा से बाहर $$$[0,1]$ , अर्थात्, सर्कल किनारे को नहीं छू सकता है, क्योंकि इसके लिए इसे किनारे के अंतिम बिंदुओं में से एक को छूना होगा। यह संभव नहीं है क्योंकि एक किनारे के अंतबिंदु पहले से ही अन्य सर्कल के लिए स्पर्शरेखा हैं।

हालांकि, यदि हम हलकों को ओवरलैप करने की संभावना की अनुमति देते हैं, तो मान $$$यू$ सीमा से बाहर $$$[0,1]$ किनारे के साथ दृष्टि की रेखा को ओवरलैप कर सकते हैं। यह उन मामलों से मेल खाता है जहां संक्रमण किनारे के अंत से परे सर्कल स्थित है, लेकिन अंत बिंदु को ओवरलैप या छूता है। गणितीय रूप से ऐसे मामलों को ट्रैक करने के लिए, हम सीमित करेंगे $$$यू$ अंतराल $$$[0,1]$ :

$$

$$ई = ए + क्लैंप (यू, 0, 1) * (बी - ए)$$

दृष्टि की लिफाफा लाइन

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


यह निर्धारित करने के लिए कि किनारे के लिफाफे को किसी अन्य बाधा से अवरुद्ध किया गया है, हम उन बिंदुओं को निर्धारित करने के लिए निम्नलिखित विधि का उपयोग करते हैं, जिन पर दो वृत्त प्रतिच्छेद करते हैं। यदि सर्कल में बिंदुओं पर केंद्र हैं $$$ए$ और $$$ब$ और रेडी $$$r_A$ और $$$r_B$ जहाँ $$$ड$ - के बीच की दूरी $$$ए$ और $$$ब$ शुरुआत के लिए, हमें कई मामलों की जाँच करने की आवश्यकता है। यदि वृत्त एक दूसरे को स्पर्श नहीं करते (अर्थात $$$d> r_A + r_B$ )
एक दूसरे के अंदर हैं ( $$$d <| r_A - r_B |$ ) या मैच ( $$$d = 0$ और $$$r_A = r_B$ ), तब मंडलियां एक दूसरे के लिफाफे को प्रभावित नहीं कर सकती हैं।

यदि इनमें से कोई एक शर्त पूरी नहीं होती है, तो वृत्त दो बिंदुओं पर प्रतिच्छेद करते हैं; यदि वृत्त एक दूसरे को स्पर्श करते हैं, तो ये दो बिंदु मेल खाते हैं। चौराहे के बिंदुओं को जोड़ने वाली मूल धुरी पर विचार करें; यह जोड़ने वाली रेखा के लंबवत है $$$ए$ और $$$ब$ कुछ बिंदु पर $$$सी$ । हम दूरी की गणना कर सकते हैं $$$एक$ से $$$ए$ को $$$सी$ निम्नानुसार है:

$$

$$a = {r_A ^ 2 - r_B ^ 2 + d ^ 2 \ over 2d}$$

खोज $$$एक$ हम कोण पा सकते हैं $$$$ थीटा$ :

$$

$$\ theta = \ arccos {a \ over r_A}$$

अगर $$$$ थीटा$ शून्य है, तो मंडलियां स्पर्श करती हैं $$$सी$ । अन्यथा, सकारात्मक और नकारात्मक के अनुरूप दो चौराहे बिंदु हैं $$$$ थीटा$ ।


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

दो बिंदुओं के लिए स्पर्शरेखा की गणना और परिवर्तन किनारों के लिए दृष्टि की रेखा और किनारों के लिफाफे में परिवर्तन करने के बाद, सब कुछ सही ढंग से।

चर अभिनेता त्रिज्या और Minkowski विस्तार

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

आस्थगित एज जनरेशन

सामान्य तौर पर, एक जंगल के लिए एक ग्राफ $$$एन$ बाधाओं में शामिल है $$$O (n ^ 2)$ संक्रमण किनारों, लेकिन उनमें से प्रत्येक के साथ दृष्टि की रेखा के लिए जाँच की जानी चाहिए $$$एन$ बाधाओं, तो कुल ग्राफ पीढ़ी का समय है $$$O (n ^ 3)$ । इसके अलावा, संक्रमण किनारों के जोड़े लिफाफे के किनारों के निर्माण के लिए नेतृत्व कर सकते हैं, और उनमें से प्रत्येक को दृष्टि की रेखा के लिए प्रत्येक बाधा के साथ जांचना चाहिए। हालांकि, ए * एल्गोरिथ्म की उच्च दक्षता के कारण, यह आमतौर पर इष्टतम पथ बनाने के लिए इस बड़े ग्राफ के केवल भाग को देखता है।

हम पहले से सभी काम करने के बजाय ए * एल्गोरिथ्म के निष्पादन के दौरान मक्खी पर ग्राफ के छोटे हिस्सों को उत्पन्न करके समय बचा सकते हैं। यदि A * जल्दी से रास्ता ढूंढ लेता है, तो हम ग्राफ का केवल एक छोटा हिस्सा उत्पन्न करेंगे। हम इसे एज जेनरेशन को neighbors() फंक्शन में ले जाकर करते हैं।

कई मामले हैं। एल्गोरिथ्म की शुरुआत में, हमें शुरुआती बिंदु के पड़ोसियों की आवश्यकता होती है। ये शुरुआती बिंदु से प्रत्येक बाधा के बाएं और दाएं किनारों पर संक्रमण के किनारों हैं।

अगला मामला तब है जब A * सिर्फ बिंदु पर पहुंच गया $$$पी$ एक बाधा के किनारे पर $$$सी$ संक्रमण बढ़त के साथ: neighbors() से आने वाले किनारों के लिफाफे वापस करना चाहिए $$$पी$ । ऐसा करने के लिए, हम यह निर्धारित करते हैं कि कौन से संक्रमण किनारों के बीच की दो बिंदुओं पर स्पर्शरेखा की गणना करके बाधा से बाहर निकलते हैं $$$सी$ और अन्य सभी बाधाएं, उन सभी को त्यागना जो दृष्टि की रेखा में नहीं हैं। फिर हम किनारों के सभी लिफाफे को जोड़ते हैं $$$पी$ इन संक्रमण किनारों के साथ, उन है कि अन्य बाधाओं से अवरुद्ध कर रहे हैं छोड़ने। हम किनारों के इन सभी लिफाफों को वापस करते हैं, neighbors() को बाद में कॉल करने के लिए संक्रमण किनारों को बचाते हैं neighbors() ।

आखिरी मामला तब है जब ए * बाधा के साथ लिफाफे के किनारे के आसपास चला गया $$$सी$ और उसे छोड़ने की जरूरत है $$$सी$ संक्रमण के किनारे के साथ। पिछले चरण की गणना और सभी संक्रमण किनारों को बचाने के बाद से, आप बस किनारों के सही सेट को ढूंढ और वापस कर सकते हैं।

हमने पसलियों के नुकीले लिफाफों को काट दिया

लिफ़ाफ़ा की पसलियाँ संक्रमण के किनारों को एक वृत्त को छूती हुई जुड़ती हैं, लेकिन यह पता चलता है कि इनमें से कई लिफ़ाफ़े पसलियों को इष्टतम तरीके से उपयोग करने के लिए उपयुक्त नहीं हैं। हम उन्हें समाप्त करके एल्गोरिथ्म को गति दे सकते हैं।

बाधाओं के जंगल के माध्यम से इष्टतम पथ हमेशा बारी-बारी से संक्रमण किनारों और किनारों के लिफाफे होते हैं। मान लीजिए हम एक नोड में प्रवेश करते हैं $$$ए$ और तय करें कि इससे कैसे बाहर निकला जाए:


के माध्यम से लॉगिन करें $$$ए$ इसका मतलब है कि हम दक्षिणावर्त घूम रहे हैं ( $$$\ $ )। हमें नोड के माध्यम से बाहर निकलना चाहिए, जो हमें दक्षिणावर्त स्थानांतरित करने की अनुमति देता है ( $$$\ $ ), अर्थात्, हम केवल नोड के माध्यम से बाहर निकल सकते हैं $$$ब$ या $$$डी$ । यदि आप से बाहर निकलते हैं $$$सी$ फिर एक विभक्ति ( $$$\ _ कर्लीवेग$ ) ऐसे तरीके जो कभी भी इष्टतम नहीं होंगे। हमें ऐसे नुकीले किनारों को छानने की जरूरत है।

सबसे पहले, ध्यान दें कि A * प्रत्येक गैर-उन्मुख बढ़त को वैसे भी संसाधित करता है। $$$P \ longleftrightarrow Q$ दो उन्मुख किनारों की तरह $$$P \ longrightarrow Q$ और $$$Q \ longrightarrow P$ । हम किनारों और नोड्स को अभिविन्यास के साथ चिह्नित करके इसका लाभ उठा सकते हैं।

1. समुद्री मील $$$पी$ अभिविन्यास के साथ नोड्स बनें - दक्षिणावर्त ( $$$P \ circlearrowright$ ) या वामावर्त ( $$$P \ _ circlearrowleft$ ) बाण।
2. अनियंत्रित संक्रमण किनारों $$$P \ longleftrightarrow Q$ उन्मुख किनारों बन जाते हैं $$$P, p \ longrightarrow Q, \ hat {q}$ और $$$Q, q \ longrightarrow P, \ hat {p}$ जहाँ $$$पी$ और $$$q$ ओरिएंटेशन हैं, और $$$\ _ {x}$ विपरीत दिशा का अर्थ है $$$x$ ।
3. अनियंत्रित रिब लिफाफे $$$P \ longleftrightarrow Q$ उन्मुख किनारों बन जाते हैं $$$P \ circlearrowright \ longrightarrow Q \ circlearrowright$ और $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ । यह वह जगह है जहां फ़िल्टरिंग होती है: हम सक्षम नहीं करते हैं $$$P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ और $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowrow$ , क्योंकि दिशा में बदलाव से किंक बनते हैं ( $$$\ _ कर्लीवेग$ )।

हमारे सर्किट में, नोड $$$ए$ दो नोड्स में बदल जाएगा, $$$A \ circlearrowright$ और $$$A \ _ circlearrowleft$ यह एक आने वाली संक्रमण बढ़त है $$$\ longrightarrow A \ circlearrowright$ और आउटगोइंग ट्रांज़िशन एज $$$A \ circlearrowleft \ longrightarrow$ । अगर हम सड़क से गुजरते हैं $$$A \ circlearrowright$ फिर नोड के माध्यम से बाहर निकलना चाहिए $$$\ $ जो या तो एक संक्रमण बढ़त होगी $$$B \ circlearrowright \ longrightarrow$ (लिफाफा किनारे के माध्यम से $$$A \ circlearrowright \ longrightarrow B \ circlearrowright$ ), या संक्रमण बढ़त $$$D \ circlearrowright \ longrightarrow$ (लिफाफा किनारे के माध्यम से $$$A \ circlearrowright \ longrightarrow D \ circlearrowright$ )। हम बाहर नहीं निकल सकते $$$C \ circlearrowleft \ longrightarrow$ , क्योंकि रोटेशन की दिशा इस तरह बदल जाएगी, और हमने किनारे के लिफाफे को फ़िल्टर किया $$$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ ।

ग्राफ से किनारों के इन नुकीले लिफाफे को फ़िल्टर करके, हमने एल्गोरिथ्म की दक्षता में वृद्धि की।

कटे हुए किनारों को काटना

आंशिक रास्तों को काट दिया जा सकता है, जो संक्रमण के अंतिम किनारों को संक्रमण के किनारे को पार कर जाता है।

बहुभुज बाधाएं

गेम यंग प्रोग्रामिंग 2 देखें, अध्याय 3.10, थॉमस यंग द्वारा लिखित पॉइंट्स-ऑफ-विजिबिलिटी पाथफाइंडिंग का अनुकूलन। यह अध्याय क्लिपिंग नोड्स पर चर्चा करता है, लेकिन हलकों के लिए नहीं, बल्कि बहुभुज के लिए।

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

• बेल्ट का कार्य
• चरखी का काम
• बिंदु और रेखा के बीच की दूरी
• दो वृत्तों का परस्पर संबंध