Условие: Дано 2 отрезка.Проверить пересекаются ли они.
Решение: Отрезок на плоскости может быть описан параметрической системой уравнений:
X = T * (X2 – X1) + X1:
Y = T * (Y2 – Y1) + Y1.
При T = 0 мы находимся в точке X1, Y1 (начало отрезка), при T = 1 в точке X2, Y2 (конец от-резка). Соответственно, при 0 <= T <= 1 мы находимся внутри отрезка.
Для двух отрезков составляем следующую систему уравнений:
X = T1 * (X12 – X11) + X11; (1)
Y = T1 * (Y12 – Y11) + Y11; (2)
X = T2 * (X22 – X21) + X21; (3)
Y = T2 * (Y22 – Y21) + Y21. (4)
Решая систему данных уравнений необходимо найти значения параметров T1 и T2.
Если решение данной системы T1 и T2 находятся в интервале [0…1], то отрезки пересекаются.
Подставив найденные значения T1 или T2 в исходные уравнения, найдём координаты точки пересечения X и Y. Для решения системы, приравняем 1-ое уравнение к 3-му, а 2-ое к 4-му.
T1 * (X12 – X11) + X11 = T2 * (X22 – X21) + X21;
T1 * (Y12 – Y11) + Y11 = T2 * (Y22 – Y21) + Y21.
Эта же система уравнений в другом виде:
T1 * (X12 – X11) – T2 * (X22 – X21) = X21 – X11;
T1 * (Y12 – Y11) – T2 * (Y22 – Y21) = Y21 – Y11.
Представляет собой систему двух линейных уравнений 1-го порядка. Решим её методом Краме-ра. Тогда: D = (X12 – X11) * (Y21 – Y22) – (X21 – X22) * (Y12 – Y11);
DT1 = (X21 – X11) * (Y21 – Y22) – (X21 – X22) * (Y21 – Y11);
DT2 = (X12 – X11) * (Y21 – Y11) – (X21 – X11) * (Y12 – Y11);
Если D = 0, то отрезки параллельны, либо полностью или частично совпадают. Иначе:
T1 = DT1 / D; T2 = DT2 / D.
Программа в Паскале:
Числовые значения координат при вводе разделяются пробелом.
Program Prg;
Uses Crt;
Var X11, Y11, X12, Y12 : Real;
Var X21, Y21, X22, Y22 : Real;
Var D, D1, D2, T1, T2 : Real;
Var X, Y : Real;
Begin
ClrScr;
Write('Введите X11 Y11 X12 Y12: ');
ReadLn(X11, Y11, X12, Y12);
Write('Введите X21 Y21 X22 Y22: ');
ReadLn(X21, Y21, X22, Y22);
D := (X12 - X11) * (Y21 - Y22) - (X21 - X22) * (Y12 - Y11);
If D = 0 Then
WriteLn('Отрезки параллельны, либо полностью или частично совпадают.')
Else
Begin
D1 := (X21 - X11) * (Y21 - Y22) - (X21 - X22) * (Y21 - Y11);
D2 := (X12 - X11) * (Y21 - Y11) - (X21 - X11) * (Y12 - Y11);
T1 := D1 / D;
T2 := D2 / D;
If (T1 >= 0) And (T1 <= 1) And (T2 >= 0) And (T2 <= 1) Then
Begin
X := T1 * (X12 - X11) + X11;
Y := T1 * (Y12 - Y11) + Y11;
WriteLn('Отрезки пересекаются в точке X Y: ',X:6:3,' ',Y:6:3)
End
End;
ReadLn
End.