Objekte zur Ortung nach x, y Koordinaten speichern

Question

Ich versuche einen schnellen Weg zu finden, eine Menge von Objekten zu speichern, die jeweils einen x- und y-Koordinatenwert haben, so dass ich schnell alle Objekte innerhalb eines bestimmten Objekts abrufen kann Rechteck oder Kreis. Für kleine Mengen von Objekten (~ 100) ist der naive Ansatz, sie einfach in einer Liste zu speichern und zu durchlaufen, relativ schnell. Für viel größere Gruppen ist dies jedoch erwartungsgemäß langsam. Ich habe versucht, sie in einem Paar treemaps auch, ein sortiert auf der x-Koordinate und einer sortiert auf der y-Koordinate, mit diesem Code zu speichern:

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

Dies funktioniert auch, und ist schneller für größere Sätze von Objekten, aber ist immer noch langsamer als ich es möchte. Ein Teil des Problems besteht auch darin, dass diese Objekte sich bewegen und wieder in diesen Speicher eingefügt werden müssen, was bedeutet, dass sie aus den Bäumen/Listen entfernt und wieder hinzugefügt werden. Ich kann nicht anders, als zu denken, dass es bessere Lösungen geben muss. Ich implementiere dies in Java, wenn es einen Unterschied macht, obwohl ich erwarte, dass jede Lösung mehr in Form eines nützlichen Musters/Algorithmus vorliegt.

Answer 1

A quadtree ist die structure, die normalerweise dafür verwendet wird.

Answer 2

Werfen Sie einen Blick auf Kd-Trees.

Answer 3

Der allgemeine Begriff ist ein Spatial Index. Ich denke, Sie sollten nach der existing implementations wählen.

Answer 4

Quadtrees scheinen das spezifische Problem zu lösen, das ich fragte. Kd-Trees sind eine allgemeinere Form für eine beliebige Anzahl von Dimensionen, anstatt nur zwei.

R-Trees kann auch nützlich sein, wenn die Objekte, die gespeichert werden, ein begrenzendes Rechteck haben und nicht nur ein einfacher Punkt.

Der allgemeine Ausdruck für diese Art von Strukturen ist Spatial Index.

Es gibt eine Java-Implementierung von Quadtree und R-Tree.

Answer 5

Sie könnten alle x-Kabel in eine Karte und die y-Kabel in eine andere Karte einfügen und die Kartenwerte auf das Objekt zeigen lassen.

 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

Einfache Quadtree Implementierung in C# http://www.codeproject.com/KB/recipes/QuadTree.aspx