366
M.A. Chapman et al.
The Point-in-Polygon Problem
In order to determine the position of a point with respect to a polygon, the polygon may
first be decomposed into several triangles (2-D primitive objects), and then, the
position of the point is examined with respect to the triangles. A triangle can be
represented in a normalized homogeneous coordinate system by its vertex coordinates:
(0, 0, 1), (0, 1, 0), and (1, 0, 0), as shown in Fig. 8. Assuming the coordinates of the
points to be examined are given as
then if any coordinate of the point is equal
to 1, the point is located on the boundary of the triangle. If any coordinate of the test
point is greater than 1 or less than zero, it indicates that the point is located outside the
triangle. Finally, if all of the coordinates of the desired point in the homogeneous
coordinate system are less than one, and greater than zero the point is located inside
the polygon. The above procedure has been used to address a point-in-polygon problem
presented in Table 1.