Convex Polygons

§ Statement

§ Solution

A necessary and sufficient condition for whether $P_c$ is a polygon is for the interior angles summing to $180(n - 2)^\circ$, where $n$ is the number of edges; all polygons, convex or concave, have this property.

Next, if $P_c$ convex, then every pair of edges must turn in the same direction.

The direction of turning can be found by using the determinant definition for the area of a triangle,

$$\begin{align*} \mathrm{area}(\triangle P_iP_{i+1}P_{i+2}) &= \frac{1}{2}\det (\langle P_i, 1\rangle, \langle P_{i+1}, 1\rangle, \langle P_{i+2}, 1\rangle), \end{align*}$$

if the sign of the area does not match for all $i \in \mathbb{Z}_n$, then we reject $P_c$ and say that it is not a convex polygon.

Next, we compute the interior angles of each pair of edges formed by points $P_i, P_{i+1}, P_{i+2} \in \mathcal{P}$ and $i \in \mathbb{Z}_n$.

To do this, we define two vectors $A = P_{i + 1} - P_i$ and $B = P_{i + 2} - P_{i + 1}$, then the angle $\theta_i$ can be found by

$$\begin{align*} \theta_i &= \arccos \left[\frac{A \cdot B}{\|A\|\|B\|}\right] \end{align*}$$

Therefore, if the sum of interior angles satisfies

$$\begin{align*} \sum_{i=0}^{n-1} \theta_i = 180(n - 2), \end{align*}$$

then we accept $P_c$ and say that it is a convex polygon; otherwise, we reject $P_c$.

§ Algorithm