Practical Algorithms for 3D Computer Graphics, 2nd Edition

10.2. Triangulating polygo n s with holes 385

(a)

i

i+1

i–1

i+2

i+1

P

m

i+2

C

C

(b)

i

Figure 10.9: Additional tests will need to be added to the procedure for determining

whether a point lies inside an polygon. In (a) an edge joining vertices i with i+2 would

form a triangle with zero area. In (b) the edge joining vertices i with i + 2 is partially

outside the polygon.

2. In the situation illustrated in figure 10.9(b) the mid-point of the edge

joining vertices i and i +2, p

m

is inside C b u t other edges of C intersect it.

In this case ver tex i should not be joined to vertex i + 2. To prevent edges

being falsely labeled as internal an additional test should be