मेरे पास एक System.Windows.Shapes.Polygon ऑब्जेक्ट है, जिसका लेआउट पूरी तरह से पॉइंट्स की श्रृंखला द्वारा निर्धारित किया जाता है। मुझे यह निर्धारित करने की ज़रूरत है कि क्या यह बहुभुज स्वयं छेड़छाड़ कर रहा है; यानी, यदि बहुभुज के किसी भी पक्ष किसी अन्य पक्ष को किसी बिंदु पर छेड़छाड़ करता है जो एक चरम नहीं है। क्या इसकी गणना करने का कोई आसान/तेज़ तरीका है?जांचें कि क्या पॉलीगॉन स्वयं छेड़छाड़ कर रहा है
आसान, धीमी गति, कम स्मृति पदचिह्न: सभी अन्य के खिलाफ प्रत्येक खंड की तुलना और चौराहों के लिए जाँच करें। जटिलता ओ (एन)।
थोड़ा तेज, मध्यम स्मृति पदचिह्न (संशोधित ऊपर के संस्करण): स्थानिक "बकेट" में दुकान किनारों, तो प्रति-बाल्टी आधार पर एल्गोरिथ्म ऊपर प्रदर्शन करते हैं। जटिलता ओ (एन/मीटर)एम बाल्टी (समान वितरण मानते हुए) के लिए।
फास्ट & उच्च स्मृति पदचिह्न: बाल्टी में किनारों विभाजित करने के लिए एक स्थानिक हैश समारोह का उपयोग करें। टक्कर के लिए जाँच करें। जटिलता ओ (एन)।
फास्ट & कम स्मृति पदचिह्न: एक झाड़ू-लाइन एल्गोरिथ्म, एक वर्णित here (या here) जैसे का उपयोग करें। जटिलता O (n लॉग इन करें n)
पिछले मेरी पसंदीदा है, क्योंकि यह अच्छा गति है - स्मृति शेष है, विशेष रूप से Bentley-Ottmann algorithm। कार्यान्वयन या तो जटिल नहीं है।
जांचें कि की कोई जोड़ी गैर-संगत लाइन सेगमेंट छेड़छाड़ की जाती है या नहीं।
वे सभी कशेरुकों पर छेड़छाड़ करना चाहिए; प्रश्न तब बन जाता है जो रेखा खंडों के मनमाने ढंग से सेट के बीच एक गैर-चरम चौराहे की जांच करने का सबसे तेज़ तरीका है। – GWLlosa
अच्छा बिंदु, अगर गैर-निरंतर खंडों एक दूसरे को काटना जाँच करने के लिए यह संपादित। मुझे नहीं लगता कि एक अंतर्निहित विधि है, आपको एक विधि लिखनी होगी। पॉलीगॉन प्राप्त करके शुरू करें। अंक –
क्या आपका मतलब ** खुला ** रेखा खंड नहीं है? मैंने कभी भी गैर-संगत रेखा खंडों के बारे में नहीं सुना है। –
पूर्णता के लिए मैं इस चर्चा में एक और एल्गोरिदम जोड़ता हूं।
पाठक मानते हैं कि अक्ष के गठबंधन बाध्यकारी बक्से (Google अगर नहीं है) के बारे में जानता है तो यह किनारों के जोड़े को तुरंत ढूंढने में बहुत सक्षम हो सकता है जिनके पास "स्वीप और प्रून एल्गोरिदम" का उपयोग करके एएबीबी की टक्कर हो रही है। (यह गूगल)। इन जोड़ों पर छेड़छाड़ की दिनचर्या को बुलाया जाता है।
लाभ यहाँ है कि आप भी एक गैर सीधा किनारा (हलकों और splines) के एक दूसरे को काटना सकता है और दृष्टिकोण लगभग इसी तरह कुशल यद्यपि अधिक सामान्य है।
हम बोलते हुए आखिरी एल्गोरिदम के आसपास अपना सिर पाने की कोशिश कर रहे हैं; विशेष रूप से, मैं मुसीबत संरचना टी – GWLlosa
* टी * का अर्थ/उद्देश्य पर नज़र रखने के आ रही है एक संरचना है, जो रेखा खंडों कि पार झाडू लाइन * एल * होता है। सबसे कुशल संरचना होगा एक द्विआधारी खोज वृक्ष (यह भी देखें [बेंटले-Ottmann एल्गोरिथ्म] (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm))। –
मैंने एक और लिंक जोड़ा [लिंक जहां बेंटले-ओटमैन एल्गोरिदम] (http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm) चित्रों के साथ वर्णित है। –