गैर-उत्तल बहुभुज में शिखर के बड़े सेट को देखते हुए, मैं किनारों को कैसे ढूंढ सकता हूं?

Question

मेरे पास शिखर का एक सेट है (जिसे ए कहा जाता है) और मैं सभी सीमावर्ती शीर्षकों को ढूंढना चाहता हूं जैसे कि यह सीमा शिखर सेट आकार की रूपरेखा है।

ए में कई कोष्ठक अनावश्यक हैं क्योंकि वे आकार के अंदर हैं, मैं इन कोष्ठकों से छुटकारा पाना चाहता हूं।

मेरा प्रश्न Best Algorithm to find the edges (polygon) of vertices जैसा है लेकिन मुझे इसे गैर-उत्तल बहुभुज मामले के लिए काम करने की आवश्यकता है।

संपादित करें: स्पष्टीकरण: नीचे दी गई छवि एक अवतल बहुभुज है। यह मेरा मतलब गैर-उत्तल द्वारा किया गया था। यदि मैं उस पर एक उत्तल हल एल्गोरिदम चलाता हूं, तो यह बहुभुज के अवतल भाग को संरक्षित नहीं करेगा। (जब तक कि मैं गलत नहीं हूं)।

मैं कोने का एक सेट है अंदर और बहुभुज की सीमा पर: [[x1, y1], [x2, y2] ...] मैं इतना है कि सेट को कम करना चाहते शिखर केवल आकार की सीमा रूपरेखा हैं।

Answer 1

यह एक गर्म विषय हो रहा है .. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

इस पत्र सबसे अच्छा लगता है। Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

Answer 2

आपका विवरण कुछ अस्पष्ट है लेकिन यह संभव है कि आप अंक के सेट के Convex Hull बनाने के लिए एल्गोरिदम की तलाश में हैं। सीधे शब्दों में कहें, उत्तल ढक्कन वह आकार है जो आप प्राप्त करते हैं यदि आप सभी कोष्ठकों के चारों ओर एक रबड़ बैंड डालते हैं।
2 डी में एक उत्तल पतवार एल्गोरिथ्म लेखन बहुत मुश्किल नहीं है और वहाँ कुछ पुस्तकालयों है कि यह की तरह qhull

(यही कारण है कि इस सवाल का जवाब भी प्रश्न में दी गई है क्या आप जो करने के लिए का एक विशेष मामला प्रतीत हो रहा है लिंक कर रहे हैं अपने प्रश्न)

Answer 3

यह एक पुराना, शायद त्याग दिया गया सवाल है, लेकिन यह मुझे इसके बारे में सोच रहा है। आप एक उत्तल ढक्कन की तलाश नहीं कर रहे हैं, आप बहुभुज आकार को बनाए रखना चाहते हैं, लेकिन केवल एक पंक्ति के साथ "किनारों" के बीच स्थित बिंदुओं से छुटकारा पाएं।

समाधान पड़ोसी बिंदुओं के माध्यम से कदम उठाने और पहले और दूसरे की रैखिक ढलान की गणना करने के लिए हो सकता है, फिर उस ढलान मूल्य को बचाकर, दूसरे और तीसरे की ढलान की गणना करें, यदि pt1-pt2 की ढलान उसके बराबर है pt2-pt3 के बाद pt2 लाइन बनाने में अनावश्यक है और इस प्रकार हटाया जा सकता है। जब तक आप पीटी 1 पर वापस हवा नहीं लेते तब तक लूपिंग रखें।

यह सुनिश्चित करेगा कि आपका अवतल आकार बनाए रखा जाए लेकिन अप्रासंगिक अतिरिक्त अंक हटा दिए जाएंगे।