Пересечение отрезков

[BoozZzilla]

Не баловства ради завожу эту тему. А интереса для!
Сразу оговорюсь - никакого практического смысла в вопросе нет, ничего такого мне делать не надо, но просто очень интересно как решается эта задача.
Уловил название темы в другой ветке и вот у меня вопрос появился - если у нас есть координаты начала и конца двух отрезков, как (алгоритм, можете код не писать) нам найти пересекаются ли эти отрезки и в какой точке.
Я понимаю что эта задача тривиальна для тех кто с графикой работает, и вот мне тоже стало интересно.

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

[Serge_Bliznykov]

1-х. рекомендую ознакомится с книжкой Окулов С.М. "Программирование в алгоритмах" - глава 5. "Алгоритмы вычислительной геометрии" раздел 5.2. "Прямая линия и отрезок прямой"

Function CrossLine(Const LI, L2: TLine) : Boolean;
{*Определяет существование точки пересечения
двух прямых. Значение функции равно True,
если точка есть, и False, если прямые
параллельны. *}
Var st: Real;
Begin
st:=Ll.A*L2.B-L2.A*Ll.B;
CrossLine:=Not RealEq (st, 0) ;
End;
Procedure Line2ToPoint(Const LI, L2: TLine; Var P:
TPoint);{*Определение координат точки
пересечения двух линий. *}
....

2-е. но и с точки зрения банального здравого смысла очевидно, что если записать два уравнения прямых, то точка их пересечения - это результат решения системы уравнений с двумя неизвестными.
Для отрезков всё так же - записываем уранения прямых, на которых данные отрезки лежат, находим координаты точки пересечения, если они принадлежат отрезку - значит есть реальное пересечение, если они за пределами отрезка - то реальной точки пересечения нет.

[denisbrain]

есть в заготовках такое

function Subtract(AVec1, AVec2 : TPoint) : TPoint;
begin
  Result.X := AVec1.X - AVec2.X;
  Result.Y := AVec1.Y - AVec2.Y;
end;

function LinesCross(LineAP1, LineAP2, LineBP1, LineBP2 : TPoint) : boolean;
Var
  diffLA, diffLB : TPoint;
  CompareA, CompareB : integer;
begin
  Result := False;
  diffLA := Subtract(LineAP2, LineAP1);
  diffLB := Subtract(LineBP2, LineBP1);
  CompareA := diffLA.X*LineAP1.Y - diffLA.Y*LineAP1.X;
  CompareB := diffLB.X*LineBP1.Y - diffLB.Y*LineBP1.X;
  if ( ((diffLA.X*LineBP1.Y - diffLA.Y*LineBP1.X) < CompareA) xor
       ((diffLA.X*LineBP2.Y - diffLA.Y*LineBP2.X) < CompareA) ) and
     ( ((diffLB.X*LineAP1.Y - diffLB.Y*LineAP1.X) < CompareB) xor
       ((diffLB.X*LineAP2.Y - diffLB.Y*LineAP2.X) < CompareB) ) then
    Result := True;
end;

function LineIntersect(LineAP1, LineAP2, LineBP1, LineBP2 : TPoint) : TPointFloat;
Var
  LDetLineA, LDetLineB, LDetDivInv : Real;
  LDiffLA, LDiffLB : TPoint;
begin
  LDetLineA := LineAP1.X*LineAP2.Y - LineAP1.Y*LineAP2.X;
  LDetLineB := LineBP1.X*LineBP2.Y - LineBP1.Y*LineBP2.X;
  LDiffLA := Subtract(LineAP1, LineAP2);
  LDiffLB := Subtract(LineBP1, LineBP2);
  LDetDivInv := 1 / ((LDiffLA.X*LDiffLB.Y) - (LDiffLA.Y*LDiffLB.X));
  Result.X := ((LDetLineA*LDiffLB.X) - (LDiffLA.X*LDetLineB)) * LDetDivInv;
  Result.Y := ((LDetLineA*LDiffLB.Y) - (LDiffLA.Y*LDetLineB)) * LDetDivInv;
end;

[Rin]

Вот хороший алгоритм http://users.livejournal.com/_winnie/152327.html