Как определить, пересекаются ли два прямых отрезка на плоскости?

Written on . Posted in [Delphi] Алгоритмы

Условие пересечения отрезков

Прямая A*x+B*y+C=0 по двум точкам P1(x1,y1), P2(x2,y2):

A = y2-y2
B = x1-x2
C = -A*x1-B*y1 = y1*x2 - x1*y2

Расстояние от точки S(x0,y0) до прямой:

r = A*x0 + B*y0 + C /sqrt(A*A + B*B)

обозначим как 

Q(P1(x1,y1),P2(x2,y2),S(x0,y0)) = r*sqrt(A*A+B*B) =
	x0*(y2-y1)+y0*(x1-x2) + y1*x2 - x1*y2

Тогда условие пересечения двух отрезков (a, b) и (A, B):

Q(a,b;A)*Q(a,b;B)<0 && Q(A,B;a)*Q(A,B;b)<0

Пример реализации на паскале:

function Q(ax,ay,bx,by,tx,ty:longint):real;
begin
	Q:=tx*(by-ay)+ty*(ax-bx)+ay*bx-ax*by;
end;
delphi форум