First consider for the case in which the obstacle region is a
convex, polygonal subset of a 2D world,
. A subset
is called *convex* if and only
if, for any pair of points in , all points along the line segment
that connects them are contained in . More precisely, this means
that for any
and
,

(3.1) |

Thus, interpolation between and always yields points in . Intuitively, contains no pockets or indentations. A set that is not convex is called

A boundary representation of is an -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, ,
, , , of points in
, given in
counterclockwise order.

A solid representation of can be expressed as the intersection of 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 and . Consider the equation of a line that passes through and . An equation can be determined of the form , in which are constants that are determined from , , , and . Let be the function given by . Note that on one side of the line, and on the other. (In fact, may be interpreted as a signed Euclidean distance from to the line.) The sign of indicates a half-plane that is bounded by the line, as depicted in Figure 3.2. Without loss of generality, assume that is defined so that for all points to the left of the edge from to (if it is not, then multiply by ).

Let denote the function derived from the line that
corresponds to the edge from to
for
. Let denote the line equation that corresponds
to the edge from to . Let a *half-plane*
for
be defined as a subset of :

Above, is a primitive that describes the set of all points on one side of the line (including the points on the line). A convex, -sided, polygonal obstacle region is expressed as

Steven M LaValle 2012-04-20