Структура данных для упорядочения двумерных точек

#cpp #алгоритм #вычислительная_геометрия

Столкнулся с задачей - имеется достаточно много (ну, скажем, десятки тысяч) точек
на плоскости (возможно, позже будут в трехмерном пространстве, но пока вопрос о плоскости).
Требуется много раз решать подзадачу - выбирать для итераций точки множества, находящиеся
на расстоянии не более чем L от некоторой точки (вообще говоря, не входящей в это множество
точек).

Подскажите, какую структуру данных использовать, чтоб не перебирать все точки подряд.
Не могу даже сообразить, как правильно проГУГЛяться, что именно искать - как запрос
сформулировать.

Рабочий язык - С++.
    

Ответы

Ответ 1

Можно разбить плоскость на квадраты размера L. Для каждого квадрата сохраняем список
попавших в него точек. Для новой точки находим ее квадрат и перебираем содержимое этого,
а также соседних квадратов. Как это сделать эффективно по памяти описано, например,
здесь: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.2471&rep=rep1&type=pdf


Ответ 2

Если задача массовая, т.е. если исходный набор точек стабилен и к этому стабильному
набору точек делается относительно большое количество запросов, то хороший вариант:
евклидова диаграмма Вороного для исходного набора плюс какой-нибудь алгоритм для быстрого
point-location.

Когда на вход приходит точка-запрос, то мы выполняем point-location, чтобы определить,
в какой регион диаграммы Вороного попала точка-запрос. После этого рассматриваем этот
регион Вороного и обходим поиском ширину соседние регионы Вороного до тех пор, пока
мы заведомо не выйдем за радиус L.

Понятное дело, что построение диаграммы Вороного и подготовка к point-location -
это относительно "тяжелый" препроцессинг, по каковой причине, как я сказал выше, такой
подход имеет смысл при стабильном входном наборе и относительно большом количестве
запросов к нему, т.е. когда результаты препроцессинга сохраняют свою актуальность "долго".

Другой вариант - k-d-tree.