Graphics Reference
In-Depth Information
P(p,n) denotes the plane through p with normal vector n.
Given a vector n, n(X) denote the set {n
·
x | xe X}
boolean function
AreDisjoint (
point set
X, Y)
{ The function returns true if conv
(X) and conv(Y) are disjoint and false otherwise.
We assume that the affine hull of the points in X and Y has dimension 3. }
begin
integer
itp;
point
p, q;
vector
n1, n2;
point set
X1, Y1;
real
c;
itp := SpaceProjectionType (X,Y,p,n1);
case
itp
of
0 :
return
(
false
);
{ Sets intersect }
1 :
return
(
true
);
{ Sets are disjoint }
2 :
begin
X1 := X « P(p,n1); Y1 := Y « P(p,n1);
itp := PlanarProjectionType (X1,Y1,p,n1,q,n2);
case
itp
of
0 :
return
(
false
);
{ Sets intersect }
1 :
return
(
true
);
{ Sets are disjoint }
2 :
begin
X1 := X1 « P(q,n2); Y1 := Y1« P(q,n2);
itp := LinearProjectionType (X1,Y1,q,n1,n2);
return
(itp = 0);
end
end
end
end
end
;
integer function
SpaceProjectionType (
point set
X, Y;
ref point
p;
ref vector
n)
{ Inputs:
subsets X = (p1,p2,º,ps) and Y = (q1,q2,º,qt) of
R
3
Output:
point p and normal vector for a plane P
function returns an integer:
0 - convex hulls of X and Y intersect
1 - convex hulls of X and Y are disjoint
2 - conv(X) « conv(Y) lies in P(p,n)
}
begin
point set
S;
integer
m, itp, i, j, k;
S := X » Y; { S = (p1,p2,º,ps,q1,q2,º,qt) = (s1,s2,º,sm) }
m := s + t; itp := 0;
Algorithm 13.2.1.
Algorithm for when convex sets are disjoint.
