खंड-बहुभुज चौराहे

Question

नमस्ते,

मैं चाहूँगा एक बहुभुज अगर एक खंड केवल 'छू लेती है' पता लगाने के लिए या इसे पार करते हैं।

चित्रा

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

Answer 1

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

Answer 2

सामान्यीकरण, एक चौराहे कई बिंदुओं शामिल हो सकती है। उदाहरण के लिए, http://cagd.cs.byu.edu/~557/text/ch7.pdf देखें जो चर्चा करता है कि प्लानर वक्र कैसे छेड़छाड़ करते हैं, और कहते हैं कि टेंगेंट वक्र दो बिंदुओं पर "ठीक से गिना जाता है" पर अंतर होता है, जो प्रति-सहज है। एक चक्करदार रेखा के साथ एक उत्तल बहुभुज के मामले में, चौराहे के दो बिंदु "ठीक से गिना जाता है?" आपके मामले में, दो बिंदुओं के साथ दो चौराहे हैं?

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