Defining the vertical decomposition

We next present an algorithm that constructs a vertical cell decomposition [189], which partitions $ {\cal C}_{free}$ into a finite collection of 2-cells and 1-cells. Each 2-cell is either a trapezoid that has vertical sides or a triangle (which is a degenerate trapezoid). For this reason, the method is sometimes called trapezoidal decomposition. The decomposition is defined as follows. Let $ P$ denote the set of vertices used to define $ {\cal C}_{obs}$. At every $ p \in P$, try to extend rays upward and downward through $ {\cal C}_{free}$, until $ {\cal C}_{obs}$ is hit. There are four possible cases, as shown in Figure 6.2, depending on whether or not it is possible to extend in each of the two directions. If $ {\cal C}_{free}$ is partitioned according to these rays, then a vertical decomposition results. Extending these rays for the example in Figure 6.3a leads to the decomposition of $ {\cal C}_{free}$ shown in Figure 6.3b. Note that only trapezoids and triangles are obtained for the 2-cells in $ {\cal C}_{free}$.

Figure 6.3: The vertical cell decomposition method uses the cells to construct a roadmap, which is searched to yield a solution to a query.
...vertical1.idr,width=2.7in} \\
(a) & (b)

Every 1-cell is a vertical segment that serves as the border between two 2-cells. We must ensure that the topology of $ {\cal C}_{free}$ is correctly represented. Recall that $ {\cal C}_{free}$ was defined to be an open set. Every 2-cell is actually defined to be an open set in $ {\mathbb{R}}^2$; thus, it is the interior of a trapezoid or triangle. The 1-cells are the interiors of segments. It is tempting to make 0-cells, which correspond to the endpoints of segments, but these are not allowed because they lie in $ {\cal C}_{obs}$.

Steven M LaValle 2012-04-20