Computational geometry · Open-source software

Software in CGAL

Algorithms for curved geometry, changing triangulations and geometric sampling, developed with collaborators and distributed in the Computational Geometry Algorithms Library.

2D Circular Geometry Kernel

Computing with circles and arcs

A circular arc can meet a line or another arc at points that ordinary rational coordinates cannot represent exactly. The circular kernel provides predicates and constructions for working with this geometry.

My contribution

I improved the efficiency of the kernel in 2006 and added functionality in 2008, building on the original implementation by Sylvain Pion and Monique Teillaud.

Contributions in 2006 and 2008

Documentation Code example Source code Contribution credits

Two circles centered at C₁ and C₂ intersect at P₊ and P₋, with exact coordinates (2, ±√21). — Two circles of radius 5, centered at (0, 0) and (4, 0), meet at (2, ±√21). Exact constructions retain these algebraic coordinates without rounding them to floating-point values.

3D Spherical Geometry Kernel

Exact intersections in three dimensions

Intersecting spheres, circles and planes requires both combinatorial decisions and exact coordinates. The spherical kernel supplies these operations for curved geometry in three dimensions.

My contribution

Monique Teillaud and I coauthored the first version, integrated into CGAL 3.4. Frédéric Cazals and Sébastien Loriot subsequently added operations relative to a common reference sphere.

First version in CGAL 3.4

Documentation Code example Source code Contribution credits

Two spheres meet along the green circle; the third meets that circle at the two red points. For the unit spheres illustrated here, the common points are (0, 0, ±4/5).

View full size

3D Triangulations

Moving and locating points in a triangulation

When a point moves, a Delaunay triangulation must remain valid. Finding the cell containing a query point is another recurring task in geometric algorithms.

My contribution

With Olivier Devillers, I added point displacement in 2010 (CGAL 3.7) and implemented structural filtering for efficient point location in 2011 (CGAL 3.8).

CGAL 3.7 · 2010 / CGAL 3.8 · 2011

Documentation Displacement API Source code Contribution credits Research account

Perspective views show a red interior vertex moving from P to Q inside the same tetrahedron. Boundary vertices A, B, C and D remain fixed; one incident cell is shaded teal. — The red vertex moves from P to Q while A, B, C and D stay fixed. One of its four incident tetrahedral cells is shaded. Both states are valid Delaunay triangulations with the same connectivity; dashed lines show hidden boundary edges.

Geometric Object Generators

Sampling points inside triangles and tetrahedra

Geometric experiments often need points distributed uniformly inside a shape. Barycentric coordinates provide a way to generate points throughout a triangle or tetrahedron.

My contribution

Alexandru Tifrea and I implemented generators for points in 2D and 3D triangles and in 3D tetrahedra during Google Summer of Code 2013.

Google Summer of Code · 2013

Documentation Generator reference Source code Contribution credits

An equilateral triangle contains 200 blue points; an upright regular tetrahedron contains 260 shaded teal points. Perspective and hidden edges reveal the three-dimensional volume. — Uniform samples across a triangle’s area (200 points) and throughout a tetrahedron’s volume (260 points). The 3D view uses perspective and depth shading, so apparent density on the screen need not be uniform.

Spatial Sorting

Ordering points on a sphere

Processing nearby points together can make geometric insertion more efficient. Hilbert sorting gives points on a sphere a spatially coherent order.

My contribution

Olivier Devillers and I added Hilbert sorting on the sphere. This extends a package whose original 2D and 3D sorting implementation was developed by Christophe Delage.

Hilbert sorting on the sphere

Documentation Code example Source code Contribution credits

Official CGAL illustration: green points on a shaded sphere are joined in order by a red path that groups nearby points. — Hilbert sort on the sphere: green points are connected by the red path in their sorted order. The path follows nearby regions across the surface.© The CGAL Project · Spatial Sorting · CC BY-NC-ND 2.0 · Full credit

Software in CGAL

Computing with circles and arcs

My contribution

Exact intersections in three dimensions

My contribution

Moving and locating points in a triangulation

My contribution

Sampling points inside triangles and tetrahedra

My contribution

Ordering points on a sphere

My contribution

Search this site

Research figure