Хранение объектов для поиска по координатам x, y

Question

Я пытаюсь определить быстрый способ хранения набора объектов, каждый из которых имеет значение координат x и y, чтобы я мог быстро получить все объекты в пределах определенного прямоугольника или круга. Для небольших наборов объектов (~ 100) наивный подход, заключающийся в простом сохранении их в списке и повторении по нему, является относительно быстрым. Тем не менее, для гораздо больших групп, это, как ожидается, медленно. Я попытался сохранить их в паре TreeMaps, один из которых отсортирован по координате x, а другой - по координате y, используя этот код:

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

Это также работает и работает быстрее для больших наборов объектов, но все же медленнее, чем хотелось бы. Часть проблемы также заключается в том, что эти объекты перемещаются и должны быть вставлены обратно в это хранилище, что означает удаление их и повторное добавление в деревья / списки. Я не могу не думать, что там должны быть лучшие решения. Я реализую это на Java, если это будет иметь какое-то значение, хотя я ожидаю, что любое решение будет больше в форме полезного шаблона / алгоритма.

Answer 1

Quadtrees , кажется, решают конкретную проблему, которую я спросил. Kd-Trees - это более общая форма для любого числа измерений, а не только для двух.

R-деревья также могут быть полезны, если сохраняемые объекты имеют ограничивающий прямоугольник, а не просто точку.

Общий термин для структур такого типа: Пространственный индекс .

Существует Java-реализация Quadtree и R-Tree .

Answer 2

Общий термин: Пространственный индекс . Я думаю, вы должны выбрать в соответствии с существующих реализаций .

Answer 3

Квадро - это структура , которая обычно используется для этого.

Answer 4

Простая реализация QuadTree в C # (легко перевести на Java) http://www.codeproject.com/KB/recipes/QuadTree.aspx

Answer 5

Посмотрите на Kd-Trees .

Answer 6

Вы можете поместить все x-шнуры на карту и 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);
            }
    }