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]$,

$\displaystyle \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}$:

$\displaystyle 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

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

Steven M LaValle 2012-04-20