Abstracts of the 23rd European Workshop on Computational Geometry, pp. 219–222
Research account
Exact and efficient computations on circles in CGAL
CGAL (Computational Geometry Algorithms Library) is a large collection of geometric objects, data structures and algorithms. At the time of this work, CGAL mainly offered functionalities for linear objects (points, segments, lines, triangles…). The first version of a kernel for circles and circular arcs in 2D had been released in CGAL 3.2. We show in this paper a variety of techniques that we tested to improve the efficiency of the 2D circular kernel. These improvements are motivated by applications to VLSI design, and real VLSI industrial data are used to measure the impact of the techniques used to enhance this kernel. The paper reports the improvements prepared for CGAL 3.3.
This work has been implemented in CGAL, you can find the user manual here, and the reference manual here . The paper has been presented at EWCG’07, and published in Abstracts of the 23rd European Workshop on Computational Geometry, pages 219-222, 2007.