Points Inside Triangles and Quadrilaterals

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

In the case of triangles and quadrilaterals, the approaches presented are very efficient when it is necessary to perform comparisons between a single polygon and a large number of points, as such techniques allow the use of precalculations: the fundamental idea is to exploit a transformation of the polygon's coordinate space into a space where comparisons are 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 applies to triangles formed by the same generating vectors, but with the comparison $0<X(\mathbf{p})<1$ and $0<Y(\mathbf{p})<1-X(\mathbf{p})$. To determine if a point lies inside the parallelogram, only 4 multiplications and 6 additions are necessary. The cost of creating the affine transformation is higher, but if the number of comparisons is large, this constant overhead becomes negligible.

To transform generic quadrilaterals into a unit square $(0,0)-(1,1)$, one must instead use the homographic transformation (see section 1.10). Despite the high initial cost of creating the transformation, the check for 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.86)

thus limited to 6 multiplications, 6 sums, and 4 comparisons.