किसी दिए गए बिंदु

Question

पर सबसे नज़दीकी बिंदु ढूंढना मैंने इसके लिए पूरी खोज की है, लेकिन मुझे इसके लिए सबसे अच्छा तरीका नहीं दिख रहा है। मेरे पास लगभग 22000 लैट/लॉन पॉइंट हैं और मैं आईफोन के वर्तमान स्थान पर सबसे नज़दीकी ढूंढना चाहता हूं। मैंने लोगों को क्वाड पेड़, डिजस्ट्रा के एल्गोरिदम, और स्थानिक डेटाबेस के बारे में पूछा है। आईफोन के लिए सबसे अच्छा कौन सा है? स्थानिक डेटाबेस सबसे आसान लगते हैं, लेकिन मुझे यकीन नहीं है।

संपादित करें: वास्तव में 20,000 से अधिक अंक हैं। आपको लगता है कि उन सभी के माध्यम से पुनरावृत्ति करना ऐसा करने का तरीका है? लेकिन आपके इनपुट के लिए धन्यवाद।

धन्यवाद।

Answer 1

वास्तव में, यह सबसे अच्छा Haversine अक्षांश/देशांतर अंक के लिए (महान चक्र) गणना के उपयोग करने के लिए है, अन्यथा तेजी से बड़ी दूरी गलत हो जाएगा, खासकर यदि आप Jherico's answer में की तरह साधारण ट्रिग का उपयोग करें।

एक त्वरित खोज इस जावास्क्रिप्ट उदाहरण प्रदान करता है:

var R = 6371; // km Radius of earth 
var dLat = (lat2-lat1).toRad(); 
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
     Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
     Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c; 

आंकड़ा संरचना के संदर्भ में, Geohash को देख के लायक है।

Answer 2

आप iPhone पर कर रहे हैं के रूप में, आप भौगोलिक दूरी प्रदर्शन करने के लिए CoreLoaction उपयोग कर सकते हैं - का उपयोग कर CLLocation के – getDistanceFrom:

मैं एक जानवर बल रैखिक खोज हालांकि सभी 2k अंक नाद उपयोग करने के लिए करता है, तो यह है कि तेजी से नहीं है परीक्षा की जाएगी पर्याप्त, खोज के लिए अपने अंक के खिलाफ मेटा डेटा स्टोर करने के लिए GeoHash जैसे कुछ पर स्विच करें।

Answer 3

यदि आपको ओ (एन) से बेहतर की आवश्यकता है, तो आप केवल तब ही प्राप्त कर सकते हैं जब आप पहले किसी प्रकार के स्थानिक हैश (क्वाड्री, ऑक्टेट्री, हैश ग्रिड, या इसी तरह) के निर्माण के लिए एन एलजी एन का भुगतान करते हैं। फिर प्रत्येक परीक्षण लगभग ओ (एलजी एन) होगा, और आमतौर पर आपके द्वारा चेक किए गए अंतिम स्थान को कैश करके बहुत बेहतर हो सकता है, यदि बहुत अधिक समेकन होता है (आमतौर पर, वहां होता है)।

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

Answer 4

क्यों दुनिया को क्षेत्रों में टाइल नहीं करते? (हेक्स सोचें।) फिर, जब आप अपनी सूची में अंक जोड़ते हैं, या एक बड़े प्री-प्रोसेसिंग लूप में, प्रत्येक बिंदु के लिए, क्षेत्र को स्टोर करें।

फिर, हेक्स एक्स में बिंदु ए के पास बिंदुओं की खोज करते समय, आपको केवल हेक्स एक्स और अधिकतम 3 पड़ोसी हेक्स में अंक की जांच करने की आवश्यकता होती है।

यदि यह जांचने के लिए अभी भी बहुत अधिक अंक हैं, तो सबग्रेन जोड़ें।

Answer 5

मैं इस एल्गोरिथ्म काम करता है लगता है:

एक सरणी अक्षांश के अनुसार क्रमबद्ध बनाएं एक सरणी देशांतर

के अनुसार क्रमबद्ध बनायें निकटतम खोजने के लिए, पहले में एक द्विआधारी खोज करने द्वारा अक्षांश से सबसे करीब लगता है अक्षांश सरणी रेखांश सरणी के लिए समान करें। अब आपके पास 2 अंक हैं, एक अक्षांश से निकटतम, दूसरा देशांतर से निकटतम है। पायथागोरियन प्रमेय के माध्यम से प्रत्येक बिंदु पर दूरी की गणना करें। निकटतम बिंदु जीतता है।

रोजर

Answer 6

आप पर विचार करना चाहिए कि डिज्कस्ट्रा उपयोग करने के लिए आप ग्राफ में अपने नोड स्थिति पता होना चाहिए, कि बजाय समस्या को हल करने की कोशिश कर रहे है, ग्राफ़ में नहीं कर रहे हैं, लेकिन आप के लिए निकटतम बिंदु को पता है

तो बस, के रूप में पहले से ही अराजकता तुमसे कहा था, आप अपनी स्थिति beetween सभी दूरी और सब 20.000 अंक की गणना करना चाहिए चाहते हैं, तो उन्हें