Using Generic Programming for Designing a Data Structure for Polyhedral Surfaces. Lutz Kettner. In: Computational Geometry - Theory and Applications 13, pp. 65-90, 1999.
Software design solutions are presented for combinatorial data structures, such as polyhedral surfaces and planar maps, tailored for program libraries in computational geometry. Design issues considered are flexibility, time and space efficiency, and ease-of-use. We focus on topological aspects of polyhedral surfaces and evaluate edge-based representations with respect to our 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.
Key words: Library design; Generic programming; Combinatorial data structure; Polyhedral surface; Halfedge data structure
[PostScript Preprint] © Elsevier 1999.