Convex polygons

First consider ${\cal O}$ for the case in which the obstacle region is a convex, polygonal subset of a 2D world, ${\cal W}= {\mathbb{R}}^2$. A subset $X \subset {\mathbb{R}}^n$ is called convex if and only if, for any pair of points in $X$, all points along the line segment that connects them are contained in $X$. More precisely, this means that for any $x_1,x_2 \in X$ and $\lambda \in [0,1]$,

$$\lambda x_1 + (1-\lambda) x_2 \in X .$$ (3.1)

Thus, interpolation between $x_1$ and $x_2$ always yields points in $X$. Intuitively, $X$ contains no pockets or indentations. A set that is not convex is called nonconvex (as opposed to concave, which seems better suited for lenses).

A boundary representation of ${\cal O}$ is an $m$-sided polygon, which can be described using two kinds of features: vertices and edges. Every vertex corresponds to a ``corner'' of the polygon, and every edge corresponds to a line segment between a pair of vertices. The polygon can be specified by a sequence, $(x_1,y_1)$, $(x_2,y_2)$, $\ldots$, $(x_m,y_m)$, of $m$ points in ${\mathbb{R}}^2$, given in counterclockwise order.

A solid representation of ${\cal O}$ can be expressed as the intersection of $m$ half-planes. Each half-plane corresponds to the set of all points that lie to one side of a line that is common to a polygon edge. Figure 3.1 shows an example of an octagon that is represented as the intersection of eight half-planes.

An edge of the polygon is specified by two points, such as $(x_1,y_1)$ and $(x_2,y_2)$. Consider the equation of a line that passes through $(x_1,y_1)$ and $(x_2,y_2)$. An equation can be determined of the form $a x + b y + c = 0$, in which $a,b,c \in {\mathbb{R}}$ are constants that are determined from $x_1$, $y_1$, $x_2$, and $y_2$. Let $f : {\mathbb{R}}^2 \rightarrow {\mathbb{R}}$ be the function given by $f(x,y) = a x + b y + c$. Note that $f(x,y)<0$ on one side of the line, and $f(x,y)>0$ on the other. (In fact, $f$ may be interpreted as a signed Euclidean distance from $(x,y)$ to the line.) The sign of $f(x,y)$ indicates a half-plane that is bounded by the line, as depicted in Figure 3.2. Without loss of generality, assume that $f(x,y)$ is defined so that $f(x,y)<0$ for all points to the left of the edge from $(x_1,y_1)$ to $(x_2,y_2)$ (if it is not, then multiply $f(x,y)$ by $-1$).

Figure 3.1: A convex polygonal region can be identified by the intersection of half-planes.

Figure 3.2: The sign of the $f(x,y)$ partitions ${\mathbb{R}}^2$ into three regions: two half-planes given by $f(x,y)<0$ and $f(x,y)>0$, and the line $f(x,y)=0$.

Let $f_i(x,y)$ denote the $f$ function derived from the line that corresponds to the edge from $(x_i,y_i)$ to $(x_{i+1},y_{i+1})$ for $1 \leq i < m$. Let $f_m(x,y)$ denote the line equation that corresponds to the edge from $(x_m,y_m)$ to $(x_1,y_1)$. Let a half-plane $H_i$ for $1 \leq i \leq m$ be defined as a subset of ${\cal W}$:

$$H_i = \{ (x,y) \in {\cal W}\;\vert\; f_i(x,y) \leq 0 \} .$$ (3.2)

Above, $H_i$ is a primitive that describes the set of all points on one side of the line $f_i(x,y) = 0$ (including the points on the line). A convex, $m$-sided, polygonal obstacle region ${\cal O}$ is expressed as

$${\cal O}= H_1 \cap H_2 \cap \cdots \cap H_m .$$ (3.3)