Nonconvex polygons

The assumption that ${\cal O}$ is convex is too limited for most applications. Now suppose that ${\cal O}$ is a nonconvex, polygonal subset of ${\cal W}$. In this case ${\cal O}$ can be expressed as

$${\cal O}= {\cal O}_1 \cup {\cal O}_2 \cup \cdots \cup {\cal O}_n ,$$ (3.4)

in which each ${\cal O}_i$ is a convex, polygonal set that is expressed in terms of half-planes using (3.3). Note that ${\cal O}_i$ and ${\cal O}_j$ for $i \not = j$ need not be disjoint. Using this representation, very complicated obstacle regions in ${\cal W}$ can be defined. Although these regions may contain multiple components and holes, if ${\cal O}$ is bounded (i.e., ${\cal O}$ will fit inside of a big enough rectangular box), its boundary will consist of linear segments.

In general, more complicated representations of ${\cal O}$ can be defined in terms of any finite combination of unions, intersections, and set differences of primitives; however, it is always possible to simplify the representation into the form given by (3.3) and (3.4). A set difference can be avoided by redefining the primitive. Suppose the model requires removing a set defined by a primitive $H_i$ that contains^3.1 $f_i(x,y) < 0$. This is equivalent to keeping all points such that $f_i(x,y) \geq 0$, which is equivalent to $-f_i(x,y) \leq 0$. This can be used to define a new primitive $H^\prime_i$, which when taken in union with other sets, is equivalent to the removal of $H_i$. Given a complicated combination of primitives, once set differences are removed, the expression can be simplified into a finite union of finite intersections by applying Boolean algebra laws.

Note that the representation of a nonconvex polygon is not unique. There are many ways to decompose ${\cal O}$ into convex components. The decomposition should be carefully selected to optimize computational performance in whatever algorithms that model will be used. In most cases, the components may even be allowed to overlap. Ideally, it seems that it would be nice to represent ${\cal O}$ with the minimum number of primitives, but automating such a decomposition may lead to an NP-hard problem (see Section 6.5.1 for a brief overview of NP-hardness). One efficient, practical way to decompose ${\cal O}$ is to apply the vertical cell decomposition algorithm, which will be presented in Section 6.2.2