algorithm - पता लगाएं कि कोई बिन्दु जो कि पतवार को कंप्यूटिंग के बिना अंक के सेट के लिए उत्तल पतवार के अंदर है




graphics geometry (4)

आपको उत्तल पतवार को गणना करने की ज़रूरत नहीं है, क्योंकि यह बहुआयामी रिक्त स्थान में काफी परेशानी लगता है। उत्तल हुल्स की एक प्रसिद्ध संपत्ति है :

अंकों की उत्तल पत के अंदर कोई भी सदिश (बिंदु) v [v1, v2, .., vn] sum(ki*vi) रूप में प्रस्तुत किया जा सकता है, जहां 0 <= ki <= 1 और sum(ki) = 1 इसी प्रकार, उत्तल पतवार के बाहर कोई बिंदु ऐसे प्रतिनिधित्व नहीं होगा।

एम-डायमेंशनल स्पेस में, यह हमें n अज्ञात के साथ m रैखिक समीकरण का सेट देगा।

संपादित करें
मैं सामान्य मामले में इस नई समस्या की जटिलता के बारे में निश्चित नहीं हूँ, लेकिन m = 2 यह रैखिक लगता है। शायद, इस क्षेत्र में अधिक अनुभव वाला कोई व्यक्ति मुझे सही करेगा

एक बिंदु पी एक्स के एक सेट के द्वारा गठित एक उत्तल पतवार के अंदर है, तो जांचने का सबसे आसान तरीका क्या है?

मुझे एक एल्गोरिदम चाहिए जो एक उच्च-आयामी अंतरिक्ष में काम करता है (कहो, 40 आयाम तक) जो स्पष्ट रूप से उत्तल पतवार की गणना नहीं करता है कोई विचार?


एक रैखिक कार्यक्रम के एक व्यावहारिक बिंदु को खोजने के द्वारा समस्या का समाधान किया जा सकता है। यदि आप पूरी जानकारी में दिलचस्पी रखते हैं, तो एक एलएपी को मौजूदा सॉल्वर में प्लग करने का विरोध करने के बजाय, मैं बॉयड और वंदेनबर्ग की उत्कृष्ट पुस्तक पर अध्याय 11.4 पढ़ने की सिफारिश कर रहा हूं।

सेट A = (X[1] X[2] ... X[n]) , यही पहला कॉलम है v1 , दूसरा v2 , आदि।

निम्न एल.पी. समस्या का समाधान करें,

minimize (over x): 1
s.t.     Ax = P
         x^T * [1] = 1
         x[i] >= 0  \forall i

कहा पे

  1. x^T का ट्रांस्पोसेज़ x
  2. [1] सभी 1 वेक्टर है

समस्या का हल अगर iff है बिंदु उत्तल पतवार में है।


मुझे 16 आयामों के साथ एक ही समस्या थी चूंकि क्यूल ने ठीक से काम नहीं किया, क्योंकि बहुत अधिक चेहरे उत्पन्न हो गए थे, मैंने परीक्षण के द्वारा अपना दृष्टिकोण विकसित किया है, चाहे नया बिंदु और संदर्भ डेटा (मैं इसे "हाइपरहोल्ड" कहता हूं) के बीच अलग-अलग हाइपरप्लेन पाया जा सकता है) ।

एक अलग हाइपरप्लेन खोजने की समस्या को एक उत्तल वर्ग प्रोग्रामिंग समस्या (देखें: एसवीएम ) में बदला जा सकता है। मैं इसे अजगर में cvxopt का उपयोग करके कम से कम 170 लाइनों कोड (I / O सहित) के साथ किया था। एल्गोरिथ्म किसी भी आयाम में संशोधन के बिना काम करता है, भले ही समस्या मौजूद हो, यह जितना ऊंचा हो, पतवार के बिंदुओं की संख्या जितनी ऊंची होगी (देखें: पॉलीटोप में यादृच्छिक बिंदुओं के उत्तल पतवार पर ) चूंकि हुल स्पष्ट रूप से निर्मित नहीं है, लेकिन केवल जांच की जाती है, चाहे कोई बिंदु अंदर या न हो, एल्गोरिथ्म के मुकाबले उच्च आयामों में बहुत बड़ा लाभ है जैसे कि तेज पतवार

यह एल्गोरिदम 'स्वाभाविक रूप से समानांतर' हो सकता है और गति को प्रोसेसर की संख्या के बराबर होना चाहिए।


यद्यपि मूल पोस्ट तीन साल पहले थी, शायद यह उत्तर अभी भी मदद का होगा। गिल्बर्ट-जॉनसन-कीर्ति (जीजेके) एल्गोरिथ्म दो उत्तल पॉलीपॉप्स के बीच सबसे कम दूरी पाती है, जिनमें से प्रत्येक को जनरेटर के सेट के उत्तल पतवार के रूप में परिभाषित किया जाता है- विशेषकर, उत्तल पतल को गणना नहीं करना पड़ता है एक विशेष मामले में, जो मामले के बारे में पूछा जा रहा है, पॉलीपॉप्स में से एक सिर्फ एक बिंदु है पी के बीच की दूरी और अंक एक्स के उत्तल पतवार की गणना करने के लिए GJK एल्गोरिथम का उपयोग क्यों न करें? यदि वह दूरी 0 है, तो पी एक्स के अंदर है (या कम से कम इसकी सीमा पर)। ओक्टेवे / मैटलैब में एक जीजेके का कार्यान्वयन, क्लोजस्टपोइंट इनकॉन्वेक्स पॉलिटेप जीजेके। एम, समर्थन कोड के साथ, http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html पर उपलब्ध है। जीजेके एल्गोरिथ्म का एक सरल विवरण संप्रदाय में उपलब्ध है। एक कागज के 2, http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf पर मैंने 31-आयामी अंतरिक्ष में कुछ बहुत छोटे सेट एक्स के लिए जीजेके एल्गोरिदम का उपयोग किया है, और अच्छे परिणाम दिए हैं I जीजेके का प्रदर्शन रैखिक प्रोग्रामिंग विधियों की तुलना करता है, जो दूसरों की सिफारिश कर रहे हैं अनिश्चित (हालांकि कोई भी तुलना दिलचस्प होगा)। जीजेके विधि उत्तल पतवार की गणना करने से या रेखीय असमानताओं के संदर्भ में पतवार को व्यक्त करने से बचना है, जो दोनों समय लेने वाली हो सकती है। उम्मीद है कि यह उत्तर मदद करता है





computational-geometry