9.1. Examples of Instability in Geometric Algorithms

9.1. Examples of Instability in Geometric Algorithms

9.1.1. Intersections of Line Segments

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.

image from book
Figure 9.3: The arrangement of a set of segments represents a subdivision of the plane into cells represented by vertices and edges.

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 image from book (respectively image from book ) at v 1 (respectively v 2 ),

    Table 9.1: References for a single edge e in the DCEL of a graph in 2D.

    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

    image from book

    image from book

    image from book

    image from book

  • a reference to the next incoming edge image from book (respectively image from book ) 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.

image from book
Figure 9.4: An edge of the arrangement and its information in the DCEL.
image from book
Figure 9.8: The DCEL information of a tetrahedron T. The faces F 1 and F 2 of the oriented edge e 1 have next edge e 5 and previous edge e 6 .

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.

image from book
Figure 9.5: The sweep status structure contains a sorted list of the segments met by the sweepline. At position i), a new segment has to be inserted and the intersections with its neighbors will create future events. At position ii), such a new event changes the order of the segments, intersections are computed, and further future events may be created.

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 = ( image from book , image from book ) and q i = ( image from book , image from book ). If an intersection ( x, y ) of l 1 and l 2 exists, it can be computed adequately by

image from book

where a i = ( image from book ˆ image from book ), b i = ( image from book ˆ image from book ), and image from book 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.

image from book
Figure 9.6: The lines l 1 : 4.3 — x/8.3 and l 2 : 1.4 — x/2.7 appear to have several intersections using floating-point evaluation with base 10, precision 2, and round to nearest.

The running time of the presented algorithm is given by O (( n + k ) log n ), where k denotes the number of intersections.

9.1.2. Cutting a Polyhedron by a Hyperplane

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 image from book with respect to the left face F 1 ,

  • a reference to the previous edge image from book with respect to the right face F 2 .

image from book
Figure 9.7: Cutting a polyhedron by a hyperplane.

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 = ( image from book , image from book ), there also has to be an entry image from book = ( image from book , image from book ), and a link between e i and image from book is stored.

Table 9.2: References in the DCEL of a polyhedron.

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

image from book

where v = ( v x , v y , v z ) denotes a vertex of P and the vectors image from book = ( a x , a y , a z ), image from book = ( b x , b y , b z ), and image from book = ( 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].



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net