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

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

Если A₁x + B₁y + C₁ = 0 и A₂x + B₂y + C₂ = 0 есть урав­нения прямых, на которых лежат первый и второй отрезки соответственно, то значения координаты точки пересечения этих прямых будут равны:

К сожалению, отрезки в отличие от прямых линий имеют конечную длину. Рассмотрим возможные случаи взаимного расположения отрезков.

Рис 3.2
Обратим внимание на варианты 1 и 2. Можно заметить, что если концы хотя бы одного из отрезков лежат по одну сторону от прямой, проходящей через концы другого отрезка, то отрезки не пересекаются. Поэтому для данных случаев нет смысла искать точку пересечения отрезков.

Для случаев 3 и 4 – концы каждого из отрезков лежат по разные стороны от прямой линии, на которой лежит другой отрезок (посмотрите предыдущий раздел).

Случай 5 и 6. Отрезки лежат на одной прямой. Если их проекции пересекаются (т.е. проекция правого края хотя бы одного из отрезков больше проекции левого края другого отрезка), то они пересекаются. Если проекции отрезков не пересекаются, то и отрезки не пересекаются. Несмотря на то, что отрезки в шестом случае пересекаются, точек пересечения будет бесконочно много. Поэтому нас будут интересовать варианты 3 и 4.

Попробуем реализовать это программно.
Procedure Work;

begin

а[1] := y[2]- y[1];

b[1] := x[1]- x[2];

c[1] := -x[1]*(y[2]- y[1])+ y[1]*(x[2]- x[1]);

а[2] := y[4]- y[3];

b[2] := x[3]- x[4];

c[2] := -x[3]*(y[4]- y[3])+ y[3]*(x[4]- x[3]);
{отсеиваем варианты 1 и 2}

if ((a[1]*x[3]+b[1]*y[3]+c[1])*(a[1]*x[4]+b[1]*y[4]+c[1])>0) or ((a[1]*x[3]+b[1]*y[3]+c[1])*(a[1]*x[4]+b[1]*y[4]+c[1])>0) then Flag:=False;

if ((a[1]*x[3]+b[1]*y[3]+c[1])=0)and((a[1]*x[4]+b[1]*y[4]+c[1])=0) then Flag:=False;

if Flag then

begin

x:= (b[1]*c[2]-b[2]*c[1])/(a[1]*b[2]-a[2]*b[1]);

end;
end;