Designing a data structure for polyhedral surfaces
Lutz Kettner · 1998
Design solutions for a program library are presented for combinatorial data structures in computational geometry, such as planar maps and polyhedral surfaces. Design issues considered are genericity, flexibility, time and space efficiency, and ease-of-use. We focus on topological aspects of polyhedral surfaces. Edge-based representations for polyhedrons are evaluated with respect to the design goals. A design for polyhedral surfaces in a halfedge data structure is developed following the generic programming paradigm known from the Standard Template Library STL for C++. Connections are shown to planar maps and face-based structures managing holes in facets. 1 Introduction Combinatorial structures, such as planar maps, are fundamental in computational geometry. In order to use computational geometry in practice, a solid library must provide generic and flexible solutions as one of its fundamental cornerstones. Other design criteria are time and space efficiency. Ease-of-use is necessar...