Пересечение сегмента линии и линии

Question

Как определить, пересекается ли линия (направление d и -d из точки p) и отрезок линии (между точками p1 и p2) в 2D? Если они это сделают, как я могу получить их точку пересечения.

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

Я нашел это, но я не понимаю, что это побочный оператор: http://www.loria.fr/~lazard//ARC-Visi3D/Pant-project/files/Line_Segment_Line.html

Answer 1

Если это 2D задача (линия и отрезок лежат в одной плоскости, и они определяются 2-мерным координаты), это легко.

Построить вектор, нормальный к d (направление линии).

Вычислительные точечные произведения d * (p1-p) и d * (p2-p). Если они имеют один и тот же знак, нет пересечения. Если они имеют противоположные знаки, есть пересечение. Немного подумав, вы можете выяснить, как вычислить местоположение пересечения в терминах p, p1-p и p2-p.

Answer 2

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

строка 1: (x, y) (t) = p + t * d; линия 2: (х, у) (т) = p1 + K * (р2 - р1)

В точке пересечения: р + т * д = р1 + к * (р2 - р1) - два уравнения (за x и на y)

Из этих уравнений вы можете просто найти k и t параметров.Если 0 < к < 1 точка пересечения находится в (p1, p2)

Если вы знаете, K или Т можно просто вычислить точку пересечения с (х, у) (т) = р + т * D или (х, у) (т) = p1 + к * (р2 - р1)

Answer 3

пусть p(x,y) и a свое направление уравнение линии D = a.x+b где b = y - a.x

пусть p1(x1,y1) и p2(x2,y2) сегмент, который уравнение D' = a'.x+b' для любого x в [x1;x2] где a' = (y2-y1)/(x2-x1) и b' = y2 - a'.x2 = y1 - a'.x1

у вас есть перекресток, если есть x между [x1;x2], для которого D = D' , таким образом, если X = (b'-b)/(a-a') принадлежат [x1;x2] то Y = a.X+b = a'.X+b дает точку пересечения P(X,Y)

, например:

let p(255,255), a = 1 =>b = 0

пусть p1(60,179) и p2(168,54)

=>a' = -125/108

=>b' = 24596/99

=>X = (24596/99 - 0)/(1+125/108) = 115,1587983

=>Y = (24596/99 - 0)/(1+125/108) = 115,1587983

X находится между 60 и 168 таким образом есть пересекаться ion point at P(X,Y)