शिखर के किनारों (बहुभुज) को खोजने के लिए सर्वश्रेष्ठ एल्गोरिदम

Question

मेरे पास बड़ी संख्या में शिखर हैं, उनमें से कुछ किनारों हैं, कुछ अनावश्यक हैं (आकार के अंदर) और मैं उनको हटाना चाहता हूं।

सबसे सरल एल्गोरिदम मैं सोच सकता हूं कि अगर वे दूसरों द्वारा गठित आकार को हिट करते हैं तो एक-एक करके जांच कर सकते हैं। लेकिन यह एक बहुत धीमी एल्गोरिदम होना चाहिए।

मैंने किनारे से एक को चुनने के बारे में सोचा (प्रति उदाहरण मूल से सबसे दूर) और इस शुरुआत से सबसे लंबा रास्ता गणना करें ... किनारे का रास्ता प्राप्त करना चाहिए, है ना?

कोई सुझाव?

Answer 1

पॉलीहेड्रल एल्गोरिदम के साथ चाल आपके इनपुट और आपके वांछित आउटपुट के साथ फिट बैठ रही है, क्योंकि पॉलीहेड्रॉन का प्रतिनिधित्व करने के लिए एक से अधिक तरीके हैं और प्रतिनिधित्व के बीच कनवर्ट करना महंगा हो सकता है। इस मामले में, आप अंक से शुरू कर रहे हैं और शिखर के साथ समाप्त करना चाहते हैं, इसलिए convex hull के शीर्षकों की गणना करने के लिए एल्गोरिदम चाल चलाना चाहिए, हालांकि यह 2-डी मामले से पहले इसे विस्तारित करने के लिए कुछ प्रयास कर सकता है। यह इनपुट कॉलर की संख्या में ओ (एन लॉग एन) है।

Answer 2

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

इसके लिए खोज करके, आपको एक मिलान करने वाला एल्गोरिदम मिलना चाहिए।

Answer 3

The Convex Hull कम्प्यूटेशनल ज्यामिति की अधिक शोध समस्याओं में से एक है। ग्राहम स्कैन सरल convex hull algorithms में से एक है, लेकिन निश्चित रूप से केवल एक ही नहीं है। The Gift-wrapping Algorithm, जिसे जार्विस 'मार्च भी कहा जाता है, मुझे सबसे सरल पता है। The Stony Brook algorithm repository में सी और सी ++ में उत्तल हल एल्गोरिदम के कई कार्यान्वयन हैं। Geometry in Action मुख्य रूप से उत्तल हल्स के अनुप्रयोग दिखाता है। यहां low-dimensional और arbitrary-dimensional उत्तल हॉल गणना कार्यक्रमों का संग्रह दिया गया है।