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.

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}$.