Points Inside Triangles and Quadrilaterals

Consider the problem of determining whether a point lies inside relatively simple polygons such as triangles or quadrilaterals. The treatment of the general polygon case is more complex and is left to the reader (and can optionally be reduced to the triangle/quadrilateral case).

For triangles and quadrilaterals, the approaches presented are highly efficient when comparisons must be performed between a single polygon and a large number of points, since these techniques allow precomputation: the basic idea is to exploit a transformation from the polygon's coordinate space into a space where the comparison is easier to perform.

For example, a parallelogram formed by two generating vectors can always be transformed into a unit square $(0,0)-(1,1)$ through an affine transformation $\mathbf{p} \mapsto \left( X, Y \right)$. A point $\mathbf {p}$ lies inside the parallelogram if $0<X(\mathbf{p})<1$ and $0<Y(\mathbf{p})<1$. The same transformation also applies to triangles formed by the same generating vectors, but with the conditions $0<X(\mathbf{p})<1$ and $0<Y(\mathbf{p})<1-X(\mathbf{p})$. Determining whether a point lies inside the parallelogram requires only 4 multiplications and 6 additions. Creating the affine transformation is more expensive, but when the number of comparisons is large, this fixed cost becomes negligible.

To transform generic quadrilaterals into a unit square $(0,0)-(1,1)$, the homographic transformation must be used instead (see Section 1.11). Despite the high initial cost of constructing the transformation, checking whether a point belongs to the geometric figure is relatively simple:

$$\begin{array}{l} 0<h_0 p_x + h_1 p_y + h_2 < h_6 p_x + h_7 p... ...3 p_x + h_4 p_y + h_5 < h_6 p_x + h_7 p_y + h_8 \\ \end{array}$$ (1.127)

and therefore requires only 6 multiplications, 6 additions, and 4 comparisons.