Алгоритм нахождения ближайшего сегмента к точке среди множества сегментов (обратное геокодирование)

Question

У меня есть набор сегментов, определяемых двумя точками.Учитывая точку, как я могу обнаружить ближайший сегмент к такой точке?

Я уже написал алгоритм, который вычисляет расстояние между точкой и сегментом.В любом случае вычисление такого расстояния для каждого сегмента, а затем выбор сегмента с наименьшим расстоянием не очень эффективно: (

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

ОГРОМНОЕ СПАСИБО!

Answer 1

Используйте метод разбиения сетки двоичного пространства, дерева kd, quadtree или аналогичного метода. Затем, начиная с древовидной ячейки, в которой находится ваша точка, начинайте исследовать сегменты, пока расстояние от точки до ячейки, содержащей сегмент, не превысит наименьшее расстояние, найденное до сих пор.

http://en.wikipedia.org/wiki/Binary_space_partitioning

(Это, конечно, при условии, что сегменты / улицы меняются очень редко, но у вас есть много точек для поиска).