Mathematical Structures for Computer Graphics

6.3 Polyhedra

6.2.3 Inside and Outside

As with triangles in particular, checking a point to see if it is inside or outside of a polygon is a common task in graphics. Barycentric coordinates formed a key tool in working with triangles, but, although generalizing these coordinates to arbitrary polygons can work for convex polygons, it is not practical for concave polygons. In the case of convex polygons, one approach defines the barycentric coordinates as ratios of areas much like the case for triangles. However, the areas used are more complicated than those used for triangles (See Section 6.4 for details).

Recall that the point is the centroid of a triangle and is inside the triangle. It is natural to consider the point for an arbitrary polygon with vertices. Assume the polygon is convex. Then, the affine combination of two vertices and is on the edge of the polygon, and hence we consider it inside the polygon. Moving up one step to three vertices, the affine combination of three ...