Алгоритм линейного пути пересечения точек

Question

У меня есть проблема, в которой мне нужно проверить, пересекла ли точка путь линии,
Путь линии - это набор строк (y = ax + b).
Кто-нибудь знает какой-то известный алгоритм для этого?

так я решил это следующим образом: я добавил 2 очка в начале и в конце path-, так что теперь оно многоугольник я добавил 2 очка в 90 градусов к точкам на фиксированном расстоянии. и я использовал алгоритм луча.

Answer 1

Есть простые алгоритмы, чтобы знать, если точка находится внутри или вне многоугольника: http://en.wikipedia.org/wiki/Point_in_polygon Это может быть адаптировано к линии пути установки, нажав несколько ребер многоугольника до бесконечности (на практике, вы можете поместить свой путь линии в большой коробке и cansider многоугольник, образованный частью коробки, которая находится справа (или слева, так как вы хотите) стороны линии).

Answer 2

Учитывая входной точки (x_1, y_1), и ваша линия имеет вид y = ax + b, то вы можете сказать, где ваша точка ввода определяет местоположение, поставив x_1 в уравнение линии:

if y_1 == a * x_1 + b then (x_1, y_1) is on the line 
if y_1 < a * x_1 + b then (x_1, y_1) locates below the line 
if y_1 > a * x_1 + b then (x_1, y_1) locates above the line 

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

Answer 3

поэтому я решил это следующим образом: я добавил 2 точки в начале и в конце пути, поэтому теперь это многоугольник, я добавил 2 точки в 90 градусов к точкам на фиксированном расстоянии. и я использовал алгоритм луча.

редактировать: его не всегда 90 градусов, это depens от угла между начальной и конечной точкой

Answer 4

Я знаю двух подходов:

1. использование адаптированного точки внутри алгоритма многоугольника
   • вы должны знать, с какой стороны находится сторона (скрещенная/непересекая сторона)
   • поэтому создайте вектор dir, который указывает на линию патч к стороне пересечения
   • это может быть средним нормальными (или нормальной точка линии старта-конец)
   • литой лучами от тестируемой точки в реже направления
   • подсчет пересечения с вашей линией патчем
   • , если пересечение происходит именно на месте соединения двух линий подсчитывать только один раз
   • в конце, если счетчик не равен нулю и нечетно, то точка пересек линию патч
   • это надежный ошибкам, но немного медленно
   • см Левого изображения
2. если линия патч не слишком сложная форма использования обмотки правила (скалярное умножение вектора)
   • линии коммутационных линии должны быть в одном направлении от начала до конца !!!
   • линия выбора из пластыря, которые близки к точке (1-5 должна быть достаточно)
   • в идеале на ту же высоту, на рисунке справа
   • конечно в реале может быть повернуты так, выберите линии на расстоянии (нет необходимости SQRT его)
   • вычислительного скалярного произведения для выбранных линий, как это:
   • линии Р0, Р1, точка P -> точки продукта = (. (P1-P0) (Р-Р1))
   • dot product из 2 векторов ((x1, y1, z1)) = (x0 * x1 + y0 * y1 + z0 * z1)
   • полярность результата означает, что направление намотки по часовой стрелке/против часовой стрелки
   • если все обмотки являются правильными, чем точка не пересекаются
   • , если форма линии патча является сложной, то могут возникнуть проблемы, если точка находится слишком близко к нему
   • в этом тесте случае только линии одной и той же высоте «» или метод использования 1.
   • , чтобы получить «высоту» вычислить расстояние между точкой и начальной точкой линии в направлении линии
   • , если его из от нуля до размера строки, что его OK еще не использует его
   • также может быть сделано с точки продукта на вектор нормали к направлению линии