| ||
First, we consider the arrangement A of a set of segments in the plane; see Figure 9.3. The set of segments represents a subdivision of the plane into cells, and we need to find a well-suited representation of the subdivision, i.e., a data structure that represents the combinatorial structure of the arrangement. The combinatorial structure of the arrangement consists of one-dimensional vertices, edges, and 2D cells. We may assume that we want to have access to all cells of the arrangement systematically. A single cell is given by the ordered sequence of the surrounding segments and the intersections in between. Thus, the whole arrangement can be represented by a planar graph G . Logically, a graph G = ( V,E ) is given by, a set of vertices V and a set of edges E . Physically, we will try to build a doubly connected edge list (DCEL). The efficient DCEL data structure, introduced in [Guibas and Stolfi 85], includes the combinatorial information of G and does not waste space for it. In fact, it is the most space-efficient way of storing a subdivision.
The DCEL of a planar graph gives access to the following information for every edge e of G :
a reference to the source and target vertices v 1 and v 2 of e ,
a reference to the left and right face F 1 and F 2 adjacent to e ,
a reference to the previous incoming edge (respectively ) at v 1 (respectively v 2 ),
Edge | Vertex | Faces | Incoming Edges | |||||
---|---|---|---|---|---|---|---|---|
Start | End | Left | Right | Next Start | Prev. End | Next End | Prev. End | |
e | v 1 | v 2 | F 1 | F 2 |
|
|
|
|
a reference to the next incoming edge (respectively ) at v 1 (respectively v 2 ).
Additionally, the DCEL contains:
a reference to a starting edge for every face F ,
a reference to the coordinates for every vertex v .
We further assume that we have access to the vertices, edges, and faces by their names . The terms previous and next refer to an ordering of the incoming edges in a clockwise or counterclockwise manner. The information of the reversed edge e = ( v 2 , v 1 ) is implicitly contained. Figure 9.4 shows the information of the DCEL for a single edge e ; see also Figure 9.8 for an example of the DCEL in 3D. With the help of the DCEL, we can perform a simple walk-through in the whole graph in time linear in the number of edges.
Any algorithm that builds the DCEL of A has to compute the intersections of the segments and has to order the segments by angle if three segments have a common intersection. This means that geometric predicates have to be evaluated precisely and intersections have to be computed exactly.
The subproblem of computing all intersections can be efficiently solved with the famous sweep paradigm; see [Bentley and Ottmann 79].
Let us consider a sketch of this idea. We assume that the segments are x -monotone and that intersections can be computed efficiently. If a segment is not x -monotone, we may split it into several segments if a vertical tangent occurs. For example, at the the vertical tangent t in Figure 9.5, we can split a non-monotone segment into two monotone segments. First, we sort the endpoints of the segments by x -coordinates and insert them into an event list . Now we will visit all events successively by a vertical sweepline that moves from right to left. During the sweep, we will maintain the important information along the sweepline in a sweep status structure . In case of the arrangement, the sweep status structure contains a sorted list of segments that intersect the sweepline. The list is sorted by the y -coordinates of the intersections. The idea is that just before two line segments intersect, they must have been neighbors in the sweep status structure. See Figure 9.5 for an example of the main steps in the sweep algorithm. The following three main events must be handled:
If a start point of a segment is met, we insert the new segment into the sorted list of segments. The new segment may have intersections with the neighboring segments in the segment list. We compute all next intersections with respect to the x -coordinates and insert them by x order into the event list. Note that at most two intersections with neighboring segments are inserted in the event list;
If an intersection event is met by the sweepline, we have to rearrange the order of the segments. Again, two segments have changed their order in the sweep status structure, and we perform an intersection test with the new neighbors as in the previous case;
If an endpoint of a segment is met, we delete this segment in the sweep status structure. An intersection test is required for the new neighboring segments.
As an invariant, the sweep status structure always contains the sorted list of segments intersected by the sweepline. The neighboring segments are tested for intersections. Obviously, the invariant belongs to the combinatorial part of the algorithm.
During the sweep, we will collect all intersections, which are part of the information needed for the DCEL. Let us assume for a moment that we have to deal with line segments represented by their endpoints; that is, let l i = ( p i , q i ), where p i = ( , ) and q i = ( , ). If an intersection ( x, y ) of l 1 and l 2 exists, it can be computed adequately by
where a i = ( ˆ ), b i = ( ˆ ), and for i = 1 , 2; see also Section 9.4.2. This is the numerical part of the algorithm.
If the x -coordinates of the intersections are not computed exactly, two actually neighboring segments will eventually not appear as neighbors during the sweep. The event list may have an incorrect order. In this inconsistent situation, we have lost information for the DCEL due to impreciseness. The invariant is no longer valid, and the result will be incomplete. Note that for the flow of the algorithm, it suffices to compare the x -coordinates of intersections or endpoints of line segments, rather than computing the intersection coordinates. However, comparisons may be erroneous as well.
Ramshaws braided lines example [Nievergelt and Hinrichs 93, Nievergelt and Schorn 88] shows that naively applied floating-point arithmetic cannot guarantee preciseness for intersections. Unfortunately, the lines l 1 : 4 . 3 — x/ 8 . 3 and l 2 : 1 . 4 — x/ 2 . 7 seem to have several intersections if floating-point arithmetic with base 10, precision 2, and rounding to nearest is used; see Figure 9.6. For the details of floating-point arithmetic; see Section 9.3.1.
The running time of the presented algorithm is given by O (( n + k ) log n ), where k denotes the number of intersections.
Let us consider a simple 3D example where we do not need to compute intermediate results, which seems to be the problem of the previous section. We want to find the intersecting edges of a convex polyhedron with a hyperplane in 3D; see Figure 9.7. Let us assume that the polyhedron is given by a graph G = ( V, E ). The underlying data structure should be a DCEL in 3D. In analogy to the 2D case, the DCEL contains the following information for every edge e of every tetrahedron T :
a reference to the source and target vertices v 1 and v 2 of e ,
a reference to the left and right face F 1 and F 2 adjacent to e ,
a reference to the next edge with respect to the left face F 1 ,
a reference to the previous edge with respect to the right face F 2 .
The orientations left and right correspond to the orientation of the edge e . We consider the edge from the outer side of T . We can move one adjacent face into the plane of the other without an intersection of the faces. Now with respect to the orientation of the edge, one face lies to the left of e and the other edge lies to the right of e . These orientations are uniquely determined. Every edge has an orientation from the start point to the endpoint.
Additionally, we keep track of the following information:
a reference to the normal for every face F ,
a reference to a starting edge for every face F ,
a reference to the coordinates for every vertex v .
We can assume that access to the vertices, edges, and faces is given by their names. Figure 9.8 together with Table 9.2 show the DCEL of a single tetrahedron. Note that for every edge e i = ( , ), there also has to be an entry = ( , ), and a link between e i and is stored.
Edge | Vertex | Faces | Edges | |||
---|---|---|---|---|---|---|
Start | End | Left | Right | Next | Prev. | |
e 1 | v 1 | v 2 | F 1 | F 2 | e 5 | e 6 |
e 2 | v 2 | v 3 | F 4 | F 2 | e 3 | e 1 |
e 3 | v 3 | v 4 | F 4 | F 3 | e 5 | e 6 |
e 4 | v 1 | v 4 | F 3 | F 1 | e 3 | e 1 |
e 5 | v 2 | v 4 | F 1 | F 4 | e 4 | e 2 |
e 6 | v 1 | v 3 | F 2 | F 3 | e 2 | e 4 |
A general graph in 3D may represent a set of polyhedra. For example, the Voronoi diagram in 3D represents a subdivision of the plane into convex polyhe dra; see Chapter 6. In this case, every polyhedron is represented by the corresponding information. Additionally, for every edge e , there is a reference to the next polyhedron of e , sorted in clockwise or counterclockwise order. Altogether, we can easily trace the graph, visiting all edges and vertices.
For a simple geometric algorithm, we need to know whether a vertex of the polyhedron P lies above or below the hyperplane H . There is a simple and efficient predicate for this test. We have to compute the sign of the determinant
where v = ( v x , v y , v z ) denotes a vertex of P and the vectors = ( a x , a y , a z ), = ( b x , b y , b z ), and = ( c x , c y , c z ) span the hyperplane H . If and only if Det( a, b, c, v ) > 0 holds, vertex v is below the oriented plane H formed by a , b , and c . The plane is meant to be oriented as follows . If we see the points a , b , and c in a counterclockwise order, the plane is seen from above . In Section 9.4 we will give a formal motivation and a generalized form of this so-called orientation test .
Now, the problem arises that the sign of the determinant Det( a, b, c, v ) cannot be evaluated precisely in all cases. For example, a face of P may be almost parallel and very close to the hyperplane H . In this case, roundoff errors may produce incorrect results, and any algorithm will fail to compute the correct result. On the other hand, it might even happen that a vertex of P lies exactly on H . Any algorithm has to make a decision for a degenerate case.
Note that a simple incremental algorithm correctly computes the convex hull in 3D by using a correct orientation test only; see [Sugihara 94].