Stockage d'objets pour la localisation par coordonnées x, y

Question

J'essaie de déterminer un moyen rapide de stocker un ensemble d'objets, dont chacun a une valeur de coordonnées x et y, de sorte que je puisse récupérer rapidement tous les objets dans un certain rectangle ou cercle. Pour les petits ensembles d'objets (~ 100), l'approche naïve consistant à simplement les stocker dans une liste et à les parcourir est relativement rapide. Cependant, pour des groupes beaucoup plus importants, cela devrait être lent. J'ai essayé de les stocker dans une paire de TreeMaps ainsi, une triées sur le coordonnée x et une triées sur le coordonnée y, en utilisant ce code:

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

Cela fonctionne aussi, et est plus rapide pour agrandir ensembles d'objets, mais est encore plus lent que je le voudrais. Une partie du problème est également que ces objets se déplacent et doivent être réinsérés dans ce stockage, ce qui signifie qu'ils doivent être supprimés et ajoutés de nouveau aux arbres/listes. Je ne peux m'empêcher de penser qu'il doit y avoir de meilleures solutions. J'implémente ceci en Java, si cela fait une différence, même si je m'attends à ce que toute solution soit plus sous la forme d'un modèle/algorithme utile.

Answer 1

A quadtree est le structure qui est habituellement utilisé pour cela.

Answer 2

Jetez un oeil à Kd-Trees.

Answer 3

Le terme général est un Spatial Index. Je suppose que vous devriez choisir selon le existing implementations.

Answer 4

Quadtrees semblent résoudre le problème spécifique que j'ai demandé. Kd-Trees sont une forme plus générale, pour n'importe quel nombre de dimensions, plutôt que seulement deux.

R-Trees peut également être utile si les objets stockés ont un rectangle de délimitation, plutôt que d'être simplement un simple point.

Le terme général pour ce type de structure est Spatial Index. Il existe une implémentation Java de Quadtree et de R-Tree.

Answer 5

Vous pouvez placer tous les cordons x dans une carte et les cordons y dans une autre carte et faire pointer les valeurs de la carte sur l'objet.

 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

simple mise en œuvre de QuadTree en C# (facile à traduire en java) http://www.codeproject.com/KB/recipes/QuadTree.aspx