सुरुचिपूर्ण "वाम की" परीक्षण पॉलीलाइन

Question

के लिए दिया गया है:

• (एक्स, वाई) के समन्वय, एक वाहन की स्थिति है।
• (एक्स, वाई) के ऐरे, जो पॉलीलाइन में शिखर हैं। ध्यान दें कि पॉलीलाइन में केवल सीधी सेगमेंट होते हैं, कोई चाप नहीं।

मुझे क्या करना चाहते हैं:

• गणना करने के लिए है कि क्या वाहन बाईं ओर या पॉलीलाइन के अधिकार के लिए है (या शीर्ष पर, बिल्कुल)।

मेरे दृष्टिकोण: सभी लाइन खंडों के

• दोहराएं, और प्रत्येक खंड के लिए दूरी की गणना। फिर निकटतम सेगमेंट के लिए आप एक साधारण बाएं-टेस्ट करते हैं (उदाहरण के लिए here समझाया गया है)।

संभावित मुद्दों:

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

मेरा प्रश्न:

• मैं कैसे सुंदर ढंग से, लेकिन ज्यादातर कुशलतापूर्वक देखभाल इस विशिष्ट स्थिति के ले जा सकते हैं?

मेरे ठीक अब तक: दोनों खंडों कि खंड पर एक बिंदु, शिखर बिंदु से शुरू करने के लिए

• कंप्यूट।
• यूक्लिडियन दूरी
• का उपयोग करके उस सेगमेंट को रखें, जिसके लिए गणना बिंदु निकटतम है।

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

मौजूदा codebase सी ++ में है, इसलिए यदि आप किसी विशिष्ट भाषा में लिखना चाहते हैं, सी ++ मेरी प्राथमिकता है। धन्यवाद!

[संपादित करें] मैं मेरी ठीक, एक सीधा बिंदु से एक समानांतर बात करने के लिए, बदल के रूप में मुझे लगता है कि यह आसान है रेखा खंड की गणना जावक सामान्य से पालन करने के लिए।

Answer 1

यह विषय इतने लंबे समय तक निष्क्रिय रहा है कि मुझे विश्वास है कि यह मर चुका है। मेरे पास एक समाधान है हालांकि।

हालांकि, परीक्षण के बाएँ निकलेगा सही यदि प्रथम खंड निकटतम खंड के रूप में चुना है, और छोड़ दिया अन्यथा।

आपने थोड़ा अस्पष्ट भाषा का उपयोग किया है। मैं पॉलीलाइन और क्वाड्रंट में लाइन सेगमेंट के बारे में बोलने के लिए सेगमेंट का उपयोग करने जा रहा हूं। तो आपके मामले में, आपके पास एक लाल क्वाड्रंट होगा जो एक सेगमेंट और दूसरे के बाईं ओर स्थित है।

यदि बाएं परीक्षण में विभिन्न सेगमेंट के लिए अलग-अलग उत्तर मिलते हैं, तो आपको सेगमेंट पर परीक्षण फिर से करना चाहिए। आपके मामले में, आप होगा:

• वृत्त का चतुर्थ भाग प्रथम खंड
• वृत्त का चतुर्थ भाग दूसरे खंड

दोनों क्षेत्रों पर जहां असहमत के बाईं ओर है के दाईं तरफ है वृत्त का चतुर्थ भाग झूठ है, तो आप दो और बहुविकल्पी परीक्षण कार्य करें:

• दूसरे खंड प्रथम खंड
• देवदार के दाईं तरफ है सेंट खंड दूसरा खंड

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

(मैं लगभग आप दो बहुविकल्पी परीक्षण का केवल एक साथ कर सकते हैं यकीन है, मैं दोनों में डाल दिया है स्पष्टता के लिए)

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

Answer 2

बस एक त्वरित विचार: यह, अपनी पॉलीलाइन के आखिरी और पहले सिरे कनेक्ट करने के लिए संभव हो जाएगा इतना है कि यह एक बहुभुज बन जाएगा? फिर आप एक साधारण अंदर/बाहर की जांच कर सकते हैं यह निर्धारित कर सकते हैं कि वाहन लाइन के बाएं/दाएं है (यह संभोग बहुभुज की दिशा पर निर्भर करता है)।

हालांकि, इस विधि मान है कि बहुभुज अभी भी स्वयं का प्रतिच्छेदन पिछले और पहले सिरे से जोड़ने के बाद नहीं है।

Answer 3

अनंतता = एम दें जहां एम काफी बड़ा है। आप इस बात पर विचार कर सकते हैं कि सब कुछ वर्ग [-एम, एम] एक्स [-एम, एम] में है, वर्ग को अपनी पॉलीलाइन के साथ विभाजित करें और अब आपके पास दो बहुभुज हैं। फिर जांच करें कि क्या कार किसी दिए गए बहुभुज में है, कोणों के साथ बहुत आसानी से किया जा सकता है।

मैं विचार है कि अपने पहले बिंदु और अपने अंतिम बिंदु वहाँ निर्देशांक में एम की है। आपको पॉलीगॉन रखने के लिए इनमें से कुछ बिंदुओं को जोड़ने की आवश्यकता हो सकती है: (-एम, -एम), (एम, -एम), (एम, एम) और (-एम, एम)।

पॉलीलाइन के बाईं ओर एक बहुभुज होने के बाद, ओईजी कोणों को योग करें जहां ओ एक निश्चित बिंदु है, सी कार है और पी बहुभुज का एक बिंदु है। यदि योग 0 है तो कार बहुभुज के बाहर है, अन्यथा यह अंदर है।

Answer 4

यह कम्प्यूटेशनल ज्यामिति से समस्या का एक मानक प्रकार है। चूंकि आप यह जांचने के लिए देख रहे हैं कि किसी बिंदु (x0, y0) को किसी दिए गए सतह (आपकी पॉलीलाइन) से बचाया गया है, तो आपको यह पहचानने की आवश्यकता है कि किस सेगमेंट को इसकी ऊंचाई से परीक्षण करना है। ऐसा करने का एक आसान तरीका प्रत्येक सेगमेंट के निचले बिंदु का पेड़ बनाना होगा, और उसमें टेस्ट पॉइंट के पूर्ववर्ती के लिए खोज करना होगा। एक बार आपके पास उस सेगमेंट हो जाने के बाद, आप सीधे अपने बाएं-टेस्ट टेस्ट कर सकते हैं: यदि यह दोनों एंडपॉइंट्स के बावजूद है, या उचित पक्ष पर उनके बीच है, तो आप सच हो जाते हैं।

मैं यहाँ यह सोचते हैं रहा हूँ आप गारंटी देते हैं कि कि अपनी पॉलीलाइन के ऊर्ध्वाधर हद तक, जहां आप अपनी क्वेरी बिंदु मिल सकती है से अधिक है, और लाइन में ही खड़ी ओवरलैप नहीं है। बाद की धारणा काफी खराब हो सकती है। ओपी की टिप्पणी के जवाब में

विस्तार:

नोट है कि प्रश्न में कोण उदाहरण के विपरीत पहली धारणा - पॉलीलाइन खोज बिंदु के ऊंचाई तक पहुंच नहीं है।

मेरी विधि को अवधारणाबद्ध करने का एक तरीका है अपने सेगमेंट को लंबवत क्रमबद्ध करना, और उसके बाद सेगमेंट के खिलाफ अपने बिंदु के वाई-समन्वय की तुलना करना, जब तक कि आपका बिंदु निचले अंतराल से ऊपर न हो और उच्च अंतराल से नीचे न हो। फिर, दिए गए वाई पर एक्स-इंटरसेप्ट को समझने के लिए सेगमेंट के एंडपॉइंट्स का उपयोग करें। यदि बिंदु में कम एक्स-कोऑर्डिनेट है, तो यह बाईं ओर है, और यदि इसमें अधिक एक्स-समन्वय है, तो यह सही है।

वहाँ कोई वास्तविक कार्यान्वयन में इस व्याख्या पर सुधार करने के लिए दो तरीके, जिनमें से एक मैं बारे में उल्लेख किया है:

1. एक संतुलित खोज ट्री का उपयोग करें के बजाय एक क्रमबद्ध सूची के माध्यम से पुनरावृत्ति के अधिकार के खंड को खोजने के लिए, करने के लिए O(n) से O(log n)
2. समय को पॉलीलाइन के चौराहे और क्षैतिज रेखा y = y0 खोज बिंदु के माध्यम से खोज को दोबारा शुरू करें। फिर बस खोज बिंदु के खिलाफ छेड़छाड़ के एक्स मान की तुलना करें।