Хранение объектов для локации по координатам 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, если это имеет значение, хотя я ожидаю, что любое решение будет в большей степени в форме полезного шаблона / алгоритма.
Ответы 6
Квадродерево - это состав, который обычно используется для этого.
Взгляните на Kd-деревья.
Общий термин - Пространственный индекс. Думаю, стоит выбирать по существующие реализации.
Quadtrees, похоже, решает конкретную проблему, которую я задал. Kd-деревья - это более общая форма для любого количества измерений, а не только для двух.
R-деревья также может быть полезен, если сохраняемые объекты имеют ограничивающий прямоугольник, а не просто точку.
Общий термин для этого типа структур - Пространственный индекс.
Вы можете поместить все шнуры 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);
}
}
Простая реализация QuadTree на C# (легко перевести на java) http://www.codeproject.com/KB/recipes/QuadTree.aspx
Если вы имеете дело с точками на смежной плоскости вместо нескольких отдельных точек, вы можете улучшить это, используя «ведра» определенного размера. Не так хорошо, как четырехугольное дерево, но проще в реализации.