1. घर
  2. सवाल और जवाब
  3. 2 डी, सी ++

2 डी, सी ++

2010-11-13 18 views
6

में सभी के निकटतम पड़ोसियों को मुझे डेटा के प्रत्येक बिंदु को अपने निकटतम पड़ोसियों को सेट करने की आवश्यकता है। डेटा सेट में लगभग शामिल हैं। 10 मिलियन 2 डी अंक। डेटा ग्रिड के करीब हैं, लेकिन एक सटीक ग्रिड नहीं बनाते हैं ...2 डी, सी ++

यह विकल्प केडी पेड़ के उपयोग को छोड़कर (मेरी राय में), जहां मूल धारणा कोई बिंदु नहीं है, एक्स एक्स समन्वय और y समन्वय है ।

मुझे इस समस्या को हल करने के लिए एक तेज़ एल्गोरिदम ओ (एन) या बेहतर (लेकिन कार्यान्वयन के लिए बहुत मुश्किल नहीं है) की आवश्यकता है ... इस तथ्य को हल करने के लिए कि बूस्ट मानकीकृत नहीं है, मैं उपयोग नहीं करना चाहता यह ...

अपने जवाब या कोड नमूने के लिए धन्यवाद ...

स्रोत

2010-11-13 Ian

+0

क्या आप जो खोज रहे हैं उसके लिए एक उदाहरण प्रदान कर सकते हैं? –

+0

संभावित डुप्लिकेट [डेटा संरचना की उपयुक्त पसंद और 2 डी में तेज़ के-निकटतम पड़ोसी खोज के लिए एल्गोरिदम] (http://stackoverflow.com/questions/3944649/suitable-choice-of-data- संरचना-and-algorithm-for -फास्ट-के-नजदीकी-पड़ोसी-खोजकर्ता) – ybungalobill

+1

मैं काफी अनुवर्ती नहीं हूं कि आप केडी-पेड़ों का उपयोग क्यों नहीं कर सकते। मैं संक्षेप में बताऊंगा कि मुझे क्या लगता है कि आप कह रहे हैं: मुझे बताएं कि मैं कहां गलत हूं। आपके पास 10 एम विशिष्ट बिंदुओं का एक सेट है। वे एक पूर्णांक ग्रिड पर झूठ नहीं बोलते हैं, लेकिन करीब हैं, उदाहरण के लिए, एक बिंदु (2.01, 1.05) और दूसरा (1.99,1.03) है।क्या आप अंक को स्केल नहीं कर सकते हैं ताकि वे सभी एक पूर्णांक ग्रिड पर रख सकें, और फिर केडी-पेड़ का उपयोग करें? उदाहरण के लिए, ऊपर दिए गए 2 अंक (201,105) और (199,103) हो सकते हैं। – corriganjc

उत्तर

12

मैं निम्नलिखित करना होगा:

  1. अंक के ऊपर एक बड़ा ग्रिड बनाएँ।

  2. रैखिक रूप से बिंदुओं के माध्यम से जाएं, और उनमें से प्रत्येक के लिए, यह पता लगाएं कि कौन सा बड़ा "सेल" है (और उस सेल से जुड़ी सूची में अंक जोड़ें)।

    (यह प्रत्येक बिंदु के लिए निरंतर समय में किया जा सकता है, बस अंक के निर्देशांक के एक पूर्णांक विभाजन करते हैं।)

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

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

यहाँ एक (बदसूरत) पिक स्थिति का वर्णन है:

enter image description here

कोशिकाओं इतना बड़ा (बीच में) और पास के सेल निकटतम 10 अंक को रोकने के लिए के लिए होना चाहिए, लेकिन गणना को तेज करने के लिए काफी छोटा है। आप इसे "हैश-फ़ंक्शन" के रूप में देख सकते हैं जहां आपको एक ही बाल्टी में सबसे नज़दीकी अंक मिलेंगे।

(नोट सख्ती से बोला कि यह नहीं हे (एन) लेकिन बड़े कोशिकाओं के आकार को समायोजित करके, आप काफी निकट मिलना चाहिए। :-)

स्रोत

2010-11-13 11:57:03 aioobe

+4

न केवल आसन्न, दुर्भाग्य से (मान लें कि पूर्व में सेल में दो बिंदु सीधे उत्तर-पूर्व में सेल के बिंदुओं के करीब हो सकते हैं उदाहरण के लिए, यह समस्या उच्च आयामों में बहुत खराब हो जाती है)। इसके अलावा, अगर पड़ोसी कोशिकाओं में 10 से कम अंक होते हैं तो क्या होगा? अभ्यास में, आपको "सर्पिल आउट" करने की आवश्यकता होगी। –

+0

इस विशेष मामले में नहीं: * डेटा ग्रिड के करीब हैं, लेकिन एक सटीक ग्रिड नहीं बनाते हैं ... *। बड़ी पर्याप्त कोशिकाओं को चुनकर, आप इसे इस तरह हल कर सकते हैं। – aioobe

+0

और एलएसएच के बारे में क्या? – Ian

1

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

इस दिलचस्प काम के साथ शुभकामनाएँ!

स्रोत

2010-11-16 11:13:20

संबंधित मुद्दे
नवीनतम प्रश्न

 संबंधित मुद्दे