बहुभुज

Question

के अंदर एक धुरी-संरेखित आयताकार ढूँढना मैं एक (एग्री जरूरी नहीं) बहुभुज के अंदर अक्ष-संरेखित आयत को खोजने के लिए एक अच्छा एल्गोरिदम ढूंढ रहा हूं। एक अधिकतम आयत अच्छा होगा, लेकिन आवश्यक नहीं है - कोई भी एल्गोरिदम जो "काफी अच्छा" आयताकार पा सकता है ठीक होगा।

बहुभुज में भी छेद हो सकते हैं, लेकिन एल्गोरिदम के लिए कोई संकेतक जो केवल उत्तल या साधारण बहुभुज के लिए काम करते हैं, भी सहायक होंगे।

मेरे कार्यान्वयन में, पक्षों के लिए छेड़छाड़ परीक्षण काफी सस्ते है, लेकिन "बहुभुज में बिंदु" परीक्षण महंगा हैं, इसलिए आदर्श को कम किया जाना चाहिए।

Answer 1

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

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

स्पष्ट कारणों के लिए, यह काफी धीमी गति से और अयथार्थ है, असजीला का उल्लेख नहीं करने के लिए :)

Answer 2

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
उत्तल के लिए एक एल्गोरिथ्म है, संदर्भ एक नज़र लायक हो सकता है।
यह सुनिश्चित नहीं है कि इसे गैर-उत्तलता तक बढ़ाया जा सकता है या नहीं।

Answer 3

एक समाधान अवतल बहुभुज को उत्तल खंडों में विभाजित करना है और फिर कोबबल के लिंक का उपयोग करना है।

चूंकि आपके पास वास्तव में दो अलग-अलग मौलिक समस्याएं हैं, क्या आपने हिट टेस्ट समस्या के अन्य विकल्पों को माना है, जैसे कि बीएसपी पेड़ का उपयोग करना? आप पॉली पर ग्रिड डालने और प्रत्येक ग्रिड स्क्वायर के लिए बीएसपी पेड़ का निर्माण करके इसे आगे बढ़ा सकते हैं। या प्रत्येक पत्ता में सबसे किनारे पर एक केडी-पेड़?

संपादित करें: मैं (बोरियत से बाहर, भले ही वह किसी को भी किसी भी काम का हो सकता) केडी-पेड़ पर ellaborate होगी:

1. :

   केडी के पेड़ों निम्नलिखित गुण होते हैं वे बाइनरी

2. प्रत्येक गैर-पत्ता नोड एक अक्ष के लंबवत एक अक्ष के साथ अंतरिक्ष को विभाजित करता है, प्रति बच्चे एक तरफ। जैसे रूट x < x0 और x> = x0
3. पेड़ के स्तर अलग-अलग अक्षों के साथ विभाजित हो जाते हैं, उदाहरण के लिए स्तर 0 (रूट) एक्स करने के लिए खड़ा विभाजन स्तर 1 -> वाई, आदि

मारा पता लगाने बहुभुज के लिए इसका उपयोग करने के लिए, इस प्रकार के पेड़ का निर्माण:

1. एक शीर्ष उठाओ विभाजित करने के लिए साथ। (एक संतुलित पेड़ के लिए कहीं भी मध्य के करीब)।
2. विभाजन के दोनों तरफ के लिए दो सेटों में विभाजित करें। उपरोक्त vertex या तो सेट में नहीं जाता है।
3. सेट में किनारों को भी रखें। स्प्लिट लाइन को छेड़छाड़ करने वाला कोई भी किनारा दोनों सेटों में जाता है।
4. उपरोक्त समूहों से बच्चों को दोबारा निर्माण करें।

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

1. उस बिंदु को ढूंढें जिसमें बिंदु गिरता है।
2. यदि पत्ते में किनारे हैं, तो इसकी तुलना करें। यदि नहीं, तो यह स्पष्ट होना चाहिए कि बिंदु अंदर या बाहर है (पेड़ का निर्माण करते समय इस तरह की पत्तियों में इस जानकारी को स्टोर करें)।

Answer 4

कान क्लिपिंग का उपयोग करने के बारे में क्या? आप प्रत्येक त्रिभुज में अधिकतम अक्ष-संरेखित आयताकार पा सकते हैं। फिर आप त्रिभुज में शामिल होने और अपने आयतों को दोबारा बदलने की कोशिश कर सकते हैं।