Сохранение объектов для размещения по координатам x, y

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

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

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

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

Ответ 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);
            }
    }