Раздел «Алгоритмы».IntersectPAS:

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

{ (C) Igor Kvasov }
type
  point   = record x,y :extended; end;
  vector  = record x,y :extended; end;
  segment = record b,e :point;    end;


function vec(b,e:point):vector;
begin 
  vec.x := e.x-b.x; vec.y := e.y-b.y; 
end;

function mul(a,b:vector):extended;
begin 
   mul := a.x*b.y - a.y*b.x; 
end;

function lintersect(b1,e1,b2,e2:extended):boolean;
begin
    lintersect:=true;
    if (b1-b2)*(e1-b2) <= 0 then exit;
    if (b1-e2)*(e1-e2) <= 0 then exit;
    if (b2-b1)*(e2-b1) <= 0 then exit;
    lintersect:=false;
end;

function intersect(a,b:segment):boolean;
begin
    intersect:=false;
    { false если концы отрезка b лежат по разные стороны от прямой a }
    if mul(vec(a.b,a.e),vec(a.b,b.b)) * mul(vec(a.b,a.e),vec(a.b,b.e)) > 0 then exit;

    { false если концы отрезка a лежат по разные стороны от прямой b }
    if mul(vec(b.b,b.e),vec(b.b,a.b)) * mul(vec(b.b,b.e),vec(b.b,a.e)) > 0 then exit;
    
    {проекции отрезков на обе оси пересекаются }
    intersect:=lintersect(a.b.x,a.e.x,b.b.x,b.e.x) 
               and lintersect(a.b.y,a.e.y,b.b.y,b.e.y);
end;

begin

end.

-- IgorKvasov? - 28 Dec 2004

AlgorithmClasifyForm
Type: Теория
Scope:  
Strategy:  
Complexity: Low