एक क्षेत्र की सतह पर 0 डिग्री (अक्षांश, अक्षांश)-बिंदुओं का उत्तल हॉल

Question

मानक उत्तल हॉल एल्गोरिदम (अक्षांश, अक्षांश)-बिंदुओं के साथ काम नहीं करेगा, क्योंकि मानक एल्गोरिदम मानते हैं कि आप कार्टेशियन बिंदुओं के सेट की हल चाहते हैं। अक्षांश-रेखांश बिंदु कार्टेशियन नहीं हैं, क्योंकि एंटी-मेरिडियन (+/- 180 डिग्री) पर रेखांश "चारों ओर लपेटता है"। यानी, 17 डिग्री रेखांश के दो डिग्री पूर्व -179 है।

तो यदि अंक का आपका सेट एंटी-मेरिडियन को छेड़छाड़ करने के लिए होता है, तो आप नकली हल्स की गणना करेंगे जो दुनिया भर में गलत तरीके से फैलता है।

चाल के लिए कोई सुझाव मैं इसके लिए सही करने के लिए एक मानक उत्तल हॉल एल्गोरिदम के साथ आवेदन कर सकता हूं, या उचित "भू-भौतिक" हल एल्गोरिदम के लिए पॉइंटर्स?

अब जब मैं सोचता हूं, एंटी-मेर्डियन को झुकाव करने के बजाय विचार करने के लिए और अधिक दिलचस्प मामले हैं। पृथ्वी के घेरे वाले बिंदुओं के "बैंड" पर विचार करें - इसके उत्तल ढक्कन में पूर्व/पश्चिम सीमा नहीं होगी। या फिर भी, {(0,0), (0, 9 0), (0, -90), (90, 0), (-90, 0), (180, 0)} का उत्तल झुकाव क्या है? - इसमें पृथ्वी की पूरी सतह शामिल होगी, तो कौन से अंक इसके परिधि पर हैं?

Answer 1

स्टैंडर्ड उत्तल पतवार एल्गोरिदम रैपिंग से हार नहीं कर रहे हैं पृथ्वी की सतह पर निर्देशांक का सार - लेकिन एक और मौलिक समस्या से। एक गोलाकार की सतह (चलो पृथ्वी की काफी-गोलाकारता को भूलना नहीं) एक यूक्लिडियन अंतरिक्ष नहीं है, इसलिए यूक्लिडियन ज्यामिति काम नहीं करती है, और उत्तल हॉल रूटीन जो मानते हैं कि अंतर्निहित स्थान यूक्लिडियन है (मुझे दिखाएं जो ' टी, कृपया) काम नहीं करेगा।

क्षेत्र की सतह elliptic geometry की अवधारणाओं के अनुरूप होती है जहां रेखाएं बड़ी सर्कल होती हैं और एंटीपोडल बिंदुओं को एक ही बिंदु माना जाता है। आप पहले से ही एक अंडाकार अंतरिक्ष में उत्परिवर्तन की यूक्लिडियन अवधारणा को लागू करने की कोशिश करने से उत्पन्न होने वाले मुद्दों का अनुभव करना शुरू कर चुके हैं।

आपके लिए एक दृष्टिकोण खुला है geodesic convexity की परिभाषाओं को अपनाने और एक भूगर्भीय उत्तल हलचल दिनचर्या को लागू करना होगा। वह काफी बालों लग रहा है। और यह परिणाम उत्पन्न नहीं कर सकता है जो आपके (आमतौर पर यूक्लिडियन) अपेक्षाओं के अनुरूप है। कई मामलों में, 3 मनमानी बिंदुओं के लिए, उत्तल ढक्कन क्षेत्र की पूरी सतह बन जाता है।

युग के माध्यम से नेविगेटर और कार्टोग्राफ़रों द्वारा अपनाया गया एक अन्य दृष्टिकोण, यूक्लिडियन अंतरिक्ष में जो क्षेत्र (आपकी सभी बिंदुओं वाला एक हिस्सा) की सतह का हिस्सा प्रोजेक्ट करना होगा (जो नक्शा अनुमानों का विषय है और मैंने जीता उस पर व्यापक साहित्य के संदर्भ के साथ आपको परेशान नहीं करता) और अनुमानित बिंदुओं के उत्तल ढांचे को समझने के लिए। जिस क्षेत्र में आप रुचि रखते हैं उस क्षेत्र को प्रोजेक्ट करें और निर्देशांक समायोजित करें ताकि वे चारों ओर लपेट न जाएं; उदाहरण के लिए, यदि आप फ्रांस में दिलचस्पी रखते हैं तो आप 30 डिग्री जोड़कर सभी लम्बाई समायोजित कर सकते हैं ताकि पूरे देश को + संख्याओं द्वारा समन्वित किया जा सके।

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

Answer 2

अक्षांश-देशांतर डेटा के रूप में आपके डेटा पर विचार करने के बजाय, क्या आप इसे 3 डी स्पेस में मान सकते हैं और 3D convex hull algorithm लागू कर सकते हैं? फिर आप 3 डी उत्तल हॉल का विश्लेषण करके 2 डी उत्तल झुकाव प्राप्त करने में सक्षम हो सकते हैं।

यह आपको कार्टेशियन उत्तल hulls (हालांकि तीन आयामों में) के लिए अच्छी तरह से यात्रा एल्गोरिदम पर लौटाता है और निर्देशांक के चारों ओर लपेटने के साथ कोई समस्या नहीं है।

वैकल्पिक रूप से, वहाँ इस पत्र है: Computing the Convex Hull of a Simple Polygon on the Sphere (1996) जो एक ही मुद्दों है कि आप के साथ काम कर रहे हैं में से कुछ से निपटने के लिए लगता है (आदि समन्वय चादर के आसपास,)

Answer 3

यदि आपके सभी अंक एक गोलार्द्ध के भीतर हैं (यानी, यदि आप पृथ्वी के केंद्र के माध्यम से एक कट विमान ढूंढ सकते हैं जो उन्हें एक तरफ रखता है), तो आप केंद्रीय उर्फ ​​gnomic उर्फ ​​gnomonic प्रक्षेपण कर सकते हैं कट ऑफ प्लेन के समानांतर विमान के लिए पृथ्वी का केंद्र। फिर सभी महान सर्किल प्रक्षेपण में सीधी रेखाएं बन जाती हैं, और इसलिए प्रक्षेपण में एक उत्तल ढक्कन पृथ्वी पर एक सही उत्तल झुकाव पर वापस आ जाएगा। आप देख सकते हैं कि "गनोमोनिक प्रक्षेपण" खंड here में अक्षांश रेखाओं को देखकर कितना गलत लैट/लोन पॉइंट देख रहे हैं (ध्यान दें कि रेखांश रेखाएं सीधे रहती हैं)।

(पृथ्वी को एक क्षेत्र के रूप में मानना ​​अभी भी सही नहीं है, लेकिन यह एक अच्छा दूसरा अनुमान है। मुझे एक और यथार्थवादी पृथ्वी (WGS84) पर एक वास्तविक कम दूरी वाले पथ पर अंक नहीं लगता है । केंद्र के माध्यम से एक विमान आप क्या आप एक क्षेत्र के साथ मिल की तुलना में एक बेहतर सन्निकटन देता है वे करते हैं हो सकता है कि नाटक)

Answer 4

FutureNerd:।

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

अंक एक ही गोलार्ध में होना चाहिए। जैसे-जैसे यह निकलता है, इस गोलार्द्ध को चुनना गैर-तुच्छ है (यह केवल अंक 'केंद्र नहीं है, जैसा कि मैंने शुरू में अनुमान लगाया था।) उदाहरण के लिए, निम्नलिखित चार बिंदुओं पर विचार करें: (0,0), (-60,0), (+60,0) भूमध्य रेखा के साथ, और (0,90) उत्तर ध्रुव। हालांकि आप "केंद्र" को परिभाषित करना चुनते हैं, उनका केंद्र उत्तर ध्रुव पर समरूपता से स्थित है और सभी चार बिंदु उत्तरी गोलार्ध में हैं। हालांकि, चौथे बिंदु को प्रतिस्थापित करने पर विचार करें, (-19, 64) आइसलैंड। अब उनका केंद्र उत्तर ध्रुव पर नहीं है, लेकिन असममित रूप से आइसलैंड की ओर खींचा गया है। हालांकि, सभी चार बिंदु अभी भी उत्तरी गोलार्ध में हैं। इसके अलावा, उत्तरी गोलार्ध, जिसे उत्तरी ध्रुव द्वारा विशिष्ट रूप से परिभाषित किया गया है, वह केवल गोलार्द्ध है जिसे वे साझा करते हैं। तो इस "ध्रुव" की गणना एल्गोरिदमिक बन जाती है, बीजगणित नहीं। एक महान, सोचा उत्तेजक प्रश्न के लिए https://github.com/VictorDavis/GeoConvexHull