एक्स से पता लगाने के लिए वस्तुओं भंडारण, वाई निर्देशांक

Question

मैं वस्तुओं, जिनमें से प्रत्येक एक एक्स है और y मूल्य समन्वय, ऐसा है कि मैं जल्दी से एक निश्चित भीतर सभी वस्तुओं प्राप्त कर सकते हैं का एक सेट को संग्रहीत करने का तेज़ तरीका निर्धारित करने के लिए कोशिश कर रहा हूँ आयताकार या सर्कल। ऑब्जेक्ट्स के छोटे सेट (~ 100) के लिए उन्हें सूची में संग्रहित करने का मूर्ख दृष्टिकोण, और इसके माध्यम से पुनरावृत्ति, अपेक्षाकृत तेज़ है। हालांकि, बहुत बड़े समूहों के लिए, यह अपेक्षाकृत धीमी है। मैं उन्हें ट्री-मैप की एक जोड़ी में भंडारण के रूप में अच्छी तरह की कोशिश की है, एक पर एक्स अनुसार क्रमबद्ध समन्वय, और एक y पर छाँटे गए समन्वय, इस कोड का उपयोग:

xSubset = objectsByX.subSet(minX, maxX); 
ySubset = objectsByY.subSet(minY, maxY); 
result.addAll(xSubset); 
result.retainAll(ySubset); 

यह भी काम करता है, और बड़े के लिए तेजी से होता है वस्तुओं के सेट, लेकिन मैं अभी भी धीमा है जितना मैं चाहता हूँ। समस्या का एक हिस्सा यह भी है कि ये वस्तुएं घूमती हैं, और इस भंडारण में वापस डालने की आवश्यकता होती है, जिसका अर्थ है उन्हें उन्हें हटाने और पेड़/सूचियों में दोबारा जोड़ना। मैं मदद नहीं कर सकता लेकिन लगता है कि वहाँ बेहतर समाधान होना चाहिए। मैं जावा में इसे कार्यान्वित कर रहा हूं, अगर इससे कोई फर्क पड़ता है, हालांकि मुझे उम्मीद है कि कोई समाधान उपयोगी पैटर्न/एल्गोरिदम के रूप में अधिक होगा।

Answer 1

A quadtreestructure जो आम तौर पर उस के लिए प्रयोग किया जाता है।

Answer 2

Kd-Trees पर एक नज़र डालें।

Answer 3

सामान्य शब्द Spatial Index है। मुझे लगता है कि आपको existing implementations के अनुसार चयन करना चाहिए।

Answer 4

Quadtrees मैंने पूछा कि विशिष्ट समस्या को हल करने लगते हैं। Kd-Trees केवल दो से अधिक आयामों की किसी भी संख्या के लिए, अधिक सामान्य रूप हैं।

R-Trees भी उपयोगी यदि वस्तुओं बल्कि सिर्फ एक सरल बिंदु होने से, संग्रहीत किया जा रहा बाउंडिंग आयत है हो सकता है।

इन प्रकार की संरचनाओं के लिए सामान्य शब्द Spatial Index है।

Quadtree और R-Tree की एक जावा कार्यान्वयन नहीं है।

Answer 5

आप सभी एक्स तारों को मानचित्र में रख सकते हैं, और y अन्य तारों में y तारों को रख सकते हैं, और नक्शा मान वस्तु को इंगित कर सकते हैं।

 TreeMap<Integer, TreeMap<Integer, Point>> xMap = new TreeMap<Integer, TreeMap<Integer, Point>>(); 
     for (int x = 1; x < 100; x += 2) 
      for (int y = 0; y < 100; y += 2) 
       { 
        Point p = new Point(x, y); 
        TreeMap<Integer, Point> tempx = xMap.get(x); 
        if (tempx == null) 
         { 
          tempx = new TreeMap<Integer, Point>(); 
          xMap.put(x, tempx); 
         } 
        tempx.put(y, p); 
       } 
     SortedMap<Integer, TreeMap<Integer, Point>> tempq = xMap.subMap(5, 8); 
     Collection<Point> result = new HashSet<Point>(); 
     for (TreeMap<Integer, Point> smaller : tempq.values()) 
      { 
       SortedMap<Integer, Point> smallerYet = smaller.subMap(6, 12); 
       result.addAll(smallerYet.values()); 
      } 
     for (Point q : result) 
      { 
       System.out.println(q); 
      } 
    } 

Answer 6

सी # में सरल QuadTree कार्यान्वयन (आसान जावा में अनुवाद करने) http://www.codeproject.com/KB/recipes/QuadTree.aspx