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