मेरा मानना है कि मैं एल्गोरिथ्म को काफी समझता हूंस्पष्ट रूप से, उस चरण को छोड़कर, जहां आप यह देखना चाहते हैं कि क्या कोई बिंदु है जो डिवीजन में देखने के करीब है और एक पट्टी बनाएं जहां पट्टी के भीतर अंक उम्मीदवार हैं।
लेकिन फिर एल्गोरिथ्म अंक को सॉर्ट करने के लिए कहता हैउनके y निर्देशांक द्वारा और फिर पट्टी में एक दूसरे बिंदु की जांच करने के लिए यह पता लगाने के लिए कि क्या पहले की तुलना में एक छोटी दूरी है। यह मूल रूप से लगता है जैसे आप स्ट्रिप के भीतर जानवर बल।
उदाहरण के लिए, यहाँ क्या है एल्गोरिदम का परिचय कहा गया है:
तो ऐसा लगता है कि आप बस एक बिंदु लेते हैं और तुलना करते हैंयह निकटतम अंक खोजने के लिए अन्य लोगों के खिलाफ है? फिर y मान द्वारा क्रमबद्ध करना क्यों आवश्यक है? आप पहले से ही उन्हें x द्वारा क्रमबद्ध कर चुके हैं, तो उस के साथ बल क्यों नहीं?
उत्तर:
उत्तर № 1 के लिए 1आप सभी बिंदुओं के विरुद्ध तुलना नहीं करते Y"
लेकिन केवल अगले के खिलाफ p
। यदि वह पहले से ही बहुत दूर है तो आप कर सकते हैंबस रुक जाओ, क्योंकि अन्य सभी बिंदु और भी दूर होंगे। आप केवल अगले निकटतम पड़ोसी का मूल्यांकन करना जारी रखते हैं यदि अंतिम कोई आपकी खोज दूरी के भीतर था।
पाठ में यह समझाता है जैसा कि हम जल्द ही देखेंगे अनुभाग।
छँटाई यहाँ एक अनुकूलन है जो आपको निकटतम पड़ोसियों को पुनरावृत्त करने की अनुमति देता है O(1)
की छँटाई लागत का भुगतान करने के बाद O(n log n)
एक बार।