Computer Aided Engineering Design

COMPUTATIONS FOR GEOMETRIC DESIGN 281

convex polygon if it lies to the left of all the edges (maintaining counterclockwise traverse). This is
illustrated in Figure 9.8 (a). A faster version is to check whether the point lies outside the bounding
box before the actual queries described above for both convex and non-convex polygons are made
(Figure 9.8 b).

Figure 9.6 The crossings check

(a) Odd number of crossings; point is inside (b) Even number of crossings; point is outside

Figure 9.7 Crossings test for a ray passing through a vertex

(a) Point inside a convex polygon (b) Point outside the bounding box

Figure 9.8 Faster point-in-polygon checks