किसी दिए गए बिंदु पर निकटतम बिंदु

Question

मेरे पास 2 डी छवि में यादृच्छिक रूप से चयनित पिक्सल का सेट सेट है। छवि में हर दूसरे पिक्सेल के लिए मुझे यह पता लगाना होगा कि सेट के में कौन सा पिक्सेल इसके निकट है (मानक वर्ग (डीएक्स^2 + डीई^2) दूरी का माप)। मुझे पता है कि प्रत्येक पिक्सेल के लिए एक से अधिक समाधान हो सकते हैं। जाहिर है यह सेट में प्रत्येक पिक्सेल के खिलाफ ब्रूट फोर्स द्वारा किया जा सकता है, लेकिन मैं इसके बजाय इसे टालना चाहूंगा क्योंकि यह कुशल नहीं है। कोई अन्य अच्छा सुझाव?

चीयर्स।

Answer 1

यह मत भूलना कि आपको वर्ग रूट से परेशान करने की आवश्यकता नहीं है।

यदि आप केवल निकटतम (और यह वास्तविक दूरी नहीं है) ढूंढना चाहते हैं तो बस dx^2 + dy^2 का उपयोग करें, जो आपको प्रत्येक आइटम के लिए दूरी की दूरी प्रदान करेगा, जो कि उतना ही उपयोगी है।

यदि आपके पास पिक्सल की इस सूची को लपेटने वाली कोई डेटा संरचना नहीं है, तो आपको बस उन सभी के खिलाफ परीक्षण करना होगा।

यदि आपके पास कुछ लचीलापन है, तो वर्कलोड को कम करने के अच्छे तरीके हैं। Quadtree बनाएं, या अपनी खोज को और अधिक तेज़ी से संकीर्ण करने के लिए पिक्सल की क्रमबद्ध सूची (x द्वारा क्रमबद्ध और वाई द्वारा क्रमबद्ध) रखें।

Answer 2

इसे निकटतम पड़ोसी खोज कहा जाता है। डोनाल्ड Knuth इसे पोस्ट ऑफिस की समस्या कहा जाता है।

कई समाधान हैं: रैखिक खोज, इलाके संवेदनशील संवेदनशील हैशिंग, वेक्टर सन्निकटन फ़ाइलें और स्थान विभाजन।

उन लोगों को गुगल करने में मदद करनी चाहिए।

Answer 3

इस ग्राफिक को पिक्सल से कितना घना भरा है, इस पर निर्भर करता है कि आप अपने पिक्सेल के मूल से बाहर की खोज से बेहतर हो सकते हैं।

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

Answer 4

एक अन्य संकेत: दूरी हमेशा से अधिक या प्रत्येक समन्वय के अंतर के बराबर, और हमेशा से कम या उनकी राशि के बराबर है, यानि कि

d >= dx, d >= dy, d <= dx + dy. 

यह और अधिक कुशलता से छँटाई मदद कर सकता है तुम क्या कर।

Answer 5

है कि आप क्या करने की कोशिश कर रहे हैं का निर्माण एक voronoi diagram इस हे में किया जा सकता (एन एन लॉग इन करें) एक plane sweep

Answer 6

का उपयोग कर Voronoi Diagrams के निर्माण Computational Geometry की एक शाखा है। Delaunay Triangulations के निर्माण में समान विचार शामिल हैं। आप अपनी आवश्यकताओं के अनुरूप निम्नलिखित Delaunay algorithms में से एक को अनुकूलित करने में सक्षम हो सकते हैं।

• फ्लिप एल्गोरिदम
• इंक्रीमेंटल
• फूट डालो और जीत
• Sweepline

Answer 7

एक केडी पेड़ में अंक रखो, के बाद यह यह निकटतम पड़ोसी को खोजने के लिए बहुत तेजी से है।विवरण के लिए विकिपीडिया पर this आलेख देखें।

Answer 8

मुझे Voronoi Diagram बनाने के साथ जेके और ईवान से सहमत होना होगा। यह बहुभुज में अंतरिक्ष का विभाजन करेगा। के प्रत्येक बिंदु में बहुभुज होगा जो सभी बिंदुओं का वर्णन करता है जो इसके सबसे नज़दीक हैं। अब जब आप किसी बिंदु की क्वेरी प्राप्त करते हैं, तो आपको यह पता लगाना होगा कि यह किस बहुभुज में है। इस समस्या को Point Location कहा जाता है और Trapezoidal Map का निर्माण करके हल किया जा सकता है।

जेके पहले से ही Voronoi Diagram के निर्माण से Fortune's algorithm का उपयोग कर जुड़ा हुआ है जो ओ (एन लॉग एन) कम्प्यूटेशनल चरणों और लागत ओ (एन) स्पेस लेता है। This website आपको दिखाता है कि ट्रैपेज़ॉयडल मानचित्र कैसे बनाएं और इसे कैसे पूछें। (एन एन लॉग इन करें)
अपेक्षित अंतरिक्ष जटिलता हे: हे (एन)

लेकिन सबसे महत्वपूर्ण उम्मीद क्वेरी समय: (एन लॉग इन करें) हे तुम भी वहाँ कुछ सीमा पा सकते हैं:
अपेक्षित निर्माण समय। केडी-पेड़ के ओ (√ एन) से यह (सैद्धांतिक रूप से) बेहतर है।

मेरा स्रोत (उपरोक्त लिंक के अलावा) है: Computational Geometry: algorithms and applications, अध्याय छः और सात।

वहां आपको दो डेटा संरचनाओं (विस्तृत प्रमाण सहित) के बारे में विस्तृत जानकारी मिल जाएगी। Google पुस्तकें संस्करण में केवल आपके लिए आवश्यक चीज़ों का एक हिस्सा है, लेकिन अन्य लिंक आपके उद्देश्य के लिए पर्याप्त होना चाहिए। अगर आप उस तरह की चीज़ में रुचि रखते हैं तो बस किताब खरीदें (यह एक अच्छी किताब है)।