आयताकार सीमाओं के अंदर कुशल बिंदु

Question

मैं एक वेक्टर मैप संपादक पर काम कर रहा हूं और मेरे पास तत्वों का एक समूह है, जिनमें से प्रत्येक दृश्य में बाध्यकारी बॉक्स निर्दिष्ट करता है। जैसे ही माउस चलता है मैं को पहले तत्व पर हाइलाइट करना चाहता हूं जिसका बाउंडिंग बॉक्स वर्तमान माउस स्थान है। अभी मैं एक साधारण सूची का उपयोग करता हूं और इसके माध्यम से जाता हूं, लेकिन तत्वों की संख्या में वृद्धि होने की संभावना है, वर्तमान खोज एल्गोरिदम की ओ (एन) जटिलता एक इंटरैक्टिव एप्लिकेशन के लिए समस्याग्रस्त हो जाएगी।

इसके लिए बेहतर एल्गोरिदम/डेटा संरचना क्या होगी?

कुछ अतिरिक्त की कमी/आवश्यकताओं:

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

Answer 1

पुस्तकों के माध्यम से ब्राउज़ करने के बाद, मुझे Computational Geometry पुस्तक (पृष्ठ 237) में एक उत्तर मिला है। इस प्रकार की खोज को अक्सर स्टैबिंग क्वेरी के रूप में जाना जाता है और आमतौर पर segment trees का उपयोग करके लागू किया जाता है।

जटिलताओं:

• क्वेरी: हे (log2n + k), जहां कश्मीर की सूचना दी बाउंडिंग बक्से की संख्या
• डेटा संरचना हे का उपयोग करता है (एन * लोग इन एन) भंडारण
• संरचना ओ (एन * लॉग एन) समय

Answer 2

यदि आप अपने तत्वों को निम्न x-location से सॉर्ट करते हैं, तो आप एक निश्चित बिंदु से पहले सभी तत्वों को छोड़ सकते हैं। यदि आपके पास ऊपरी एक्स-लोकेशन के साथ दूसरी सूची है, तो आप जानते हैं कि आपका काम कब किया जाता है।

एक और विचार: पूरे क्षेत्र को 100x100 भागों में विभाजित करने के लिए एक ग्रिड बनाएं। अब एक बार पता लगाना है, जिसमें अपने ग्रिड के कुछ हिस्सों एक आंकड़ा ओवरलैपिंग है:

5 
4 
3 xx 
2 xxxx 
1 xx 
0 
0 1 2 3 4 5 

यह आंकड़ा यह होगा (1,1) के लिए, (1,2) (2,2) (2,3) एक्स * वाई सूची के मानचित्र में अब 4 स्थानों (1,1) -> एस, (1,2) -> एस, ...

के लिए यह आकार एस होगा, यदि आपके पास शायद ही कभी सम्मिलन/हटाना है , लेकिन अक्सर तुलना, यह आपकी खोजों को गति देगा। आप केवल एक निश्चित सेल से जुड़े आकृतियों का दौरा करेंगे, और इनके लिए सटीक निर्देशांक की जांच करेंगे।

Answer 3

लुकअप टेबल: उपयोगकर्ता स्क्रीन पर उसी क्षेत्र में वापस जाते हैं (इसलिए मार्जिन विज़िट दर आमतौर पर कम होती है, और केंद्र यात्रा दर आमतौर पर अधिक होती है)। इसलिए हम अपने प्रदर्शन को बेहतर बनाने के लिए इस ज्ञान का उपयोग कर सकते हैं। हे
एक बार (पाने की किसी भी अन्य विधि हो सकता है) आप एक सूची है, और अगली बार जब उपयोगकर्ता एक ही जगह का दौरा के रूप में परिणाम को कैश कर सकते एक बिंदु पाने के बाद, देखने होगा (1)। एक बार नया आकार जोड़ा जाने के बाद आपको कैश को डंप करने की आवश्यकता होगी।

एक और संभावना Observer Pattern उपयोग कर रहा है, प्रत्येक नया आकार आवश्यक अंक में खुद को पंजीकृत करेंगे (यह महंगा हो सकता है, कितना आकार डालने अक्सर होता है ... पर निर्भर करता है) और एक बार माउस इस मुद्दे पर है, यह सब करना पड़ता है जो भी इस बिंदु पर पंजीकृत है कॉल करें।

तीसरी संभावना निश्चित रूप से आपके खोज क्षेत्र को काटकर @user अज्ञात सुझाव दिया गया है।इस संभावना को लुकअप टेबल के साथ जोड़ा जा सकता है।