Computer Aided Engineering Design

282 COMPUTER AIDED ENGINEERING DESIGN

Example 9.3. A quadrilateral is defined by A (1, –1), B (0, 5), C (–1, –1) and D (0, 3). Determine if
pointE (0, 1) lies within this polygon or not.

(a) Determine if test point E is coinciding with any of the vertices of polygon ABCD.

Distance from EtoAis (1 – 0) + (1 + 1) = 5^22 > 0, thus implying Eis not coincident with A.

Similarly, distance from E to B,C and D are > 0. Thus test point E is not coincident with any of the
vertices of the polygon ABCD.

(b) Determine if test point is lying on boundary of polygon ABCD.
Find determinant Δ of triangle ABE.

ΔABE =

1–11

051

011

= 4 0≠

This implies that E is not on AB. Similarly, ΔBCE,ΔCDE and ΔDAE are not equal to zero and thus
E does not lie on the boundary of ABCD.

(c) Determine the ‘in’ or ‘out’ status by ray shooting algorithm.
Determine a point outside polygon ABCD along x-axis to throw a ray to the test point E. The xmax of
the polygon is 1 and thus a ray can be shot from point F (2 (>xmax), 1 (y-coordinate of E)).
Determine the number of crossings the ray EF makes with the polygon ABCD to reach F from E.
Initialize a counter count = 0.
Find if EF intersects with the edge AB.
SinceΔABE= 4, ΔABF = –8 and ΔEFA = – 4, ΔEFB = 8 are pair wise opposite in sign, EF and AB
intersect. Increment the counter (count = 1).
Similarly, EF does not intersect BC, CD and intersects DA (count = 2). Since number of crossings
is even, E is outside ABCD. Figure 9.9 illustrates the procedure.

9.4 Proximity Between a Point and a Plane

Consider a point D (x 4 ,y 4 ,z 4 ) and a plane specified three points A (x 1 ,y 1 ,z 1 ),B (x 2 ,y 2 ,z 2 ) and

Figure 9.9 Example 9.3 on point in polygon

yyy

B B

B

D D D

E E F E

F

O O O

C A

x x x

C A

C A

(a) Polygon ABCD and test point E (b) Bounding box of ABCD

and ray determination

(c) Crossings test