Personal tools
You are here: Home Projects Internal Projects Arrangements
« March 2017 »
Log in

Forgot your password?


[Circle Arrangement]


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.


  • 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


Iddo Hanniel
Document Actions