एक ओ (एन) एल्गोरिदम का पता लगाने के लिए गणना करता है कि एक रेखा उत्तल बहुभुज को छेड़छाड़ करती है तो यह जांचने के लिए होता है कि बहुभुज के किसी किनारे रेखा को छेड़छाड़ करते हैं, और देखें कि चौराहे की संख्या अजीब या यहां तक कि है।यदि कोई रेखा उत्तल बहुभुज
क्या कोई असंवेदनशील रूप से तेज़ एल्गोरिदम है, उदा। एक ओ (लॉग एन) एक?
lhf का उत्तर सही है। यहां एक संस्करण है जो उसके साथ समस्या को ठीक करना चाहिए।
बहुभुज को vcl, v1, ... vn को घुमावदार क्रम में लंबवत करने दें। अंक x0 और x1 लाइन पर होने दें।
दो चीजें नोट करें: सबसे पहले, दो पंक्तियों के चौराहे को ढूंढना (और इसके अस्तित्व को निर्धारित करना) निरंतर समय में किया जा सकता है। दूसरा, यह निर्धारित करना कि एक बिंदु बाईं ओर या रेखा के दाईं ओर एक बिंदु है, निरंतर समय में किया जा सकता है।
हम ओ (लॉग एन) एल्गोरिदम प्राप्त करने के लिए lhf के समान मूल विचार का पालन करेंगे। मूल मामले तब होते हैं जब बहुभुज में 2 या 3 शिखर होते हैं। इन दोनों को निरंतर समय में संभाला जा सकता है।
निर्धारित करें कि रेखा (v0, v (n/2)) रेखा (x0, x1) को छेड़छाड़ करती है या नहीं।
केस 1: वे अंतर नहीं करते हैं।
इस मामले में जिस लाइन में हम रुचि रखते हैं वह बहुभुज को विभाजित करने वाली रेखा के बाएं या दाएं ओर है, और इसलिए हम बहुभुज के उस आधे हिस्से में पुन: कार्य कर सकते हैं। विशेष रूप से, यदि x0 बाईं ओर है (v0, v (n/2)) तो दाएं "आधा", {v0, v1, ... v (n/2)} में सभी शीर्षक एक ही तरफ हैं (x0, x1) और इसलिए हम जानते हैं कि बहुभुज के उस "आधे" में कोई छेद नहीं है।
केस 2: वे छेड़छाड़ करते हैं।
यह मामला थोड़ा सा चालक है, लेकिन हम अभी भी अंतराल को बहुभुज के एक "आधे" तक सीमित कर सकते हैं।
प्रकरण 2.1:: वहाँ 3 subcases हैं चौराहे अंक V0 और वी (एन/2)
हम किया जाता है के बीच है। रेखा बहुभुज को छेड़छाड़ करती है।
प्रकरण 2.2: चौराहे (V0 के पक्ष में जो है, बहुभुज के बाहर) V0 के करीब है
निर्धारित करें यदि लाइन (x0, x 1) लाइन के साथ काटती है (V0, v1)।
यदि ऐसा नहीं होता है तो हम बहुभुज को अंतर नहीं करते हैं।
यदि ऐसा होता है, तो चौराहे पाएं, पी। यदि पी लाइन के दाईं ओर है (v0, v (n/2)) तो बहुभुज के सही "आधा", {v0, v1, ..., v (n/2)} में पुन: कार्य करें, अन्यथा रिकर्स बाईं ओर "आधा" {v0, v (n/2), ... vn}।
इस मामले में मूल विचार यह है कि बहुभुज में सभी बिंदु रेखा के एक तरफ (v0, v1) हैं। यदि (x0, x1) इसके चौराहे के एक तरफ (v0, v (n/2)) (v0, v1) से अलग हो रहा है (v0, v (n/2))। हम जानते हैं कि उस तरफ बहुभुज के साथ कोई अंतर नहीं हो सकता है।
प्रकरण 2.3: चौराहे वी के करीब है (एन/2)
इस मामले में केस 2.2 की तरह ही नियंत्रित किया जाता है, लेकिन वी के उचित पड़ोसी (एन/2) का उपयोग कर।
हम कर रहे हैं। प्रत्येक स्तर के लिए, इसके लिए दो पंक्ति चौराहे की आवश्यकता होती है, एक बाएं-दाएं चेक, और यह निर्धारित करना कि रेखा पर एक बिंदु कहां है। प्रत्येक रिकर्सन 2 से लंबवत की संख्या को विभाजित करता है (तकनीकी रूप से उन्हें कम से कम 4/3 तक विभाजित करता है)। और इसलिए हमें ओ (लॉग एन) का रनटाइम मिलता है।
बाउंडिंग बॉक्स उपयोगी साबित हो सकते हैं।
याद रखें कि एक एफ़िन स्पेस का एक उत्तल भाग अपने सभी लिफाफे हाइपरप्लेन का अंतर है: आप लिफाफे के सबसेट के केवल छेड़छाड़ पर विचार करके अपने बहुभुज का अनुमान लगा सकते हैं ("बाध्यकारी उत्तल बहुभुज" पढ़ें) हाइपरप्लेन्स, इस अनुमान के साथ आपकी रेखा के चौराहे के लिए परीक्षण, और यदि आवश्यक हो तो परिशोधित करें।
यदि आप कम संख्या में चौराहे की अपेक्षा करते हैं तो यह सब बेहतर काम करता है।
आपको बस एक बिंदु ए को खोजने की जरूरत है जो रेखा के बाईं ओर है और दूसरी तरफ दाईं तरफ है। शेष प्रश्न यह है कि उन बिंदुओं को जल्दी से कैसे ढूंढें।
उत्तल पोलिगॉन से यादृच्छिक दो बिंदु ए और बी लें।
द्वारा किया जा सकता उन दो दूर का अंक अपनी लाइन के विभिन्न पक्ष पर हैं, लाइन poligon काटती है, अन्यथा यह
नहीं है वैसे भी आप ओ (लॉग एन) में वास्तविक चौराहे बिंदु भी पा सकते हैं।
एल्गोरिदम अमान्य है। 1) शिखर एबी और बीए के अनुक्रम टर्नरी खोज के लिए मान्य नहीं हो सकते हैं। 2) इन polylines पर एल से अधिकतम दूरी के साथ अंक होने की गारंटी नहीं है कि अंक जांच लाइन के विपरीत पक्षों पर हैं। यहां तक कि जब रेखा बहुभुज को पार करती है। –
या तो दूरी पूर्ण नहीं होनी चाहिए (ताकि एक तरफ नकारात्मक हो, अन्य सकारात्मक पर), या एक तरफ एल के माध्यम से ए और बी के माध्यम से दूसरे के माध्यम से चला जाता है। – Sarmun
गैर-पूर्ण दूरी मदद करेगा, लेकिन सभी मामलों में नहीं। Http://jurajblaho.wz.cz/path2816.png देखें। सीडब्ल्यू ऑर्डर में ए-> बी टर्नरी सर्च के लिए मान्य नहीं है क्योंकि यह बढ़ रहा है, घट रहा है और अंत में बढ़ रहा है। –
मुझे लगता है कि this article एक स्पष्ट ओ (लॉग एन) समाधान देता है। दी गई रेखा के लंबवत दिशा में चरम सीमाएं पाएं।
कृपया, पॉलीगॉन के बाएं/दाएं आधे हिस्से को स्पष्ट करें। हो सकता है कि शब्दों का उपयोग करना बेहतर होगा v0-> vk या vk-> v0 मानते हुए ऑर्डर सीसीडब्ल्यू है। –
हर बार जब मैंने बाएं/दाएं आधा कहा, तो मैंने स्पष्ट किया, मैंने उस आधा में शिखर सूचीबद्ध किए। विशेष रूप से, बायां आधा वह शिखर होता है जो रेखा के दाईं ओर नहीं है (v0, v (n/2)), {v0, v1, ..., v (n/2)}। मैं इस शब्द का उपयोग दाईं ओर नहीं करता क्योंकि यह लाइन के बाईं ओर रेखाओं के साथ-साथ रेखा पर भी है। –
+1 जब तक मुझे एक अनुबंध उदाहरण नहीं मिलता है। नोट: मुझे लगता है कि स्पष्टीकरण गलत है। सीसीडब्ल्यू आदेश में सही आधा v0-> v (n/2) है। –