Хранение объектов для локации по координатам 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, если это имеет какое-то значение, хотя я ожидаю, что любое решение будет в большей степени в форме полезного шаблона / алгоритма.


java tree spatial quadtree
person Derek Lewis    schedule 25.09.2008    source источник

Ответы (6)


arrow_upward
14
arrow_downward

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

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

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

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

person Derek Lewis    schedule 25.09.2008

arrow_upward
4
arrow_downward

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

person Yuval F    schedule 25.09.2008

arrow_upward
2
arrow_downward

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

person Vinko Vrsalovic    schedule 25.09.2008

arrow_upward
1
arrow_downward

Взгляните на Kd-Trees.

person Torsten Marek    schedule 25.09.2008

arrow_upward
1
arrow_downward

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

person Blue Toque    schedule 30.08.2009

arrow_upward
0
arrow_downward

Вы можете поместить все шнуры 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);
            }
    }
person Milhous    schedule 25.09.2008
comment
Если вы имеете дело с точками на смежной плоскости вместо нескольких отдельных точек, вы можете улучшить это, используя ведра определенного размера. Не так хорошо, как четырехугольное дерево, но проще в реализации. - person Paul Tomblin; 19.11.2008