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

Question

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

Спасибо,

Джефф

Answer 1

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

d = |v x w| / |v|

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

Answer 2

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