👨🏾 🌼 🧗🏻 मोशन प्लानिंग: दृश्यता का ग्राफ, रोडमैप 🏘️ 👣 👩‍👦‍👦

सभी को शुभ दिन। इस लेख में, मैं कम्प्यूटेशनल ज्यामिति से संबंधित कुछ एल्गोरिदम के बारे में बात करना चाहूंगा, जो वर्तमान में खेल के विकास में व्यापक रूप से उपयोग किए जाते हैं। यदि आपने कम से कम एक बार एक गेम प्रोग्राम किया है जिसमें एक चरित्र (स्थान) एक स्थान के चारों ओर घूम रहा है, तो आपको रास्ता खोजने की समस्या को हल करना होगा। मैं इस समस्या को हल करने के तरीकों में से एक के बारे में बात करना चाहता हूं।

समस्या का बयान

तिरस्कार बहुभुज P का एक सेट दें - बहुभुज बाधाएं दी जाएं। एक ही विमान में एक एजेंट को आगे बढ़ने दें - यह एक डॉट द्वारा दर्शाया गया है। शुरुआती बिंदु को और अंतिम बिंदु f को बताएं। हमें बिंदु s से बिंदु f तक सबसे छोटा मार्ग बनाने की आवश्यकता है, जबकि हम मानते हैं कि एजेंट बाधा की सीमा पर हो सकता है, लेकिन इसके अंदर नहीं।

निर्णय

इष्टतम तरीका है

यह साबित किया जा सकता है कि इष्टतम पथ एक टुकड़े-टुकड़े में रेखीय टूटी हुई रेखा है जिसका सिरा बाधाओं के कोने से मेल खाता है।

सबूत

भाग 1. इष्टतम पथ - टुकड़ा रेखीय पॉलीलाइन

मान लीजिए कि सबसे छोटा रास्ता टी - एक टुकड़े-टुकड़े रैखिक टूटी हुई रेखा नहीं है। इस मामले में, पथ T पर एक बिंदु p मौजूद है जो T (चित्र 1) से किसी भी सीधे खंड से संबंधित नहीं है। इसका मतलब है कि बिंदु p (चित्रा 2) का एक ε-पड़ोस मौजूद है जिस पर कोई बाधा नहीं आती है। इस मामले में, उप-टी the जो ath-पड़ोस के अंदर है, को कॉर्ड के साथ छोटा किया जा सकता है, पथ। के साथ neighborhood-पड़ोस की सीमा के चौराहे के बिंदुओं को जोड़ने के साथ। चूंकि मार्ग का हिस्सा कम किया जा सकता है, तो पूरा रास्ता कम किया जा सकता है, और इसलिए मूल धारणा गलत है। पथ टी एक टुकड़े वाली रैखिक टूटी हुई रेखा है।


चित्रा 1. पथ टी पर बिंदु पी	चित्रा 2. 2.-p का पड़ोस	चित्रा 3. सबसे छोटा रास्ता कॉर्ड

भाग 2. मार्ग के शीर्ष बाधाओं के शीर्ष के साथ मेल खाते हैं
अब मान लीजिए कि पथ टी के कोने बाधा पॉलीगोन के कोने के साथ मेल नहीं खाते हैं। पथ के शीर्ष v पर विचार करें। शीर्ष मुक्त स्थान के अंदर झूठ नहीं बोल सकता, क्योंकि अन्यथा, एक समान दृष्टिकोण का उपयोग करके, हम शीर्ष v (चित्रा 4) के neighborhood-पड़ोस में जीवा के साथ एक छोटा मार्ग पाएंगे। इसलिए, शीर्ष v को बाधाओं की सीमाओं पर (उनके शीर्ष पर या किनारों पर) झूठ होना चाहिए। लेकिन शीर्ष पर किनारों पर झूठ नहीं हो सकता है, क्योंकि (फिर से हम neighborhood-पड़ोस पर विचार करते हैं), हम कॉर्ड (चित्रा 5) के साथ काट सकते हैं।


चित्रा 4. खाली स्थान में पड़े हुए मार्ग के शीर्ष का neighborhood-पड़ोस	चित्रा 5. किनारे पर पड़े हुए पथ के शीर्ष का neighborhood-पड़ोस

उपरोक्त का अर्थ है कि टुकड़े-टुकड़े रैखिक पथ T के कोने बाधाओं-बहुभुज के कोने पर स्थित होना चाहिए।

दृश्यता ग्राफ

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

चित्र 6. दृश्यता ग्राफ का एक उदाहरण।

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

एक दृश्यता ग्राफ का निर्माण: एक भोली एल्गोरिथ्म

हम ग्राफ़ वीजी ⁺ में सभी जोड़ियों के माध्यम से सॉर्ट करेंगे और उनमें से प्रत्येक के लिए यह जांच करेगा कि क्या बाधा किनारे के चौराहों के कोने को जोड़ने वाला खंड है या नहीं। यह देखना आसान है कि इस तरह के एल्गोरिथ्म की जटिलता ओ (एन ³ ) है, क्योंकि हमारे पास एन ² जोड़े कोने और ओ (एन) किनारों हैं।

O (n ² log (n)) में दृश्यता ग्राफ बनाना

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

चित्रा 7. एक घूर्णन बीम के साथ एक विमान को स्वीप करना

पी बिंदु से गुजरने वाले अक्ष के सापेक्ष कोण द्वारा आदेशित कोने को घटना कतार में संग्रहीत किया जाएगा। स्थिति को प्रारंभ करने में O (nlog (n)) समय लगेगा, इवेंट कतार को प्रारंभ करने में O (nlog (n)) समय भी लगेगा। स्वीपिंग एल्गोरिथ्म का कुल ऑपरेटिंग समय O (nlog (n)) है, इस प्रकार, ग्राफ के प्रत्येक शीर्ष के लिए एल्गोरिथ्म को लागू करते हुए, हम O (n ² log (n)) के आदेश के समय एक दृश्यता ग्राफ प्राप्त करते हैं।
औपचारिक रूप से। नापसंद बहुभुज-बाधा के सेट के किनारों की संख्या n होने दें। बिगाड़ने वालों में, मैं एक छद्म भाषा में कोड का हवाला दूंगा जो जावा के समान है।

दृश्यता ग्राफ का निर्माण

public final G buildVisibilityGraph(final Set<Segment> segments) { /*  .        .   - . */ final G visibilityGraph = new G(getVertices(segments)); /*     */ for (final Vertex v : visibilityGraph.getVertices()) { /*       */ final Set<Vertex> visibleVertices = getVisibleVertices(v, segments); /*       */ for (final Vertex w : visibleVertices) visibilityGraph.addEdge(v, w); } return visibilityGraph; }

BuildVisibilityGraph फ़ंक्शन इनपुट के रूप में कई खंडों - बाधा पॉलीगन्स के किनारों - को स्वीकार करता है और निर्मित दृश्यता ग्राफ को लौटाता है। यहाँ स्पष्टीकरण, यह मुझे लगता है, आवश्यक नहीं हैं। GetV अदृश्यVertices फ़ंक्शन के छद्मकोड पर विचार करें।

सभी दृश्यमान कोने की सूची प्राप्त करना

 public final Set<Vertex> getVisibleVertices(final Vertex v, final Set<Segment> segments) { /*    ( )  ,   pw ( w -  )   ,    v */ final SortedSet<Vertex> sortedVertices = sortSegmentsVertices(v, segments); /*  I -  ,   v.   ,                   */ final BST<Segment> intersectedSegments = new BST<Segment>(v, segments); /*     */ final Set<Vertex> visibleVertices = new HashSet<Vertex>(); /*     */ for (final Vertex w : sortedVertices) { if (isVertexVisible(v, w, intersectedSegments)) visibleVertices.add(w); /*      ,   w       ( vw),  ,    w */ intersectedSegments.add(getIncidentSegments(v, w, Position.RightOf)); /*      ,   w       ( vw),  ,    w */ intersecedSegments.remove(getIncidentSegments(v, w, Position.LeftOf)); } return visibleVertices; }

तो, सबसे पहले, वर्टिस w sort W को रे vw और v से गुजरने वाले वर्टिकल हाफ-एक्सिस के बीच के कोण से सॉर्ट किया जाता है। यह छँटाई O (nlog (n)) में की जाती है, उदाहरण के लिए, मर्ज छँटाई। फिर, दृश्यमान आवृत्तियों के सेट को प्रारंभ किया जाता है (डिफ़ॉल्ट रूप से, ऐसा सेट खाली होता है)। अगला विमान को स्वीप करना शुरू करता है। उनमें से प्रत्येक के लिए कोने की छंटाई के क्रम में, एक चेक बनाया गया है: शीर्ष पर v से दिखाई देने वाली वर्टेक्स है। चूंकि इस चेक का मतलब है कि चौराहे हैं जो एक संतुलित पेड़ में संग्रहीत हैं, इसे ओ (लॉग (एन)) में किया जा सकता है। यदि शीर्ष दृश्यमान है, तो आपको इसे दृश्यमान रेखाओं की सूची में जोड़ना होगा। और अंत में, वर्टेक्स की दृश्यता की परवाह किए बिना, स्वीपिंग लाइन की स्थिति को बदलना आवश्यक है। ऐसा करने के लिए, वर्तमान शीर्ष w के लिए, वर्तमान चौराहों की सूची से सभी किनारों (खंडों) को हटाना आवश्यक है जो इस शीर्ष पर समाप्त होते हैं (पंक्ति vw के बाईं ओर) और इसमें शुरू होने वाले सभी किनारों (खंडों) को जोड़ें (पंक्ति vw के दाईं ओर स्थित) ।
आंकड़ों पर गौर करें 8-10:

आंकड़े 8-10

चित्रा 8. चरण 1. व्यापक लाइन की स्थिति का अद्यतन करना।

चित्र 9. चरण 2. स्वीपिंग लाइन की स्थिति का अद्यतन करना।

चित्रा 10. चरण 3. व्यापक लाइन की स्थिति का अद्यतन करना।

इसलिए, पहले चरण में (रे vw ₁ ), दो खंडों w ₁ w ₅ और w ₁ w ₂ को पेड़ में जोड़ा जाता है, क्योंकि वे किरण vw ₁ के दाईं ओर स्थित होते हैं। नारंगी में स्वेप्ट लाइन की स्थिति चिह्नित है।
दूसरे चरण में (सूची में दूसरा शीर्ष शीर्ष w _{3 है} ), स्थिति में दो और किनारों को जोड़ा गया है: w ₃ w ₂ और w ₃ w ₄ । अब 4 पसलियां स्थिति में हैं। अंत में, तीसरे चरण में (वर्टेक्स डब्ल्यू ₂ ), 2 किनारों को स्थिति से हटा दिया जाता है: डब्ल्यू ₃ डब्ल्यू ₂ और डब्ल्यू ₁ डब्ल्यू ₂ ।

अंत में, आपको शीर्ष दृश्यता जांच फ़ंक्शन को देखना चाहिए।

सत्यापन दृश्यता समारोह

 public final boolean isVisible(final Vertex v, final Vertex w, final BST<Vertex> intersections) { final Segment currentSegment = new Segment(v, w); /*  vw    ,   w,    */ if (intersects(currentSegment, w.getSegments()) return false; /*   ( )    vw. */ if (currentSegment.contains(w.getPreviousVertex())) { /*   ,  ,   */ if (!v.getPreviousVertex().isVisible()) return false; return !intersections.hasIntersectionsWith(new Segment(w.getPrevious(), w)); } /*         (    vw    ) */ return intersections.intersectWithLeftMost(currentSegment); }

इस फ़ंक्शन को केवल सही लौटने की आवश्यकता है यदि शीर्ष पर w शीर्ष से दिखाई दे और अन्यथा झूठी है। ऐसा करने के लिए, बस खंड vw की लंबाई और बिंदु v से चौराहे की दूरी पेड़ (सबसे बाईं शीट) में संग्रहीत निकटतम खंड के साथ तुलना करें। लेकिन यहाँ कई सीमाएँ हैं:

रे vw अंतड़ियों को घटना को v या w से काटता है
किरण उस किनारे से मेल खाती है जिस पर अन्य कोने हैं।

इस प्रकार, दृश्यता चेक फ़ंक्शन ओ (लॉग (एन)) के लिए सबसे खराब स्थिति में काम करता है, क्योंकि यह एक संतुलित पेड़ में खोज का उपयोग करता है। शेष संचालन निरंतर समय में किया जाता है।

सड़क के नक्शे

एक अन्य मार्ग नियोजन विधि रोडमैप का उपयोग कर रही है। एक truism की तरह लगता है, है ना? इस लेख के ढांचे में, मैं संक्षेप में इसके सार के बारे में बात करूंगा (क्योंकि लेख पहले से ही काफी लंबा है), अगर किसी को दिलचस्पी है, तो शायद मैं बाद में एक और प्रकाशन लिखूंगा। So.

हम एक आयत का निर्माण करते हैं, जिसके अंदर सभी बाधा बहुभुज होते हैं (चित्र 11)। सेगमेंट के सेट पर विचार करें - बाधाओं के किनारों और इसके लिए एक ट्रैपेज़ॉइडल मैप का निर्माण करें (चित्र 12), और फिर परिणामी मैप से सभी बाधाओं (चित्रा 13) के अंदर पड़े ट्रैपोज़ाइड को हटा दें। एक नक्शा बनाने में O (nlog (n)) समय लगता है, जहाँ n बाधा संख्याओं की कुल संख्या है। ट्रेपोजॉइड टी को हटाने के लिए यह तय करने के लिए, यह किनारे शीर्ष (टी) को लेने के लिए पर्याप्त है और यह जांचें कि क्या एक बाधा इसके ऊपर या नीचे स्थित है, जिसकी सीमा में यह किनारा है। इस प्रकार, सभी अतिरिक्त ट्रेपोज़ोइड को हटाने के लिए O (n) समय लगता है।
यदि प्रारंभ और अंत बिंदु एक ही ट्रेपोज़ॉइड के अंदर हैं, तो आप पहले बिंदु से दूसरे तक सीधी रेखा में जा सकते हैं। यदि ये बिंदु अलग-अलग ट्रेपोज़िड्स में झूठ बोलते हैं, तो पथ कई ट्रेपोज़ोइड को पार करेगा, और, शायद, उनमें से कुछ में हमें मोड़ बनाने होंगे।
हम एक रोड मैप बनाते हैं - ग्राफ जी। जी के कोने बाधाओं के शीर्ष और ट्रेपोज़ॉइड के मिडपॉइंट के माध्यम से खींची गई ऊर्ध्वाधर लाइनों के खंडों के मध्य बिंदु होंगे। ग्राफ जी के दो कोने एक किनारे से जुड़े हुए हैं यदि और केवल अगर उनमें से एक कुछ ट्रेपोज़ॉइड के बीच का है और दूसरा इस ट्रेपोज़ॉइड के ऊर्ध्वाधर किनारे पर स्थित है। ग्राफ G का निर्माण O (n) समय में एक ट्रेपोजॉइडल मानचित्र से किया जा सकता है। ध्यान दें कि ग्राफ G एक सपाट ग्राफ है।
बिंदु s से बिंदु f तक का मार्ग खोजने के लिए, हम सबसे पहले यह निर्धारित करते हैं कि किस समलंब में s और f हैं। यदि वे एक ट्रेपोज़ॉइड के अंदर मिले, तो सबसे छोटा रास्ता एक सीधी रेखा है। अन्यथा, हम बिंदु एस से ट्रेपेज़ॉइड के मध्य तक एक सीधी रेखा में चलते हैं, फिर ग्राफ के किनारों के साथ ट्रैपेज़ॉइड के मध्य में ले जाएँ जिसमें एफ (आप चौड़ाई-प्रथम खोज का उपयोग कर सकते हैं), और अंत में ट्रैपोज़ॉइड के मध्य से एक सीधी रेखा में जाएँ (आंकड़ा) 14)। चूंकि ट्रैपेज़ॉइडल मैप में n में ट्रेपेज़ोइड्स रैखिक की संख्या होती है, और बाधाओं के कोने के माध्यम से खींची गई ऊर्ध्वाधर लाइनों के खंडों की संख्या भी n में रैखिक होती है, ग्राफ G में O (n) कोने होते हैं, और चूंकि यह प्लानेर है, किनारों की संख्या भी O (है) एन)। इसलिए, जी पर एक चौड़ाई-पहली खोज ओ (एन) के समय में की जा सकती है। चूँकि O (log (n)) को एक ट्रेपेज़ॉइडल मानचित्र में एक बिंदु को स्थानीय करने के लिए आवश्यक है, इसलिए बिंदु O से बिंदु f तक का मार्ग बनाने के लिए O (n) की आवश्यकता होती है। लेकिन रोडमैप का उपयोग करके बनाए गए मार्ग इष्टतम नहीं होंगे।


चित्र 11. एक संलग्न आयत का निर्माण	चित्रा 12. ट्रैपेज़ॉइडल मानचित्र	चित्रा 13. कम ट्रेपोज़ाइडल मानचित्र

चित्र 14. निर्मित सड़क का नक्शा

उप-कार्य

उत्तल पतवार निर्माण

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

भोली एल्गोरिथ्म। O (n ⁴ ) के लिए काम करता है। प्रत्येक "चरम नहीं" के लिए (अर्थात, सेट का ऐसा बिंदु जिसके माध्यम से आप एक सीधी रेखा खींच सकते हैं जिसके संबंध में पूरा सेट एक तरफ होगा), निम्नलिखित परीक्षण किया जाता है। यदि यह सेट के बिंदुओं से प्राप्त कम से कम एक त्रिकोण से संबंधित है, तो यह उत्तल पतवार का एक बिंदु है। एन बिंदुओं के एक सेट में, एन ³ त्रिकोण हैं। इसलिए, एन बिंदुओं में से प्रत्येक के लिए, आपको एन ³ चेक करने की आवश्यकता है।
थोड़ा कम भोली एल्गोरिथ्म। ओ (एन ³ )। एक पूरा ग्राफ कई नोड्स के साथ बनाया गया है - मूल सेट के अंक। प्रत्येक किनारे (जिनमें से N ² ) के लिए, शेष N-2 बिंदुओं की जाँच की जाती है। क्या वे सभी किसी दिए गए पसली के एक तरफ झूठ बोलते हैं। यदि ऐसा है, तो किनारे उत्तल पतवार का है।
जार्विस एल्गोरिथ्म। O (n ² ) के लिए काम करता है। एक विमान पर बहुत सारे बिंदुओं की कल्पना करें। उनमें से सबसे बाईं ओर चुनें (यह हमेशा किया जा सकता है (यदि कई हैं, तो कोई भी बाएं के बीच में है), यह स्पष्ट रूप से उत्तल पतवार का एक बिंदु है), और फिर उपहार के रूप में सेट को "लपेटें"। अन्य सभी बिंदुओं में, हम एक को चुनते हैं जिसमें सबसे छोटा ध्रुवीय कोण होता है (दृश्यता ग्राफ के निर्माण के साथ सादृश्य द्वारा, हम इसे एक किरण के साथ स्पॉट करते हैं)
ग्राहम एल्गोरिथम। O (nlog (n)) के लिए काम करता है। मैंने एक विवरण प्रदान नहीं किया (जैसा कि आप जानते हैं, एल्गोरिथ्म जितना तेज़ होगा, उतना ही अधिक स्क्रिबल) - Google

लाइन चौराहा

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

निष्कर्ष

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

एक हजार शब्दों के बजाय

संदर्भ

अनुप्रस्थ गणित विभाग, सेंट पीटर्सबर्ग स्टेट पेडागोगिकल यूनिवर्सिटी में रेखीय बीजगणित, उच्च गणित, असतत गणित, एल्गोरिदम के सिद्धांत और कम्प्यूटेशनल ज्यामिति में व्याख्यान पाठ्यक्रम
एम। डी। बर्ग, ओ। चेयोंग, एम। क्रेवेल्ड, एम। ओवरमर्स कम्प्यूटेशनल ज्यामिति, 2008
जेई गुडमैन, जे। ओ'रोरके असतत और कम्प्यूटेशनल ज्यामिति, 2004
जावा में वेंटा पुस्तकालय कार्यान्वयन

मोशन प्लानिंग: दृश्यता का ग्राफ, रोडमैप

समस्या का बयान

निर्णय

इष्टतम तरीका है

चित्रा 1. पथ टी पर बिंदु पी

चित्रा 2. 2.-p का पड़ोस

चित्रा 3. सबसे छोटा रास्ता कॉर्ड

चित्रा 4. खाली स्थान में पड़े हुए मार्ग के शीर्ष का neighborhood-पड़ोस

चित्रा 5. किनारे पर पड़े हुए पथ के शीर्ष का neighborhood-पड़ोस