Определение, находится ли точка на дороге

Question

Если у меня есть ломаная линия, которая описывает дорогу, и я знаю ширину дороги на всех участках, есть ли алгоритм, который я могу использовать для определения, находится ли точка на дороге? Я не совсем уверен, как это сделать, так как сама строка имеет ширину 1px.

спасибо,

Jeff

Answer 1

Возможно, вы могли бы взять каждый отрезок, построить прямоугольник отрезка + его ширину и использовать алгоритмы столкновения прямоугольник / точка, чтобы определить, содержит ли прямоугольник точку. Хороший алгоритм будет учитывать сценарий width = 1, который должен просто попытаться построить обратную функцию отрезка и определить, является ли y-1 (point.y) x между line_segment.x1 и line_segment.x2

Answer 2

Найдите минимальное расстояние от точки до линии (это будет вектор, перпендикулярный линии). Фактический расчет, где P0 - первая точка сегмента дороги, v - вектор сегмента дороги, а w - вектор от P0 до рассматриваемой точки. Вам придется перебирать каждое ребро ломаной линии. Если расстояние меньше ширины этого отрезка, то оно «на дороге».

d = |v x w| / |v|

Углы могут быть хитрыми, в зависимости от того, рассматриваете ли вы их как закругленные (постоянный радиус) или угловые.