Столкнулся с задачей - имеется достаточно много (ну, скажем, десятки тысяч) точек на плоскости (возможно, позже будут в трехмерном пространстве, но пока вопрос о плоскости). Требуется много раз решать подзадачу - выбирать для итераций точки множества, находящиеся на расстоянии не более чем L от некоторой точки (вообще говоря, не входящей в это множество точек).
Подскажите, какую структуру данных использовать, чтоб не перебирать все точки подряд. Не могу даже сообразить, как правильно проГУГЛяться, что именно искать - как запрос сформулировать.
Рабочий язык - С++.
Ответ
Можно разбить плоскость на квадраты размера L. Для каждого квадрата сохраняем список попавших в него точек. Для новой точки находим ее квадрат и перебираем содержимое этого, а также соседних квадратов. Как это сделать эффективно по памяти описано, например, здесь: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.2471&rep=rep1&type=pdf
Комментариев нет:
Отправить комментарий