I participated in 2019 Google Summer of Code (GSoC) by creating the Shape regularization package for the Computational Geometry Algorithms Library (CGAL) project by implementing the Generalized Global Regularization algorithm from the article “KIPPI: Kinetic Polygonal Partitioning of Images” written by Jean-Philippe Bauchet and Florent Lafarge at Inria. Development for the package for CGAL was carried out under the supervision of Dr. Dmitry Anisimov. The package comes with classes that work on a given set of 2D segments.
Google Summer of Code 2019 was a 12 week, full time, remote, paid internship with regular evaluation of the participant’s work every 4 weeks. I designed, implemented, tested and documented the package under the direction of my mentor Dr. Dmitry Anisimov.
The algorithm works as follows:
- Computes neighbors of each item in the data set;
- Computes objective function values among these neighbors;
- Solves the quadratic programming problem utilizing the Operator Splitting Quadratic Program (OSQP) solver;
- Sorts items into groups based on the regularized objective function values;
- Updates items within each regularized group.
If the item type is a 2D segment, the package provides a few classes to reorient and realign them:
- Delaunay Neighbor Query – finds the neighbors of each segment by constructing a Delaunay triangulation using the CGAL::Delaunay_triangulation_2 class
- Angle Regularization – re-orients segments to preserve parallelism and orthogonality.
- Ordinate regularization – re-aligns segments to preserve collinearity.