Arrangements
![[Circle Arrangement]](circ2.gif)
Abstract
Given a collection C of curves in the plane, the arrangement of C is the subdivision of the plane into vertices, edges and faces induced by the curves in C Constructing arrangements of curves in the plane is a basic problem in computational geometry. Applications relying on arrangements arise in fields such as robotics, computer vision and computer graphics. Many algorithms for constructing and maintaining arrangements under various conditions have been published in papers. However, there are not many implementations of (general) arrangements packages publicly available. We present an implementation of a generic and robust package for arrangements of curves that is part of the CGAL library.Application - Polygons Boolean Operations


An intersection of polygons created with the covering_DFS function on the arrangement, and a union of circles created with the same function (the generating programs can be found in software distribution in Iddo Hanniel's site.
Links
- Ron Wein,
Efi Fogel,
Baruch Zukerman, and
Dan Halperin
Advanced programming techniques applied to Cgal's arrangement package
Computational Geometry: Theory and Applications, 38(1-2): 37-63, 2007 [link] [bibtex] - Efi Fogel,
Ron Wein,
and Dan Halperin
Code Flexibility and Program Efficiency by Genericity
In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), 3221/2004: 664-676, 2004 [link] [bibtex] - Iddo Hanniel and Dan Halperin
Two-dimensional arrangements in CGAL and adaptive point location for parametric curves
In Proceedings of the 4th International Workshop on Algorithm Engineering (WAE), 1982: 171-182, Springer, LNCS, Saarbrücken, 2000 [link] [bibTex] - Iddo Hanniel
The Design and implementation of planar arrangements of curves in CGAL
M.Sc. thesis [pdf] [bibtex] - Adaptive Point Location Project
- CGAL Class Arrangement_2 Reference Manual Chapter
Contact
Iddo Hanniel | ![]() |
![]() |