किसी क्षेत्र पर अंक की सबसे नज़दीकी जोड़ी ढूंढना

Question

मुझे पता है कि 2 डी मामलों (एक्स और वाई) के लिए अंक एल्गोरिदम (शामोस और होई) के एन लॉग एन निकटतम जोड़ी को कैसे कार्यान्वित किया जाए। हालांकि एक ऐसी समस्या के लिए जहां अक्षांश और देशांतर दिया जाता है, इस दृष्टिकोण का उपयोग नहीं किया जा सकता है। दो बिंदुओं के बीच की दूरी को हेवरसिन सूत्र का उपयोग करके गणना की जाती है।

मैं जानना चाहता हूं कि इन अक्षांशों और अनुदैर्ध्यों को अपने संबंधित एक्स और वाई निर्देशांक में परिवर्तित करने और बिंदुओं की सबसे नज़दीकी जोड़ी ढूंढने का कोई तरीका है, या यदि कोई अन्य तकनीक है जो इसे करने के लिए उपयोग की जा सकती है।

Answer 1

मैं उन्हें तीन आयामी निर्देशांक में अनुवादित करता हूं और फिर divide and conquer approach का उपयोग एक रेखा के बजाय विमान का उपयोग करके करता हूं। यह निश्चित रूप से सही ढंग से काम करेगा। हमें इसका आश्वासन दिया जा सकता है क्योंकि जब क्षेत्र में केवल अंक की जांच होती है, तो आर्क दूरी (सतह पर चलने वाली दूरी) द्वारा दो निकटतम बिंदु भी 3-डी कार्टेशियन दूरी से निकटतम होंगे। इसमें ओ (nlogn) चलने का समय होगा।

3-डी निर्देशांक में अनुवाद करने के लिए, पृथ्वी का केंद्र (0,0,0) बनाने का सबसे आसान तरीका है और फिर आपके निर्देशांक (cos (lat) * cos (lon), cos (lat) * sin (लैन), पाप (अक्षां))। उन उद्देश्यों के लिए मैं गणना का सरलीकरण करने के लिए एक पैमाने का उपयोग कर रहा हूं जिसके लिए पृथ्वी का त्रिज्या 1 है। यदि आप किसी अन्य इकाई में दूरी चाहते हैं, तो उस इकाई में मापा जाने पर पृथ्वी की त्रिज्या से सभी मात्राओं को गुणा करें।

मुझे ध्यान रखना चाहिए कि यह सब मानते हैं कि पृथ्वी एक क्षेत्र है। यह बिल्कुल एक नहीं है और अंक वास्तव में ऊंचाई भी हो सकते हैं, इसलिए ये उत्तर वास्तव में पूरी तरह से सटीक नहीं होंगे, लेकिन वे लगभग हर मामले में सही होने के बहुत करीब होंगे।