7

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

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

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

4
  • 1
    Может R tree? 11 июл 2016 в 17:24
  • @AlexanderPetrov Спасибо, посмотрю.
    – Harry
    11 июл 2016 в 18:39
  • 1
    Если точки относительно компактно расположены и проверяемая точка отстоит также относительно недалеко, то может быть обычная матрица? Если точка в ячейке есть, то значение "1", если нет - "0". Поиск тогда сведётся к перебору ячеек матрицы в радиусе L. Заполнение матрицы новыми точками также будет простым.
    – user177227
    11 июл 2016 в 18:51
  • @alexis031182 Хм... тоже вариант :) Спасибо!
    – Harry
    11 июл 2016 в 19:35

2 ответа 2

5

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

4

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

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

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

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

1
  • Вообще-то говоря, набор точек потом планируется изменять...
    – Harry
    11 июл 2016 в 18:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.