कौन सी डेटा संरचना "पॉइंट पी से दूरी डी के भीतर सभी बिंदुओं" के लिए उपयुक्त है

Question

मेरे पास 3 डी पॉइंटक्लाउड है और मैं एक मनमानी बिंदु पी से दूरी डी के भीतर सभी बिंदुओं को कुशलता से पूछना चाहता हूं (जो अनिवार्य रूप से हिस्सा नहीं है संग्रहीत pointcloud)

क्वेरी लगेगा

Pointcloud getAllPoints(Point p, float d); 

की तरह कुछ क्या accelerationstructure इस के लिए उचित होगा? एक रेंज-पेड़ केवल आयताकार वॉल्यूम पूछताछ के लिए उचित प्रतीत होता है, क्षेत्र की मात्रा नहीं (निश्चित रूप से मैं क्षेत्र के बाउंडिंगबॉक्स से पूछताछ कर सकता हूं और फिर उन सभी शीर्षकों को हल कर सकता हूं जिनमें डी से बड़ी दूरी है - लेकिन शायद ऐसा करने का एक बेहतर तरीका है यह ??)

धन्यवाद! ,

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance) 
SearchStructure Remove(Point p) 
SearchStructure Insert(Point p) 
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points 

आमतौर पर n प्रश्नों के बाद, अंक विस्थापित हो और कुछ (बहुत सारे!) सम्मिलन और विलोपन बना रहे हैं:

Novelocrats सुझाव के अनुसार, मैं संरचना के वांछित कार्यों को परिभाषित करने की कोशिश । ऑफसेट वैक्टर सभी बिंदुओं के बाउंडिंगबॉक्स की तुलना में बहुत छोटे हैं

Answer 1

दूरी और मूल्य के बराबर कुंजी वाला एक बिंदु पॉइंट स्वयं ही आपको किसी दिए गए दूरी से कम या किसी दिए गए सीमा के भीतर सभी बिंदुओं के लिए क्वेरी करने की अनुमति देगा।

Answer 2

अच्छा, यह डेटा संरचना के लिए आपको आवश्यक अन्य उपयोगों पर निर्भर करता है।

आप बिंदु से दूसरे बिंदुओं तक दूरी की एक सूची प्राप्त कर सकते हैं, दूरी से आदेश दिया गया है, और इन सूचियों को हैशपैप के साथ बिंदुओं पर मानचित्रित कर सकते हैं।

map: 
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}] 
p2 -> ... 
... 

आप मानचित्र में बिंदु देख सकते हैं, और जब तक दूरी की आवश्यकता से अधिक हो तब तक सूची को फिर से चालू करें।

Answer 3

आप जो चाहते हैं वह एक संरचना है जो अंतरिक्ष को विघटित करती है ताकि विशेष क्षेत्रों को कुशलता से पाया जा सके। एक उचित ढंग से विघटित ऑक्टेट या केडी-पेड़ आपको यह अच्छी तरह से करने की अनुमति देनी चाहिए, क्योंकि आप अपने बिंदु p वाले पेड़ के अनुभाग को केवल 'खुले' बिंदुओं को देखने के लिए 'खुले' करेंगे। इससे आपको दूरी की तुलना करने के लिए कितने अतिरिक्त अंक की आवश्यकता होती है, इस पर काफी कम एसिम्प्टोटिक लगाया जाना चाहिए (यह जानते हुए कि कुछ स्तर के अपघटन के नीचे, सभी बिंदु पर्याप्त हैं)। दुर्भाग्यवश, मुझे इस क्षेत्र में साहित्य को और अधिक विस्तृत पॉइंटर्स देने के लिए पर्याप्त जानकारी नहीं है। इन चीजों के साथ मेरा मुठभेड़ बार्न्स-हट एन-बॉडी सिमुलेशन एल्गोरिदम से है।

यहां another question इस से निकटता से संबंधित है। और another। और a third, एक डेटा संरचना (हिल्बर्ट आर-पेड़) का जिक्र करते हुए जिसे मैंने पहले नहीं सुना था।

Answer 4

मैं आपके एपीआई को समझ नहीं पा रहा हूं, आप पॉइंट क्लाउड में सभी बिंदुओं को गोल कर सकते हैं जो मनमानी क्षेत्र के अंदर स्थित हैं, लेकिन आप यह भी कहते हैं कि बिंदु-बादल संग्रहीत हैं? उस स्थिति में आपको प्वाइंट क्लाउड्स की एक सूची नहीं मिलनी चाहिए जो कि दिए गए क्षेत्र के अंदर है, अन्यथा प्वाइंट क्लाउड को संग्रहीत करने के साथ बिंदु (बहाना बहाना) क्या है?

एपीआई को पहले से परिभाषित करने की कोशिश करने के बजाय, इसे आवश्यकता होने पर इसे परिभाषित करें। ऐसा कुछ भी लागू करने की आवश्यकता नहीं है जिसका कभी भी उपयोग नहीं किया जाएगा, अकेले ऐसे फ़ंक्शन को अनुकूलित करें जो कभी नहीं कहा जाएगा (जब तक कि यह बिल्कुल मजेदार नहीं है :))।

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

Answer 5

VTK मदद कर सकते हैं: नियमित रूप से बाल्टी, केडी-पेड़, और octrees:

vtkAbstractPointLocator की

void vtkAbstractPointLocator::FindPointsWithinRadius (
double R, double x, double y, double z, vtkIdList * result
)

उपवर्गों खोज त्वरण के लिए विभिन्न डेटा संरचनाओं होते हैं।

Answer 6

A Template for the Nearest Neighbor Problem (Larry Andrews at DDJ) पर एक नज़र डालें। इसकी केवल 2 डी है, जिसमें ओ (लॉग एन) की एक वापसी की जटिलता है, लेकिन इसे 3 डी के लिए भी अपनाया जा सकता है।