Arrangements

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