Graphics Reference
In-Depth Information
for
i:=1
to
m
do
for
j:=i+1
to
m
do
for
k:=j+1
to
m
do
if
si,sj,sk are linearly independent points
then
begin
n := (sj - si) ¥ (sk - si); { normal to plane P }
if
n(X) is disjoint from n(Y)
then
begin
itp := 1;
Break;
end
else if
n(X) meets n(Y) is a single number
then
begin
itp := 2; p := si; Break;
end
end
;
return
(itp);
end
;
integer function
PlanarProjectionType (
point set
X, Y;
point
p;
vector
n1;
ref point
q;
ref vector
n2)
{ Inputs: X = (p1,p2,...,ps) , Y = (q1,q2,...,qt) Õ plane P = P(p,n1)
Convex hull of points in X and Y is assumed to have dimension 2.
Output: point q and normal vector n2 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 on line L = P(q,n1) « P(q,n2) }
begin
point set
S;
integer
m, itp, i, j;
S := X » Y;
{ S = (p1,p2,...,ps,q1,q2,...,qt) = (s1,s2,...,sm) }
m := s + t;
itp := 0;
for
i:=1
to
m
do
for
j:=i+1
to
m
do
if
si,sj are distinct points
then
begin
n2 := (sj - si) ¥ n1; { normal to the line L in the plane P }
if
n2(X) is disjoint from n2(Y)
then
begin
itp := 1; Break;
end
Algorithm 13.2.1.
Continued