 | The ACM Journal of Experimental Algorithmics |
Volume 5, Article 13, 2000
The Design and Implementation of Planar Maps in CGAL
by
and
and
Iddo Hanniel
and
and
http://www.jea.acm.org/2000/FlatoPlanar/
Abstract:
Abstract Planar maps are fundamental structures in computational geometry. They
are used to represent the subdivision of the plane into regions and have
numerous applications. We describe the planar map package of Cgal1 -- 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 introduce the two main classes of the
design -- planar maps and topological maps that enable the convenient separation
between geometry and topolog y. 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 se t 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.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated October 11, 2001, by editor@jea.acm.org