DETECTION OF THE INTERSECTION OF TWO SIMPLE POLYHEDRA
49
INFORMATICA 1 /90
Dusar> Surla, Zoran Budimac
Keywords: detection algorithm, polyhedron	Institute of Mathematics,
intersection, modula-2	drl.Djuricica4,21000NoviSad
ABSTRACT. An algorithm is described for detecting the intersection of two simple polyhedra. The corresponding programme, implemented in Modula-2, is essentially based on a procedure developed to test the intersection of the given segment and simple polygon. The basis for this procedure is the relations between a point, a straight line and a plane, expressed in the vector form.
1. INTRODUCTION
One of the fundamental problems in computational geometry is detection of the intersection of two polyhedra. The problem is directly related to linear programming, hidden surface elimination, computer vision, motion planning and robotics.
Of the numerous publications devoted to this subject we shall mention only those dealing with the problem of intersection [5,6,9] and detection of the intersection [1-4] of two polyhedna. Some of the authors have considered the computational complexity of the algorithms used for solving these problems [3-6,9,10).
In [7] and [8] we have described an algorithm and the corresponding programme for determination whether a given point belongs to the interior domain of a simple polyhedron, as well as for determination of the intersection of a straight line and a simple polyhedron. The basic procedures were formed on the basis of the relations (given in the vector form), between a point, a straight line and a plane.
The present article is a continuation of the above studies in which our considerations are being extended onto the problem of detection of the intersection of two simple polyhedra.
2. THE ALGORITHM
Let bo given two simple polyhedra P and Q. Their possible relations may be as follows:
P	n	Q	-	C
P	n	Q	~	P
P	n	Q	-	Q
P	n	Q	=	0
* 0 , C
P £ Q ) Q S- P )
* P
C * Q
(1) (2)
(3)
(4)
If the intersection of at least one edge of P (resp. Q) and at least one facet of Q (resp. P) is not an empty set, then condition (1) is fulfilled. If condition (1) is not fulfilled, then P and Q intersect provided that one arbitrary vertex of P (resp. Q) belongs to the interior of the polyhedron Q (resp. P), i.e., condition 2 (resp. 3) is fulfilled. Obviously, if conditions (l)-(3) are not fulfilled, then case (4) holds, i.e., P and Q do not intersect.
Thus, testing condition (1) is reduced to the multiple use of the function for detecting the intersection of the segment (polyhedron edge) and the simple polygon (polyhedron facet). This function can be formed on the basis of the relations given in their vector form.
2.1. BASIC RELATIONS
An arbitrary point ZeR3, considered as a
vector of the same coordinates, we shall denote t~	33
Let be given 3the points AeR and Bell? , and the plane a in R . Let us form the following
expression:
Dt - (7? - >?) d2 - (g - t)
D = D. • D_
n n
(5)
(6) (7)
where FJ is a vector perpendicular to, a and Xea. The mark "°* denotes the scalar product of vectors. If D < 0 (resp. D>0), then the points A and B are on different (resp. on the same) side
of the plane a. For D -0 and
D 0O 2
point
belongs to the plane a, and for D^O and D^-point B belongs to the plane a. If -0 and D2■
then the segment AB belongs to the plane a.^ Let us form the expressions:
(Ö - Ü) x (V? - 3) (il - d) x (tf - fl)
t. . t
(8) (9) (10)
where the points G, H, U and V belong to the same plane. The mark "x" stands for the vector product of vectors. If E > 0 (resp. E < 0), then the points G and H are on the same (resp. on different) side of the straight line determined by the points U and V. For Et - 0 (resp. E2 - 0)
point G (resp. H) lies on the straight line determined by the points U and V.
50
On the basis of relations (8)-(10) it can be determined whether the segments OH and UV intersect. Namely, if the points G and H are on the different sides of the straight line UV and the points U and V are on the different sides of the straight line GH, the two segments intersect, otherwise not.
(I )
r n V V 1-1 1
T;
T is different from V
(U ) (iil) r (iv) r n V
r n V V i-i I
V V 1-1 1
V
1-1 1
V	or
V	V , i-i i
r n V V i-i i
and V = V
l '
2.2. DETECTION OF THE INTERSECTION OF A SEGMENT AND A SIMPLE POLYGON
Let. us denote the vertices of an edge of the one polyhedron by A and B, and by S a facet of the other polyhedron. Facet S is a simple polygon. Let the plane a be determined by the polygon S. Let us suppose the values in expressions (5)-(7) are as follows: D<0; D1-0
and D2*0; Dj*0 and D2=0. In these cases the
intersection of the segment AB and the plane a is a point. Let us denote this point by R. If R belongs to the interior region or of the hull of the polygon S, then the intersection of the segment and polygon S is not an empty set. In the case when, the segment AB belongs to the plane a, then detection of the intersection of the segment AB and polygon S consists in the following. The intersection of the segment AB and all the edges of S is tested on the basis of relations (8)-(10). If this intersection is an empty set, then it is necessary to test additionally if at least one of the points A and B belongs to the interior region of S. If it does, the intersection of the segment AB and polygon S is not an empty set.
Therefore, detection of the intersection of the segment AB and polygon S is reduced further to solving the following task.
Given a simple polygon S in a and the point Rea, determine if the point R belongs to the interior region of S.
Let r be an arbitrary straight line lying in the plane a. and passing through the point R. Let us introduce the following definitions.
Definition 1. The intersection point between r and the hull of P is a piercing point if at this point r passes from the interior into the exterior domain of P, or vice versa.
Definition 2. The edge of the simple polygon S, lying on the straight line r is a piercing edge if one vertex of this edge borders upon the internal and the other on the external region of S.
Then, the following theorem holds.
Theorem. Point R belongs to the interior region of S if on the same side of the point R lying on the straight line r, the sum of piercing points and piercing edges is an odd number.
Proof. Let us suppose' the point Y moves along the straight line r from infinity to the point R. Then Y belongs to the exterior domain of S until it reaches the first piercing point, or piercing edge. After passing through the first piercing point / piercing edge, the point Y enters the interior domain of S and remains in it until reaching the second piercing point / piercing edge. Afterwards, the point Y comes again to the exterior domain, and so on. Therefore, if point Y coincides with R after passing through an odd number of the sum of piercing points and piercing edges, then R belongs to the interior domain of polygon S.H
Let us denote an edge of S by V V . The
straight line r and the edge V11VJ may have one of the following relations:
In case (i ) T is a piercing point. Let in case (ii) the intersection be the vertex V .
Then Vt is a piercing point if the vertices V i
and V are on different sides of the straight
line determined by the points V and R, i.e. if
the following condition is fulfilled:
Jxlft-V, )) " '^i.rV^HM'1 <0
(11)
In case {Hi), the edge V V
is a
piercing edge if the vertices V( 2 and V are
on different sides of the straight line r, i.e. if the following condition is fulfilled:
(12)
Obviously, in case [if), the edge	is
not a piercing edge and there are no piercing points on it.
Figure 1 shows an illustrative example of the intersection of the straight line r and polygon S. The corresponding intersection points are Kf , Ka , K3, K4 and V , and the piercing
edge is	, ■ Additionally, the edges V2V3 and
V	and the vertex V are lying on the
6 7	13
straight line r. On the basis of these data, it is possible to determine if a point Rer is on the hull of S, or it belongs to the interior / exterior region of S. First, if ttie point R coincides with one of the piercing po.ints K ,
K , K , K, and V , or with the vertex V , or
234	15	13
it belongs to one of the edges V V , V V„ and
2 3 6 7
VJ()V , then R is on the hull of S. Second,	let
us suppose that the point R is between K3	and
V	. Then, on the one side of this point	are
found the piercing points Kt , K2 i K3 , and on
the other side, the piercing edge V V and	the
piercing points K^ and V ■ Obviously, on	the
basis of the given theorem, in both cases point R belongs to the interior region of S.
Let us consider now the segment RR^, where
the point R^ is chosen to belong to the exterior
region of S, which is easily achieved by taking that absolute values of the coordinates of the point Rro are large. The algorithm for
determining if R belongs to the interior region of S, can be formed as a Modula-2 function procedure Internal in the following way:
PROCEDURE Internal(R, S): BOOLEAN;
[ Procedure Internal returns TRUE if point R belongs to the interior region or to the hull of the simple polygon S, whose vertices are denoted by V , i=l, 2, ..., n, where it is assumed that
V -V , V -V
n 0 n+ 1 1
V =V
n+ 2 2
K is the sum of piercing points and piercing edges. ]
51
BEGIN K 0;
Determination of point R^;
FOR 1 := 1 TO n DO IF (RsV V ) THEN
RETURN TRUE
ELSIF (V V cRR ) AND
1 i + t	0D
2.3. PROCEDURE FOR DETECTING THE INTERSECTION OF TWO SIMPLE POLYHEDRA
(v.
V are on di fferent sides of the i * 2
straight line RR^) THEN INC(K) ELSIF (V.eRR^) AND
(V V are on different sides of the \ i - t ' i + 1
straight line RR^) THEN INC(K)
ELSIF (V,Vl+in RR^ x 0) THEN INC(K)
END END
RETURN K<>0 AND ODD(K) END Internal;
In the given algorithm, the relations betu/een two segments, and betu/een a point and a segment are determined on the basis of relations (8)—(10).
The algorithm for determining if an edge and a facet intersect is the auxiliary one, and will be used in the final step. It is formed as the Modula-2 function procedure Intersect.
PROCEDURE Intersect(E, F): BOOLEAN; 1 Procedure Intersect returns TRUE if the edge E and the facet F intersect, otherwise it returns FALSE ]
BEGIN
IF (E n plane(F) - 0) THEN IF (E c plane(F)) THEN
IF (R n hul1(F) * 0) THEN
RETURN TRUE ELSE
R is one of the vertices of E IF Internal(R, F) THEN RETURN TRUE
END
END ELSE
R := E n plane(F) IF Internal(R, F) THEN RETURN TRUE
END
END
END;
RETURN FALSE END Intersect;
FP i
i
Let us denote by EP4, i = 1,2,...,IEP|
and
1. 2..... IFPI the edges and facets of
the simple polyhedron P, and by EQ4 , i
1,2.....IEQI and FQt i - 1, 2..... IFQI the
corresponding edges and facets of the polyhedron Q. Then, the algorithm for detecting the intersection of P and Q may be presented in the form of Modula-2 function procedure Polyhedralntersect ion.
PROCEDURE Polyhedralntersection(P, Q): BOOLEAN; ( Procedure Polyhedralntersection returns TRUE if Polyhedra P and Q intersect, otherwise returns FALSE )
BEGIN
FOR i := 1 TO IEPI DO FOR j := 1 TO I FQ I DO
IF Intersect(EPt, FQ^) THEN
RETURN TRUE
END END END
FOR i := 1 TO IEQI DO FOR j :=. 1 TO IFPI DO
IF Intersect(EQl, FPj ) THEN
RETURN TRUE
END END END
IF (any vertex(P) e Q) OR ( PsQ, cond. (2) ) (any vertex(Q) e P) ( Qc:P, cond. (3) ) THEN
RETURN TRUE ELSE
RETURN FALSE END;
END Polyhedralntersection;
The modules for testing whether any vertex of one polyhedron belongs to the interior domain of the other polyhedron has been given in |8].
3. TEST EXAMPLE
Data structure of the simple polyhedra P, Q and R is given in Tables 1.-3.
Figure 1
52
Tablo 1
Ordinal no.		Polyhedra	
of vertex	P	Q	R
1	(0,0,0)	(1.1,1)	(0.0,6)
2	(5,0,0)	(6,1,1)	(5,0,6)
3	(3,2,0)	.(4,3,1)	(3.2.6)
4	(4,4,0)	(5,5,1)	(4,4,6)
5	(2,2,5)	(3,3,6)	(2,2.11)
Table 2
Ordinal no. of edge
1, 2
2,	3
3,	4
3,	5
4,	5 4, 1 1, 5
Edge determined by vertices
9.
10.
D. Surla, The Relation Between a Point and 65-68^1988) lyhedr0n>	12(2)?
D. Surla, Lj Jerinic, An Algorithm for Determining the Relation Between a Straight Line (Point) and a Simple Polyhedron, The Third International Conference on Computer Graphics, Dubrovnik, Yugoslavia, 1988, in press.
M. Szl1vA si-Nagy, An Algorithm for Determining the Intersection of Two Simple Polyhedra, Computer Graphics Forum 3. 219-225(1984).
A. C. Yao, R. L. Rivest, On the Polyhedra] Decision Problem, SIAM J. Computing 9(2) 343-347(1980).
Table 3
Ordinal no. of facet
Facet determined by ordered vertices
1	1,	2.	5
2	2.	3.	5
3	3,	5,	4
4	4.	1.	5
5	1,	2,	3, 4
P n Q « 0 and P n R
4. CONCLUSION
On the basis of the relations derived in vector form, a function can be easily formed for testing of the intersection of a given segment and a simple polygon. The multiple usé of this function can serve for detecting the intersection of two simple polyhedra P and Q for the cases when P n Q = C, C * 0, C*P and C » Q. The introduced vector relations may be suited for solving other problems in computational geometry.
References:
1.	J. W. Boyse, Interference Detection Among Solids and Surfaces, Communications of the ACM 22(1), 3-9(1979).
2.	G. Davis, Computing Separating Planes for a Pair of Disjoint Polytopes, Proc. ACM Symposium on Computational Geometry, 8-14(1985).
3.	D. P. Dobkin, D. G. Kirkpatrick, A Linear Algorithm for Determining the Separation of Convex Polyhedra, Journal of algorithms 6, 381-392(1985).
4.	D. P. Dobkin, D. G. Kirkpatrick, Fast Detection of Polyhedral Intersection, Theoretical Computer Science 27, 241-253(1983).
5.	S. Hertel, M. .Mantyia, K. Mehlhorn, J. Nievergelt, Space Sweep Solves Intersection of Convex Polyhedra, Acta Informática 21, 501-519(1984) .
6.	K. Mehlhorn, K. Simon, Intersecting Two Polyhedra One of which, is Convex, FCT, 535-542(1985).
APPENDIX
IMPLEMENTATION OF THE ALGORITHM
A.l. PRELIMINARIES
For representing a simple polyhedron, the following data structure has been adopted:
Point - ARRAY [1..3] OF REAL; Edge	- RECORD
F, S: Point END;
Polygon = RECORD
V : ARRAY [1...1001 OF Point; No : [1..1001 END;
Aux	= ARRAY [1..20 1 OF INTEGER;
Polyhedron - RECORD NoP
Vertices NoE Edges NoF
Facets NoOfV END;
CARDINAL;
ARRAY [1..100] OF Point;
CARDINAL; .
ARRAY (1..50]	OF Aux;
CARDINAL;
ARRAY [1..50|	OF Aux;
ARRAY (1..50|	OF INTEGER;
A vertex is represented by the array Point of three real numbers, i.e. coordinates of the point. An edge is represented by t.he record Edge of two points, and a polygon is represented by the record Polygon i.e. by the array V of No points.
A polyhedron is represented by the record Polyhedron i.e. by its vertices (array Vertices of NoP points), edges (array Edges of NoE vertex indices - pointers to array Vertices) and facets (array Facet of NoF vertex indices - pointers to array Vertices) . The i-th element of the array NoOfV contain the information on t.he number of vertices of the i-th polyhedron facet.
There are two operations on data structures representing polyhedron. The first one (implemented as the function procedure F.dg(P: Polyhedron; i: CARDINAL): Edge selects the i-th edge of the polyhedron P. The other one (implemented as the function procedure Fac(P: Polyhedron; i: CARDINAL): Polygon selects the i-th facet of the polyhedron P. Both procedures return their values in appropriate data structures, i.e. Edge and Polygon, respectively.
53
PROCEDURE Ed;j(P: Polyhedron; i: CARDINAL): Edge;
VAR E: Edge;
BEGIN
WITH P DO
E.F : = Vert ices I Edges[1,1]]; E.S : = Vertices[Edges[i,2]]; END;
RETURN E END Edg;
PROCEDURE Fac(P: Polyhedron; 1: CARDINAL):
Polygon;
VAR S: Polygon;
j: CARDINAL; BEGTN
WITH P DO
S.No := NoOfV[i 1 ; FOR j := 1 TO S.No DO
S.V[j] Vertices[Facets[i,j]I END; END;
RETURN S END Fac;
Wg will cite without a source code some procedures for basic vector operations, which we need for implementation of the algorithm:
PROCEDURE ScalarMul(VI,V2:Point): REAL;'
[ Scala'rMul=\h<>tf2 ] PROCEDURE VecEqual(VI,V2:Point): BOOLEAN:
[ VecEqual = (vl=\?2) ) PROCEDURE VecAdd(VI,V2:Point): Point;
( VecAdd=\h+\?2 ] PROCEDURE VecScMul(A;REAL; Vl:Point): Point;
( VecScMul=A»tfl ] PROCEDURE VecSub(VI,V2: Point): Point;
( VecSub-Vl-^2 ) PROCEDURE VecMul(VI, V2: Point): Point;
I VecMul-VIx\?2 )
A.2. PROCEDURE Internal
The procedure determines if the given point belongs to the interior domain of the simple polygon. It uses additional procedures OppSides and Between , which are based on relations ( 8)-(10 ) .
If points A and B are on different: sides of the straight line determined by C and D, then function procedure OppSides returns TRUE, otherwise it returns FALSE.
PROCEDURE OppSi des(A, B, C, D: Point): BOOLEAN;
VAR El, E2: Point;
BEGIN
El :- VgcMuJ(VecSub(A,C), VecSub(D,A)); E2 VecMul(VecSub(B.C), VecSub(D,B)); RETURN Sen 1arMul(El,E2) <0.0 END OppSides;
If the point R is on the segment V V . then
the function procedure Between returns TRUE, otherwise it. returns FALSE.
PROCEDURE Beta>cen(R, VI, V2: Point): BOOLEAN; PROCEDURE Opposite(): BOOLEAN; BEGIN
RETURN ScalarMul(VecSub(R,VI),
VecSub(R,V2)) <- 0.0
END Opposite;
PROCEDURE SameLineO: BOOLEAN; VAR ZeroVec, E: Point; BEGIN
ZeroVec[11 := 0.0; ZeroVec12] := 0.0; ZeroVoc[ 3 ] :=> 0.0;
E VecMul(VecSub(R,VI), VecSub(R,V2)); RETURN VecEqual(E, ZeroVec) END SameLine; BEGIN
RETURN SameLinef) AND Opposite*) END Between;
If the point R belongs to	the interior
domain of the simple polyhedron S,	then function
procedure Internal returns TRUE,	otherwise it returns FALSE.
PROCEDURE Internal(R: Point; S: Polygon):
BOOLEAN;
CONST Inf - 200.0; VAR i, K: CARDINAL; RInf: Point;
PROCEDURE NextVfi: CARDINAL): Point; BEGIN
RETURN S.V[(i MOD S.No) + 1 J END NextV;
PROCEDURE Next2V(i: CARDINAL): Point;
VAR Ind: CARDINAL;
BEGIN
Ind := (i MOD S.No) + 1; RETURN S.V[(Ind MOD S.No) + 1] END Next2V;
PROCEDURE PrevV(i: CARDINAL): Point; BEGIN
IF i-0 THEN
RETURN S:V[S.N0] ELSE
RETURN S.V[i-1J
END END PrevV; BEGIN K 0; WITH S DO
RInf := VecAdd(VecScMul(Inf, VecSub(R,V[1])),
V[1 ] ); FOR i 1 TO NO DO IF Between(R, V[i], NextV(i)) THEN
RETURN TRUE ELSIF Between(V[i], R, RInf) AND
Between(NextV(i), R, RInf) AND OppSides(PrevV(i),Next2V(i),R,RInf) THEN INC(K)
ELSIF Between!V[i], R, RInf) AND
OppSides(PrevV(i),NextV(i),R,RInf) THEN INC(K)
ELSIF OppSides(V[i], NextV(i), R, RInf) AND OppSides(R, RInf, V[i], NextV(i)) THEN INC(K)
END END; END;
RETURN (K<>0) AND ODD(K) END Internal;
A.3. PROCEDURE PolyhedraIntersection
The procedure determines if two simple polyhedra intersect. Additional procedures InterExlsts and Sameplane are based on relations (5)-(7 ) .
If the intersection between the segment li and the plane determined by polygon S is not an empty set, then the function procedure Int.crExists returns TRUE, otherwise it returns FALSE.
PROCEDURE InterExists( E: Edge; S: Polygon):
BOOLEAN;
VAR N: Point;
El, E2: REAL; BEGIN
WITH S DO
N := VecMul(VecSub(V[1], V[21),
VecSubJV[2], V[3] ) ); El := ScalarMul(VecSub(E^F, V[l]), N); E2 := ScalarMul(VecSub(E.S, V[l]), N); END;
RETURN E1*E2 <-0.0 END InterExists;
If the segment E belongs to the plane determined by polygon S, then the function procedure SamePlane returns TRUE, otherwise it returns FALSE.
54
PROCEDURE SamcPlane(E: Edge; S: Polygon):
PROCEDURE Intersect(E: Edge; S:
BOOLEAN;
Polygon):
BOOLEAN ;
VAR N: El BEGIN WITH N
Point; , E2: REAL;
S DO
VecMul(UGcSubfVt11, V[2|), VecSub(V[2], V[3 I)); : = ScalarMul (VecSub( E. F , Vll]), := ScalarMul(VecSub(E.S, V[l]),
El E2 END;
RETURN (El -END SamePlane ;
N); N);
0.0) AND (E2 - 0.0)
If the intersection between the segment E and the hull of S is not an empty set, then the function procedure Hul llntersect returns TRUE, otherwise It returns FALSE. Procedure is based on mutual application of procedure OppSides.
Edge; S: Polygon):
BOOLEAN;
E.F, E.S) V[i1, NV)
AND THEN
PROCEDURE !IullIntersect(E:
VAR i: CARDINAL;
NV: Point; BEGIN
WITH S DO
FOR i ':= 1 TO No DO NV := V((i MOD No)+11 IF OppSides(V[i1, NV, OppSides(E.F, E.S, RETURN TRUE
END; END; END;
RETURN FALSE END HulllnLersect;
Function procedure CrossingPoint returns the piercing point between the segment E and the plane determined by polygon S. The procedure is called only when E is piercing the plane.
PROCEDURE CrossingPoint(E: Edge;
VAR R: Point;
Aa, Bb, Cc BEGIN WITH S Aa: =
S: Polygon):
Point;
Dd, L: REAL;
Bb:<
Cc:
Dd:
END; R [ .1 I : ■ R [ 2 1:1 R [ 3 ] : •
DO
(V[2 , 2 (VI3,2 (V[2,3 (V[2 ,1 (VI2, I (V(3,1 -V[1,1 -VI1,3] -VI1.2) +V[1,31 +V[1,11
+vl1,21
(Aa * E.F (Aa *(E. Cc*(F.
=E.F(11 =E.FI 2 ! ■E . F1 3 1
1—V[1,2 1-VU.2 1—V(1,3
1-vu.i
1-VM.l
I-vil.i
1 *(V[2, *(V[2,1 *(V[2 , 3 * ( VI 3 ,1 *(V[3 , 2 *(V12.1 [11+Bb* S[ll-E. S13 1-E
1)*(V[3,31 1)*(V[2,3] 1)*(V[3,11 1)*(V|3,31 1)*(V[3,2] 1)*(V[2,21 2 I—V[1,2]) —V11,1])* -VI1,31)* -VI1,11)* .—V11,2])* 1—V[1,1])* E.F[21+Cc* F[1J)+Bb*( • F [ 3 1 ) ) ;
-V|1,3 I) -VI1.3 I ) -Vll.il) —V11,31) —V(1,2))
-VU,21):
*(V[3,3|-V[1,31) (VI 3,21—V11,2]) (V[3,1]—V11,1]) (VI 2,2]—V11,2]) (VI 2,3]-V[1,3]) (V13,3]—V[1,3]); E.F131+Dd) / E . SI 2]—E.FI 2 ] ) +
BEGIN
IF InterExists(E, S) THEN IF SamePlane(E, S) THEN
IF Hull Intersect(E, S) THEN
RETURN TRUE ELSE
RETURN Internal(E.F, S) OR Internal(E.S, S)
END ELSE
RETURN Internal(CrossingPoint(E, S), S) END; END;
RETURN FALSE; END Intersect;
If the intersection of simple polyhndra P and Q is not an empty set, then the function procedure Polyhedralntersection returns TRUE, otherwise it returns FALSE.
PROCEDURE PolyhedraIntersect ion(P, Q:
Polyhedron): BOOLEAN;
VAR i, j: CARDINAL; BEGIN
FOR i : =1 TO P.NoF. DO FOR j :=1 TO Q.NoF DO
IF Intersect)Edg(P,i), Fac(Q.j)) THEN
RETURN TRUE END END END;
FOR i: =1 TO Q.NoE DO FOR j:=1 TO P.NoF DO
IF Intersect(Edg(Q,i), Fac(P.J)) THEN
RETURN TRUE END END END;
RETURN FALSE END Polyhedralntersection;
-I.* ( E.S[ 1 )—E. F[ 11 -L* ( E . S[ 2 ]-F.. FI 2 ] —L * ( E . S1 3 1 —E. F [ 3 1
RETURN R END CrossingPoint;
If the intersection between the segment E and the polygon S is not an empty set, then the function procedure Intersect returns TRUE, otherwise it returns FALSE. The procedure is based on afore-mentioned procedures and the algorittun described in section 2.2 of the paper.