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

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

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