Designing and implementing a general purpose halfedge data structur
Written with coauthor.
Abstract:
Halfedge data structures (HDS) are fundamental in representing
combinatorial
geometric structures, useful for representing any planar structures such
as
plane graphs and planar maps, polyhedral surfaces and boundary
representations
(BREPs), two-dimensional views of a three dimensional scene, etc. Many
variants
have been proposed in the literature, starting with the winged-edge data
structure
of Baumgart, the DCEL,
the quad-edge data structure of Guibas and Stolfi, the halfedge data
structure of Weiler et al.
This paper extends the excellent study presented by Kettner
for the
CGAL library, by providing a generic and all-purpose design for the
entire
family of halfedge data structures and their variants. We validate the
approach
in a C++ template library, the HDSTL, which is described in the paper.
Related Publications:
Copyright © 2002, 2003, Hervé Brönnimann, hbr@poly.edu
