## Sunday, May 28, 2017

### Efficient polygon area computation with less multiplications.

Linear algebra computations typically try to prefer mathematical formulations which preserve numerical precision, reduce multiplications and avoid divisions if possible. More recently I came across an elegant formulation of polygon area computation with half the number of multiplications relative to the standard method. I will try to briefly derive it for posterity.

Standard Formulation: Let $P = [v_0, v_1, v_2, v_3\ldots v_{n-1}, v_{n}=v_0]$ be a polygon with $n$ vertices, $v_i = (x_i,y_i)$. Recall the standard formula for the area of the polygon $A(P) = \sum_{i=0}^{n-1} (x_{i}y_{i+1} - y_{i}x_{i+1})$. Every term $T(i) = (x_{i}y_{i+1} - y_{i}x_{i+1})$ corresponds to the edge $(v_i, v_{i+1})$ of the polygon -- more precisely this is the signed area of the triangle ${(0,0), (x_i,y_i), (x_{i+1}, y_{i+1})}$. Clearly computation of $A(P) = \sum_{i=0}^{n-1} T(i)$ needs exactly $2n$ multiplication operations.

Alternate Formulation: Consider $T(i) = x_{i}y_{i+1} - y_{i}x_{i+1}$, now add $x_iy_i$ and subtract $x_{i+1}y_{i+1}$ resulting in the following:
$$\begin{array}{lll} D(i) &=& x_iy_i + T(i) - x_{i+1}y_{i+1} \\ D(i) + D(i+1) &=& x_iy_i + T(i) - x_{i+1}y_{i+1} + x_{i+1}y_{i+1} + T(i+1) - x_{i+2}y_{i+2} \\ &=& x_iy_i + T(i) + T(i+1) - x_{i+2}y_{i+2}\\ \sum_{i=0}^{n-1}D(i) &=& x_{0}y_{0} + \sum_{i=0}^{n-1} T(i) - x_ny_n\,\, \mbox{notice that}\, (x_0,y_0) = (x_n,y_n)\\ &=& \sum_{i=0}^{n-1} T(i) \end{array}$$

Whats special about $D(i) = x_iy_i + T(i) - x_{i+1}y_{i+1}$ ?. Notice that $D(i)$ can be written as the following:
$$\begin{array}{lll} D(i) &=& x_iy_i + T(i) - x_{i+1}y_{i+1} \\ &=& x_iy_i + (x_iy_{i+1} - x_{i+1}y_i) - x_{i+1}y_{i+1} \\ &=& (x_i + x_{i+1})(y_i - y_{i+1}) \,\, \mbox{notice the only one multiplication}. \end{array}$$

Finally we state that the area of the polygon is equivalent to $A(P) = \sum_{i=0}^{n-1} (x_i+x_{i+1})(y_i - y_{i+1})$ and needs exactly $n$ multiplications instead of $2n$ with standard formulation.