Algorithm execution

Figures 6.6 and 6.7 show how the algorithm proceeds. Initially, $L$ is empty, and a doubly connected edge list is used to represent ${\cal C}_{free}$. Each connected component of ${\cal C}_{free}$ yields a single face in the data structure. Suppose inductively that after several events occur, $L$ is correctly maintained. For each event, one of the four cases in Figure 6.2 occurs. By maintaining $L$ in a balanced binary search tree [243], the edges above and below $p$ can be determined in $O(\lg n)$ time. This is much better than $O(n)$ time, which would arise from checking every segment. Depending on which of the four cases from Figure 6.2 occurs, different updates to $L$ are made. If the first case occurs, then two different edges are inserted, and the face of which $p$ is on the border is split two times by vertical line segments. For each of the two vertical line segments, two half-edges are added, and all faces and half-edges must be updated correctly (this operation is local in that only records adjacent to where the change occurs need to be updated). The next two cases in Figure 6.2 are simpler; only a single face split is made. For the final case, no splitting occurs.

Figure 6.6: There are $14$ events in this example.

Figure 6.7: The status of $L$ is shown after each of $14$ events occurs. Before the first event, $L$ is empty.

Once the face splitting operations have been performed, $L$ needs to be updated. When the sweep line crosses $p$, two edges are always affected. For example, in the first and last cases of Figure 6.2, two edges must be inserted into $L$ (the mirror images of these cases cause two edges to be deleted from $L$). If the middle two cases occur, then one edge is replaced by another in $L$. These insertion and deletion operations can be performed in $O(\lg n)$ time. Since there are $n$ events, the running time for the construction algorithm is $O(n \lg n)$.

The roadmap ${\cal G}$ can be computed from the face pointers of the doubly connected edge list. A more elegant approach is to incrementally build ${\cal G}$ at each event. In fact, all of the pointer maintenance required to obtain a consistent doubly connected edge list can be ignored if desired, as long as ${\cal G}$ is correctly built and the sample point is obtained for each cell along the way. We can even go one step further, by forgetting about the cell decomposition and directly building a topological graph of line-segment paths between all sample points of adjacent cells.