The assumption that is convex is too limited for most applications. Now suppose that is a nonconvex, polygonal subset of . In this case can be expressed as
In general, more complicated representations of 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 that contains3.1 . This is equivalent to keeping all points such that , which is equivalent to . This can be used to define a new primitive , which when taken in union with other sets, is equivalent to the removal of . 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 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 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 is to apply the vertical cell decomposition algorithm, which will be presented in Section 6.2.2
Steven M LaValle 2012-04-20