Almacenamiento de objetos para localizar por coordenadas x, y

Question

Estoy tratando de determinar una forma rápida de almacenar un conjunto de objetos, cada uno de los cuales tiene un valor de coordenada xey, de modo que pueda recuperar rápidamente todos los objetos dentro de un determinado rectángulo o círculo Para pequeños conjuntos de objetos (~ 100), el enfoque ingenuo de simplemente almacenarlos en una lista y repetirlos es relativamente rápido. Sin embargo, para grupos mucho más grandes, se espera que sea lento. He intentado almacenándolos en un par de TreeMaps así, uno ordenados en la coordenada x, y uno ordenados en la coordenada y, utilizando este código:

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

Esto también funciona, y es más rápido para mayor conjuntos de objetos, pero aún es más lento de lo que quisiera. Parte del problema es que estos objetos se mueven y deben insertarse de nuevo en este almacenamiento, lo que significa eliminarlos y volver a agregarlos a los árboles/listas. No puedo evitar pensar que debe haber mejores soluciones. Estoy implementando esto en Java, si hace alguna diferencia, aunque espero que cualquier solución tenga más la forma de un patrón/algoritmo útil.

Answer 1

A quadtree es el structure que generalmente se utiliza para eso.

Answer 2

Eche un vistazo a Kd-Trees.

Answer 3

El término general es Spatial Index. Supongo que debes elegir de acuerdo con existing implementations.

Answer 4

Quadtrees parecen resolver el problema específico que pregunté. Kd-Trees son una forma más general, para cualquier cantidad de dimensiones, en lugar de solo dos.

R-Trees también puede ser útil si los objetos que se almacenan tienen un rectángulo delimitador, en lugar de ser simplemente un punto simple. El término general para este tipo de estructuras es Spatial Index.

Hay una implementación de Java de Quadtree y R-Tree.

Answer 5

Puede poner todos los cordones x en un mapa, y los cordones y en otro mapa, y hacer que los valores del mapa apunten al objeto.

 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

aplicación árbol cuádruple simple en C# (fácil de traducir en java) http://www.codeproject.com/KB/recipes/QuadTree.aspx