Convex polygons

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 nonconvex (as opposed to concave, which seems better suited for lenses).

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 :

 (3.2)

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

 (3.3)

Steven M LaValle 2012-04-20