Какой алгоритм для определения ближайшего отрезка пути к точке?

Question

[Developer]

Дан путь на карте в виде упорядоченного набора точек.
Есть точка, которая движется по этому пути, но с некоторой погрешностью.
Необходимо определить ближайший участок пути (сегмент, ребро) к заданной точке.
Задача сначала казалась простой, но потом всплыли подводные камни. Думаю, что есть уже существующий алгоритм, но какой? Диаграмы Вороного? Триангуляция Делоне?

Answer 1

[Developer]

Кажется, нашёл ответ.
Надо использовать BSP-дерево https://en.wikipedia.org/wiki/Binary_space_partitioning
stackoverflow.com/questions/3423852/algorithm-to-f...
и ещё варианты на выбор:
https://gist.github.com/mbostock/8027637
stackoverflow.com/questions/18900642/get-point-on-...

Answer 2

[Vitaliy]

Найти расстояния ко всем точкам, соседние отрезки к самой ближней точке и перпендикуляр к одной из них. Если такой существует - ответом будет длина этого перпендикуляра, иначе - расстояние к ближайшей точке

Answer 3

[xmoonlight]

нормаль к прямой (или проекция точки на прямую): отрезок от точки до пересечения с прямой под углом 90 градусов к этой прямой.

Comments

[Developer]

Можно подробнее? Там есть подводные камни

[xmoonlight]

samodum: какие камни? можно подробнее пояснить, желательно графически.

[Developer]

xmoonlight: см ниже

[xmoonlight]

samodum: использовать B или C для отображения - выясняется по наличию точки отрезка пути на этой прямой. Т.е. в данном примере, точка конца отрезка нормали к прямой b не входит в отрезок пути. Выбираем C.
Если подобных C - несколько, тогда выбираем кратчайшую нормаль.
Остались еще вопросы?

[Developer]

xmoonlight: ты не все варианты рассматриваешь. Поэтому я ищу готовый алгоритм, а не то, что первое приходит в голову. Ибо все решения неверные.
Вот тебе ситуация, где твой вариант сломается

[Developer]

xmoonlight: можешь картинками объяснять свои варианты?

[Сергей]

Необходимо проверять касается ли нормаль опущенная на отрезок самого отрезка. Если нет, то "минимальный" результат не засчитывается.

[xmoonlight]

samodum: При равном удалении объекта от соседних отрезков пути (длин нормалей: DE и DF), нужно посчитать расстояние от этих точек (E,F) к предыдущей отметке на отрезке пути - (для примера) точка C. Наименьшее расстояние из всех вариантов (CE меньше CF) - выбираем прямую a. Соответственно верной позицией будет точка E.

[xmoonlight]

Сергей: я до картинки написал это же) выше...

[Developer]

xmoonlight: а это ТОЧНО будет работать? А то у меня ещё миллион вариантов есть. Не миллиард, но всё же

[Developer]

xmoonlight: ПОДСКАЗКА: представь, что вся область забита точками. Вопрос: какие из этих точек будут принадлежать какому отрезку.

[xmoonlight]

samodum: легко: связанные рёбра графа, вершинами которого являются эти точки. Нельзя перейти на любое ребро, если его ID не является текущим или следующим (по отношению к текущему). Текущее ребро - определяется последней позицией объекта на трэке.

[Developer]

Сергей: как быть, если нормали к нескольким сегментам лежит на самих этих отрезках? Какой выбирать?
Как быть, если нормали ко всем сегментам лежат за пределами отрезков? А какой-то сегмент надо всё равно выбрать.
Я же говорю - ситуаций море

[xmoonlight]

samodum: "как быть, если нормали к нескольким сегментам лежит на самих этих отрезках? Какой выбирать?" у которого ID больше, чем у предыдущего на 1-цу.
"Как быть, если нормали ко всем сегментам лежат за пределами отрезков? А какой-то сегмент надо всё равно выбрать."
Кратчайшее расстояние от конца точки нормали до последнего местоположения объекта и текущий (или следующий, по отношению к текущему) ID отрезка пути (ребра графа).

[xmoonlight]

samodum: т.е. суммируя (отрезок пути ограниченный двумя точками - ребро графа):
1. всегда смотрим текущий сегмент графа: текущее ребро и следующие рёбра за ним.
2. всегда опускаем нормаль от полученных координат на текущее и следующие рёбра графа
3. лимит глубины проверки: анализируем по возможной максимальной скорости и расстоянию
4. находим кратчайшую длину нормали, из всех нормалей, точки которых находятся на текущем или следующим за текущим (в графе) участках пути.
5. определяем минимальное путевое расстояние от последнего местоположения объекта до найденной кратчайшей точки нормали.

[Developer]

>"у которого ID больше, чем у предыдущего на 1-цу."
Это не спортивно. А если все сегменты неупорядочены?

[Developer]

xmoonlight: есть вариант C, когда нормаль не лежит ни на одном из отрезков, но при этом точка находится очень близко от пути

[Developer]

xmoonlight: опять ты не всё предусмотрель. Да что ж такое то!

[xmoonlight]

samodum: " А если все сегменты неупорядочены? " - я имел ввиду: примыкающий отрезок пути к текущему с любой из сторон: присоединённые рёбра графа к текущему ребру.
"есть вариант C, когда нормаль не лежит ни на одном из отрезков, но при этом точка находится очень близко от пути":