पॉलीगॉन-पॉलीगॉन-चौराहे विशेष मामले में विफल रहता है - एल्गोरिदम, ज्यामिति, बहुभुज, कम्प्यूटेशनल-ज्यामिति

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

लेकिन अगर मैं इस मामले को देखता हूं:

कोई खंड-चौराहा नहीं है। लेकिन स्पष्ट रूप से दोनों बहुभुज प्रतिच्छेद करते हैं।

मैं भोली एल्गोरिथ्म का उपयोग किए बिना इस मामले का पता कैसे लगा सकता हूं जो दूसरे बहुभुज में प्रत्येक बहुभुज के प्रत्येक बिंदु के लिए बिंदु-इन-बहुभुज की जांच करता है और इसलिए ओ (एम * एन) में चलता है।

उत्तर:

संकेत:

विशेष मामलों की हैंडलिंग जैसे कि एक शीर्ष परएक किनारे या दो अतिव्यापी किनारों एक असहज विषय है क्योंकि विन्यास विविध हैं और मामले दूरबीन कर सकते हैं (कई संपीड़ित किनारों के बारे में सोचें जो ओवरलैप होते हैं)।

मेरी सबसे अच्छी सलाह है कि सुसंगतता लागू करनाहर वर्टेक्स को अंदर या बाहर के राज्य को सौंपना (अन्य बहुभुज)। फिर जब आप अन्य बहुभुज के साथ एक किनारे को काटते हैं, तो चौराहों की संख्या की समता को समापन बिंदु राज्य (उसी राज्य => चौराहों की संख्या) में परिवर्तन से मेल खाना चाहिए।

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

मामले में एक विसंगति प्रकट होती है (संख्या की समानता)चौराहों (राज्य के परिवर्तन से मेल नहीं खाते), आपको इसे ठीक करना चाहिए, या तो एक चौराहे का त्याग करके या एक (या किसी अन्य नियम को जो आपको उपयुक्त लगता है) की नकल करके।

उदाहरण:

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

नीचे दी गई ब्लैक आउटलाइन यूनियन बहुभुज का प्रतिनिधित्व करती है जो राज्यों के इस असाइनमेंट के परिणामस्वरूप होगी।