जियोहाशिंग - पड़ोसियों के पड़ोसियों को दोबारा मिलते हैं

Question

अब मैं जियोहाशिंग एल्गोरिदम (http://www.geohash.org) के पड़ोसियों के पड़ोसियों को खोजने के लिए एक सुरुचिपूर्ण एल्गोरिदम खोज रहा हूं।
मूल रूप से एक केंद्रीय भू-रंग लेते हैं, और फिर इसके चारों ओर समान आकार के हैंश (8 तत्व) की पहली 'अंगूठी' प्राप्त करें, फिर, अगले चरण में, अगली अंगूठी को पहले आदि के आसपास प्राप्त करें आदि क्या आपने सुना है ऐसा करने के लिए एक शानदार तरीका है?

प्रत्येक पड़ोसी को लेने और अपने पड़ोसियों को बड़े पैमाने पर ओवरलैप को अनदेखा करने के लिए ब्रूट फोर्स हो सकता है। (इसी देखने-टेबल के साथ एक केंद्र कुंजी और एक दिशा में गुजर, इस तरह के साथ वर्तमान समाधान,: एक केंद्रीय geohash चारों ओर पड़ोसी (रूबी में यहां उदाहरण के लिए: http://github.com/masuidrive/pr_geohash/blob/master/lib/pr_geohash.rb) कई बार हल किया गया है स्पष्टीकरण के लिए

संपादित करें):

def adjacent(geohash, dir) 
    base, lastChr = geohash[0..-2], geohash[-1,1] 
    type = (geohash.length % 2)==1 ? :odd : :even 
    if BORDERS[dir][type].include?(lastChr) 
     base = adjacent(base, dir) 
    end 
    base + BASE32[NEIGHBORS[dir][type].index(lastChr),1] 
    end 

(Yuichiro MASUI के lib से उद्धरण)

मैं कहता हूँ इस दृष्टिकोण बदसूरत जल्द ही मिल जाएगा, क्योंकि दिशाओं बदसूरत हो जाता है एक बार हम अंगूठी दो या तीन में हैं। एल्गोरिदम आदर्श रूप से केवल दो पैरामीटर, केंद्र क्षेत्र और 0 से दूरी केंद्र केंद्र (["u0m"] और 1 (=> [["u0t", "u0w"], ["u0q", "u0n"], ["u0j", "u0h"], ["u0k", "u0s"]]) के आसपास के समान आकार के 8 भूगोलों से बना पहला अंगूठी है। दो 16 क्षेत्रों के साथ दूसरी अंगूठी है पहले अंगूठी के आसपास आदि

आप एक सुंदर रास्ते में बिट्स से 'के छल्ले' निकालना किसी भी तरह से देख सकते हैं?

Answer 1

है कि आप पड़ोसी द्वारा क्या मतलब है पर निर्भर करता है। मैं इस संभालने हूँ किया जा रहा है निकटता खोज के संदर्भ में। उस मामले में मुझे लगता है कि आपकी सबसे अच्छी शर्त बाहरीतम अंगूठी के अंदर से खोजना होगा।

मान लें कि आप बाहरी खोजने योग्य ब्रह्मांड में ओस्ट सेट (सबसे लंबी निकटता)। नए ब्रह्मांड के रूप में स्टोर करें और फिर उस ब्रह्मांड में अगला आंतरिक सेट खोजें। इस खोज को ब्रह्मांड से उस आंतरिक सेट को घटा देना चाहिए। पुरानी ब्रह्मांड (बाहरीतम अंगूठी) को स्टोर करें और इस प्रक्रिया को तब तक दोहराएं जब तक कि आप केंद्र को हिट न करें। पहले के बाद प्रत्येक खोज आपके खोज क्षेत्र को कम करेगी और आपको एक अंगूठी देगी।

Answer 2

केंद्रीय भूहाश यानी शीर्ष, दाएं, नीचे और बाएं के आसपास तुरंत पक्षों का निर्माण करके प्रारंभ करें, शुरुआत में इनमें से प्रत्येक में केवल एक ही भूहाश और कोने शामिल होगा। फिर दिशा के साथ निकटवर्ती कार्य का उपयोग करके पक्षों को दोबारा दोहराएं क्योंकि एक उचित परिणाम सेट और अगली पुनरावृत्ति के लिए पक्ष बनाए रखने के दौरान उस तरफ से मेल खाता है (यानी बाईं ओर बाएं विस्तार)। आपको प्रत्येक तरफ के लिए विकर्ण/कोने geohash को संभालने की भी आवश्यकता है (उदा। बाएं-शीर्ष के लिए बाएं-टॉप, ऊपर के लिए शीर्ष दाएं, यदि घड़ी के किनारे सहयोग का उपयोग करते हैं)। प्रक्रिया के उदाहरण के लिए this implementation I did in Lua या Javascript (लेकिन अतिरिक्त कार्यक्षमता के साथ) देखें, जो ग्रिड() को कॉल के साथ शुरू होता है।