Practical Algorithms for 3D Computer Graphics, 2nd Edition

390 10. Modeling with polygonal datasets

Test whether an edge

joining these two vertices

of C lies inside C

p

m

p

i

i

i+1

N

C

P

Figure 10.13: Part of the test for containment of a point p

m

inside a piecewise linear

curve C. The test line L is checked for intersection with a piec e P of the fence bounding

the curve.

After cappingBefore capping

Figure 10.14: Triangulating the shape shown on the left gives the result on the right.

The shape contains nested holes.

If 0 ≤ µ ≤ 1 then C is crossed by L in C’s edge segment between

vertices i and i + 1. Note that in equation 10.1 any one of the

components of the vectors could be used to determine µ. To

prevent div is ion