लेट की तुलना, लंबे समन्वय

Question

मेरे पास 15 हजार से अधिक अक्षांश और देशांतर निर्देशांक की एक सूची है। किसी भी एक्स, वाई निर्देशांक को देखते हुए, सूची में निकटतम निर्देशांक खोजने का सबसे तेज़ तरीका क्या है?

Answer 1

आप Voronoi diagram नामक एक ज्यामितीय निर्माण का उपयोग करना चाहेंगे। यह विमान को कई क्षेत्रों में विभाजित करता है, प्रत्येक बिंदु के लिए एक, जिसमें आपके प्रत्येक दिए गए बिंदुओं के सबसे नज़दीकी सभी बिंदु शामिल होते हैं।

वोरोनोई आरेख बनाने के लिए सटीक एल्गोरिदम के लिए कोड और डेटा संरचना लुकअप की व्यवस्था इस छोटे से संपादन बॉक्स में फ़िट होने के लिए बहुत बड़ी है। :)

@ लिनोर: यह वस्तुतः वोरोनोई आरेख बनाने के बाद आप क्या करेंगे। लेकिन एक आयताकार ग्रिड बनाने के बजाय, आप विभाजित लाइनों का चयन कर सकते हैं जो वोरोनोई आरेख की रेखाओं से निकटता से मेल खाते हैं (इस तरह आपको कम क्षेत्र मिलेंगे जो विभाजित लाइनों को पार करते हैं)। यदि आप प्रत्येक उपशीर्षक के लिए सबसे अच्छी विभाजन रेखा के साथ अपने वोरोनोई आरेख को आधे भाग में विभाजित करते हैं, तो आप प्रत्येक बिंदु के लिए एक वृक्ष खोज कर सकते हैं जिसे आप देखना चाहते हैं। इसके लिए थोड़ा सा काम आगे की आवश्यकता है लेकिन बाद में समय बचाता है। प्रत्येक लुकअप लॉग एन के क्रम पर होगा जहां एन अंक की संख्या है। 16 तुलना 15,000 से बहुत बेहतर है!

Answer 2

भले ही आप एक वोरोनोई आरेख बनाते हैं, फिर भी इसका मतलब है कि आपको अपने 15, बनाए गए क्षेत्रों में अपने एक्स, वाई निर्देशांक की तुलना करने की आवश्यकता है। इसे आसान बनाने के लिए, पहली बात जो मेरे दिमाग में चली गई थी, संभवतः संभव मूल्यों पर ग्रिड बनाने के लिए कुछ प्रकार का निर्माण करना था, ताकि आप आसानी से जगह बना सकें और ग्रिड में बॉक्स में से किसी एक में x/y समन्वय कर सकें, यदि वही है उन क्षेत्रों की सूची के लिए किया गया है जिन्हें आपको संभावित उम्मीदवारों को तुलना के लिए जल्दी से कम करना चाहिए (क्योंकि ग्रिड अधिक आयताकार होगा, एक क्षेत्र के लिए कई ग्रिड स्थितियों में होना संभव है)।

Answer 3

सामान्य अवधारणा जिसे आप वर्णन कर रहे हैं nearest-neighbour search है, और तकनीक की एक पूरी तरह से छत है जो इन प्रकार के प्रश्नों को हल करने के साथ सौदा करती है, या तो बिल्कुल या लगभग। मूल विचार ओ (एन) प्रति क्वेरी (लगभग) ओ (लॉग एन) प्रति जटिलता को जटिलता को कम करने के लिए स्थानिक विभाजन तकनीक का उपयोग करना है।

केडी-पेड़, और केडी-पेड़ के वेरिएंट बहुत अच्छी तरह से काम करते प्रतीत होते हैं, लेकिन चौकोर पेड़ भी काम करेंगे। इन खोजों की गुणवत्ता इस बात पर निर्भर करती है कि 15,000 डेटा पॉइंट्स का आपका सेट स्थिर है (आप संदर्भ सेट में बहुत से डेटा पॉइंट्स नहीं जोड़ रहे हैं)। Approximate Nearest Neighbour लाइब्रेरी पर माउंट और आर्य का काम गणित में अच्छी ग्राउंडिंग के बिना भी उपयोग करना और समझना आसान है। यह आपको अपने प्रश्नों के प्रकार और सहनशीलता में कुछ लचीलापन भी देता है।

Answer 4

Premature optimization is the root of all evil.

15K निर्देशांक कि ज्यादा नहीं हैं। क्यों 15 के निर्देशांक पर पुनरावृत्ति नहीं करते हैं और देखें कि क्या वास्तव में यह एक प्रदर्शन समस्या है? आप बहुत सारे काम बचा सकते हैं और हो सकता है कि यह कभी भी नोटिस करने में धीमा न हो।

Answer 5

आपने यह निर्दिष्ट नहीं किया कि आप सबसे तेज़ी से क्या मतलब रखते हैं। यदि आप किसी भी कोड को लिखने के बिना तुरंत जवाब प्राप्त करना चाहते हैं, तो मैं gpsbabel radius filter को एक यात्रा दूंगा।

Answer 6

यह निर्भर करता है कि आप इसे कितनी बार करना चाहते हैं, और कौन से संसाधन उपलब्ध हैं - यदि आप एक बार परीक्षण कर रहे हैं, तो ओ (लॉग एन) तकनीकें अच्छी हैं। यदि आप इसे सर्वर पर एक हजार बार कर रहे हैं, तो बिटमैप लुकअप टेबल बनाना तेजी से होगा, या तो परिणाम सीधे या पहले चरण के रूप में देगा। 2 जीबी बिटमैप पूरे विश्व लैट-लॉन को 32 बिट मान पर 0.011 डिग्री पिक्सेल (भूमध्य रेखा पर 1.2 किमी) पर मैप कर सकता है, और स्मृति में फिट होना चाहिए। यदि आप केवल एक देश कर रहे हैं, या ध्रुवों को बाहर कर सकते हैं, तो आपके पास एक छोटा नक्शा या उच्च रिज़ॉल्यूशन हो सकता है। 15,000 अंक के लिए आपके पास शायद एक बहुत छोटा नक्शा है - मैंने इसे पहले पोस्टकोड खोजों में लैट-लॉन करने के पहले चरण के रूप में आकार दिया है, जिसके लिए उच्च रिज़ॉल्यूशन की आवश्यकता है।आवश्यकताओं के आधार पर, आप सीधे परिणाम पर इंगित करने के लिए मैप किए गए मान का उपयोग करते हैं, या उम्मीदवारों की छोटी सूची (जो एक छोटे से मानचित्र की अनुमति देगा, लेकिन बाद में प्रसंस्करण की आवश्यकता होती है - आप ओ (1) लुकअप क्षेत्र में नहीं हैं)।

Answer 7

मैंने इसे एक बार वेबसाइट के लिए किया था। अर्थात। अपने ज़िप कोड के 50 मील के भीतर डीलर ढूंढें। मैंने 50 मील उत्तर, 50 मील पूर्व, 50 मील दक्षिण और 50 मील पश्चिम के निर्देशांक खोजने के लिए great circle calculation का उपयोग किया। इससे मुझे एक मिनट और अधिकतम लेट और एक मिनट और अधिकतम लंबा दिया गया। वहाँ तब से मैं एक डेटाबेस क्वेरी किया:

select * 
    from dealers 
    where latitude >= minlat 
     and latitude <= maxlat 
     and longitude >= minlong 
     and longitude <= maxlong 

के बाद से उन परिणामों से कुछ अभी भी 50 से अधिक मील दूर हो जाएगा, तो मैं great circle formula एक बार फिर निर्देशांक कि छोटी सूची पर इस्तेमाल किया। फिर मैंने लक्ष्य से दूरी के साथ सूची मुद्रित की।

बेशक, यदि आप अंतरराष्ट्रीय तिथि रेखा या ध्रुवों के पास बिंदुओं की खोज करना चाहते हैं, तो इससे काम नहीं करेगा। लेकिन यह उत्तरी अमेरिका के अंदर खोजों के लिए बहुत अच्छा काम करता है!

Answer 8

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

काफी सरल दूरी सूत्र और एक ब्रूट फोर्स सर्च के साथ शुरू करें और देखें कि यह कितना समय ले रहा है और यदि परिणाम फैंसी होने से पहले सटीक हैं।

Answer 9

उत्तर के लिए सभी को धन्यवाद।

@ टॉम, @ क्रिस अपचर्च: निर्देशांक एक दूसरे के काफी करीब हैं, और वे लगभग 800 वर्ग किलोमीटर के अपेक्षाकृत छोटे क्षेत्र में हैं। मुझे लगता है कि मैं सतह को सपाट मान सकता हूं। मुझे बार-बार अनुरोधों को संसाधित करने की आवश्यकता है, और प्रतिक्रिया अधिक वेब अनुभव के लिए पर्याप्त तेज़ी से होनी चाहिए।

Answer 10

आपकी स्पष्टीकरण के आधार पर, मैं एक केम-पेड़ या आर-पेड़ जैसे ज्यामितीय डेटा संरचना का उपयोग करूंगा। MySQL में एक स्थानिक डेटा प्रकार है जो यह करता है। अन्य भाषाओं/ढांचे/डेटाबेस में इसका समर्थन करने के लिए पुस्तकालय हैं। असल में, इस तरह की एक डेटा संरचना आयत के पेड़ में अंक एम्बेड करती है, और त्रिज्या का उपयोग करके पेड़ की खोज करती है। यह पर्याप्त तेज़ होना चाहिए, और मेरा मानना ​​है कि वोरोनोई आरेख बनाने से सरल है। मुझे लगता है कि ऊपर कुछ सीमा है जिसके ऊपर आप वोरोनोई आरेख के अतिरिक्त प्रदर्शन को प्राथमिकता देंगे ताकि आप अतिरिक्त जटिलता का भुगतान करने के लिए तैयार हों।

Answer 11

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

 
for each point p 
    get cell that contains p 
    add point to that cell's list 

और यह चीजों को देखने के लिए बहुत आसान है:

 
given a query point p 
    get cell that contains p 
    check points in that cell (and its 8 neighbors), against query point p 

एलेजो

Answer 12

यह कई मायनों में हल किया जा सकता। मैं पहले Delaunay नेटवर्क को एक-दूसरे से निकटतम बिंदु जोड़ने के द्वारा इस समस्या से संपर्क करता हूं। इसे ओपन सोर्स जीआईएस एप्लीकेशन GRASS में v.delaunay कमांड के साथ पूरा किया जा सकता है। आप GRASS में कई network analysis modules में से किसी एक का उपयोग करके GRASS में समस्या को पूरा कर सकते हैं। वैकल्पिक रूप से, आप दूरस्थ क्वेरी करने के लिए मुफ्त स्थानिक आरडीबीएमएस PostGIS का उपयोग कर सकते हैं।पोस्टजीआईएस स्थानिक प्रश्न MySQL में उन लोगों की तुलना में काफी शक्तिशाली हैं, क्योंकि वे बीबीओएक्स संचालन के लिए बाध्य नहीं हैं। उदाहरण के लिए:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10; 

आप देशांतर और अक्षांश उपयोग कर रहे हैं के बाद से, आप शायद Spheroid-Distance functions उपयोग करना चाहते हैं। एक स्थानिक सूचकांक के साथ, पोस्टजीआईएस बड़े डेटासेट के लिए बहुत अच्छी तरह से स्केल करता है।

Answer 13

बस कॉन्ट्रैरियन होने के लिए, क्या आपका मतलब निकट दूरी या (ड्राइविंग) समय है? एक शहरी क्षेत्र में मैं खुशी से 4 मील (20min स्टॉप और जाने) की तुलना में राजमार्ग पर 5 मील (5 मिनट) ड्राइव करता हूं।

इस प्रकार यदि यह आपको 'निकटतम' मीट्रिक की आवश्यकता है, तो मैं यात्रा समय मेट्रिक्स के साथ जीआईएस डेटाबेस देखता हूं।