AbstractPlanar maps are fundamental structures in computational geometry. They are used to represent the sub- division of the plane into regions and have numerous applications. We describe the planar map package of Cgal -- the Computational Geometry Algorithms Library. We discuss problems that arose in the design and implementation of the package and report the solutions we have found for them. In particular we in- troduce the two main classes of the design--planar maps and topological maps that enable the convenient separation between geometry and topology. We also describe the geometric traits which make our package flexible by enabling to use it with any family of curves as long as the user supplies a small set of operations for the family. Finally, we present the algorithms we implemented for point location in the map, together with experimental results that compare their performance.
- E. Flato, D. Halperin, I. Hanniel, O. Nechushtan and E. Ezra
The Design and Implementation of Planar Maps in CGAL
ACM Journal of Experimental Algorithmics, 5: 13, Special Issue, selected papers of the Workshop on Algorithm Engineering (WAE), 2000 [link] [bibtex]
A preliminary version appeared in Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE), 1668: 154-168, Springer, LNCS, London, 1999 [link] [bibtex]
- CGAL Class Topological_map Programming Guide
- CGAL Class Planar_map Programming Guide