java - saber - Almacenar objetos para ubicar por coordenadas x, y

lector de coordenadas

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 cierto rectángulo o círculo. Para pequeños conjuntos de objetos (~ 100), el enfoque ingenuo de simplemente almacenarlos en una lista e iterar a través de ellos es relativamente rápido. Sin embargo, para grupos mucho más grandes, se espera que sea lento. Intenté también almacenarlos en un par de TreeMaps, uno ordenó la coordenada xy otro ordenó la coordenada y con 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 conjuntos más grandes de objetos, pero aún es más lento de lo que quisiera. Parte del problema también 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 sea más en la forma de un patrón / algoritmo útil.

Answer 1

Eche un vistazo a Kd-Trees .

Answer 2

El término general es un índice espacial . Supongo que deberías elegir según las implementaciones existentes .

Answer 3

Puede poner todos los cables x en un mapa, y los cables 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 4

Los Quadtrees parecen resolver el problema específico que pedí. Los 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 el Índice espacial .

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

Answer 5

Un quadtree es la estructura que generalmente se usa para eso.

Answer 6

Implementación simple de QuadTree en C # (fácil de traducir a Java) http://www.codeproject.com/KB/recipes/QuadTree.aspx