Planar Straight Line Graphs:Further Remarks

Further Remarks

We have assumed that each face in the PSLG has exactly one boundary. This requirement can be relaxed for the winged-edge and the half edge data structures. One method works as follows. For each face f , pick one edge from each boundary and keep a list of references to these edges at the face record for f . Also, the edge that belongs to outer boundary of f is specially tagged. With this modification, one can traverse the boundaries of a face f consistently (e.g., keeping f on the left of traversal direction). The edge insertion and deletion algorithms also need to be enhanced. Since a face f may have several boundaries, inserting an edge may combine two boundaries without splitting f . If the insertion indeed splits f , one needs to distribute the other boundaries of f into the two faces resulting from the split. The reverse effects of edge deletion should be taken care of similarly.

The half edge data structure has also been used for representing orient able polyhedral surfaces [10]. The full power of the quad edge data structure is only realized when one deals with both subdivisions of orient able and non-orient able surfaces. To this end, one needs to introduce a flip bit to allow viewing the surface from the above or below. The primitives need to be enhanced for this purpose. The correctness of the data structure is proven formally using edge algebra. The details are in the Guibas and Stolfi’s original paper [8].

The vertex split and edge contraction are also applicable for polyhedral surfaces. The edge contractibility criteria carries over straightforwardly. Edge contraction is a popular primitive for surface simplification algorithms [4, 7, 9]. The edge contractibility criteria for non-manifolds has also been studied [5].

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout