Линия и пересечение отрезка

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

В точке пересечения: p + t * d = p1 + k * (p2 - p1) - два уравнения(по x и y)

Из этих уравнений вы можете просто найти параметры k и t.Если 0

Если вы знаете k или t, вы можете просто вычислить точку пересечения из (x, y) (t) = p + t * dили (x, y) (t) = p1 + k * (p2 - p1)

Answer 3

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

let p1(x1,y1) и p2(x2,y2) сегмент, уравнение которого равно D' = a'.x+b' для любого x in [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)

например:

пусть 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, поэтому существует точка пересечения в P(X,Y)