137 lines
4.4 KiB
ObjectPascal
137 lines
4.4 KiB
ObjectPascal
program TrianglesOverlap;
|
|
{
|
|
The program looks for a separating line between the triangles. It's known that
|
|
only the triangle sides (produced) need to be considered as possible separators
|
|
(except in the degenerate case when both triangles are reduced to a point).
|
|
If there's a strong separator, i.e. one that is disjoint from at least one
|
|
of the triangles, then the triangles are disjoint. If there's only a weak
|
|
separator, i.e. one that intersects both triangles, then the triangles intersect
|
|
in a point or a line segment (this program doesn't work out which).
|
|
If there's no separator, then the triangles have an overlap of positive area.
|
|
}
|
|
{$IFDEF FPC}
|
|
{$mode objfpc}{$H+}
|
|
{$ENDIF}
|
|
|
|
uses Math, SysUtils;
|
|
|
|
{$DEFINE USE_FP}
|
|
{$IFDEF USE_FP}
|
|
type TCoordinate = double;
|
|
const TOLERANCE = 1.0E-6;
|
|
{$ELSE}
|
|
type TCoordinate = integer;
|
|
const TOLERANCE = 0;
|
|
{$ENDIF}
|
|
|
|
type TVertex = record
|
|
x, y : TCoordinate;
|
|
end;
|
|
|
|
function Vertex( x_in, y_in : TCoordinate) : TVertex;
|
|
begin
|
|
result.x := x_in;
|
|
result.y := y_in;
|
|
end;
|
|
|
|
// Result of testing sides of a triangle for separator.
|
|
// Values are arbitrary but must be in this numerical order
|
|
const
|
|
SEP_NO_TEST = -1; // triangle is a single point, no sides to be tested
|
|
SEP_NONE = 0; // didn't find a separator
|
|
SEP_WEAK = 1; // found a weak separator only
|
|
SEP_STRONG = 2; // found a strong separator
|
|
|
|
function EqualVertices( V, W : TVertex) : boolean;
|
|
begin
|
|
result := (Abs(V.x - W.x) <= TOLERANCE)
|
|
and (Abs(V.y - W.y) <= TOLERANCE);
|
|
end;
|
|
|
|
// Determinant: twice the signed area of triangle PQR.
|
|
function Det( P, Q, R : TVertex) : TCoordinate;
|
|
begin
|
|
result := Q.x*R.y - R.x*Q.y + R.x*P.y - P.x*R.y + P.x*Q.y - Q.x*P.y;
|
|
end;
|
|
|
|
// Get result of trying sides of LMN as separators.
|
|
function TrySides( L, M, N, P, Q, R : TVertex) : integer;
|
|
var
|
|
s, sMin, sMax: TCoordinate;
|
|
H, K : TVertex;
|
|
|
|
function TestSide( V, W : TVertex) : integer;
|
|
var
|
|
detP, detQ, detR, tMin, tMax : TCoordinate;
|
|
begin
|
|
result := SEP_NONE;
|
|
detP := Det( V, W, P);
|
|
detQ := Det( V, W, Q);
|
|
detR := Det( V, W, R);
|
|
tMin := Math.Min( Math.Min( detP, detQ), detR);
|
|
tMax := Math.Max( Math.Max( detP, detQ), detR);
|
|
if (tMin - sMax > TOLERANCE) or (sMin - tMax > TOLERANCE) then
|
|
result := SEP_STRONG
|
|
else if (tMin - sMax >= -TOLERANCE) or (sMin - tMax >= -TOLERANCE) then
|
|
result := SEP_WEAK;
|
|
end;
|
|
|
|
begin
|
|
sMin := 0;
|
|
sMax := 0;
|
|
s := Det( L, M, N);
|
|
if (s <> 0) then begin // L, M, N are not collinear
|
|
if (s < 0) then sMin := s else sMax := s;
|
|
// Once we've found a strong separator, there's no need for further testing
|
|
result := TestSide( M, N);
|
|
if (result < SEP_STRONG) then result := Math.Max( result, TestSide( N, L));
|
|
if (result < SEP_STRONG) then result := Math.Max( result, TestSide( L, M));
|
|
end
|
|
else begin // s = 0 so L, M, N are collinear
|
|
// Look for distinct vertices from among L, M, N
|
|
H := L;
|
|
K := M;
|
|
if EqualVertices( H, K) then K := N;
|
|
if EqualVertices( H, K) then result := SEP_NO_TEST // L = M = N
|
|
else result := TestSide( H, K);
|
|
end;
|
|
end;
|
|
|
|
function Algo_5( A, B, C, D, E, F : TVertex) : integer;
|
|
begin
|
|
result := TrySides( A, B, C, D, E, F);
|
|
if (result < SEP_STRONG) then begin
|
|
result := Math.Max( result, TrySides( D, E, F, A, B, C));
|
|
if (result = SEP_NO_TEST) then begin // A = B = C and D = E = F
|
|
if EqualVertices( A, D) then result := SEP_WEAK
|
|
else result := SEP_STRONG;
|
|
end;
|
|
end;
|
|
end;
|
|
|
|
procedure TestTrianglePair (Ax, Ay, Bx, By, Cx, Cy,
|
|
Dx, Dy, Ex, Ey, Fx, Fy : TCoordinate);
|
|
var
|
|
ovStr : string;
|
|
begin
|
|
case Algo_5( Vertex(Ax, Ay), Vertex(Bx, By), Vertex(Cx, Cy),
|
|
Vertex(Dx, Dy), Vertex(Ex, Ey), Vertex(Fx, Fy)) of
|
|
SEP_STRONG : ovStr := 'Disjoint';
|
|
SEP_NONE : ovStr := 'Overlap';
|
|
else ovStr := 'Borderline';
|
|
end;
|
|
WriteLn( SysUtils.Format(
|
|
'(%g,%g),(%g,%g),(%g,%g) and (%g,%g),(%g,%g),(%g,%g): %s',
|
|
[Ax, Ay, Bx, By, Cx, Cy, Dx, Dy, Ex, Ey, Fx, Fy, ovStr]));
|
|
end;
|
|
|
|
// Main routine
|
|
begin
|
|
TestTrianglePair( 0,0,5,0,0,5, 0,0,5,0,0,6);
|
|
TestTrianglePair( 0,0,0,5,5,0, 0,0,0,5,5,0);
|
|
TestTrianglePair( 0,0,5,0,0,5, -10,0,-5,0,-1,6);
|
|
TestTrianglePair( 0,0,5,0,2.5,5, 0,4,2.5,-1,5,4);
|
|
TestTrianglePair( 0,0,1,1,0,2, 2,1,3,0,3,2);
|
|
TestTrianglePair( 0,0,1,1,0,2, 2,1,3,-2,3,4);
|
|
TestTrianglePair( 0,0,1,0,0,1, 1,0,2,0,1,1);
|
|
end.
|