Notes Geometric Modelling Convex Polygons

Convex Polygons

11 Oct 2023

§ Statement

Determining if $\mathcal{P} \subset \mathbb{E}$ is a Convex Polygon

Suppose we are given points $\mathcal{P} = \{P_i\}_{i=0}^{n-1} \subset \mathbb{E}^2$ that yields a closed polygon $P_c : P_0 P_1 \dots P_{n-1} P_0$ when they are connected in the given order.

How can we determine whether $P_c$ is closed, if so, it is convex?

§ 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

Detecting a Convex Polygon

# Input: Set of points $\mathcal{P} = \{P_i\}_{i=0}^{n-1}$ with ordering $P_c \in \mathfrak{S}(\mathcal{P})$
# Output: Determination of polygon is CONVEX, NOT_CONVEX, or INVALID
# Note: NOT_CONVEX $\neq$ CONCAVE; it indicates a change in winding order
# (i.e. anticlockwise to clockwise, or vice versa).
# It is a trivial modification to check if $\mathcal{P}$ is CONCAVE
function DetectConvex( $\mathcal{P}, P_c$ $P, P_{c}$ )
- if $n \leq 2$ then
  - return INVALID
- $\theta$ $\leftarrow$ $0$
- for all $i$ in $\mathbb{Z}_n$ do
  - Get vertices $P_i, P_{i-1}, P_{i-2}$ from $P_c$
  - sign $\leftarrow$ $\mathrm{sgn}(\mathrm{area}(\triangle P_{i}P_{i+1}P_{i+2}))$
  - if direction is undefined then
    - direction $\leftarrow$ sign
  - if sign <> direction then
    - return NOT_CONVEX
  - $e_1$ $\leftarrow$ $\overline{P_{i+1}P_i}$
  - $e_2$ $\leftarrow$ $\overline{P_{i+2}P_{i+1}}$
  - $\theta$ $\leftarrow$ $\theta + \mathrm{angle}(e_1, e_2)$
- if $\theta$ <> $180(n - 2)$ then
  - return INVALID
- return CONVEX

Complexity Analysis

This method has $\mathcal{O}(n)$ complexity, as we iterate through each point once per step and the computations in each iteration are all constant constant with respect to the input $\mathcal{P}$ .