Thursday, April 2, 2009

CGAL : Computational Geometry Algorithms Library in C++

I was looking for a library implementing Range Trees and Interval Trees, two less known but very useful data structures for retrieving overlapping segments and points. Those data structures are used in databases and in many other contexts.

Well, what I found is a larger golden mine. The Computational Geometry Algorithms Library (CGAL) is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python bindings are also available.

The table of content shows an impressive amount of already cooked algorithms and data structures, ranging from basic 2D and 3D Geometry Kernel, to Convex Hulls and Delaunay Triangulations, to Voronoi Diagrams.

I found the Search Structures part quite interesting with implementations of 2D Range and Neighbor Search , Interval Skip List, Spatial Searching ( Neighbor Searching , Range Searching , k-d tree ), Range and Segment Trees, Intersecting Sequences of dD Boxes.

The library has additional tools for Linear and Quadratic Programming Solver and Spatial Sorting and support for third party software such as the GUI libraries Qt, Geomview, and the Boost Graph Library. (Gosh all these are together?)

A huge amount of software all using Template C++ with an approach similar to Boost.

I take what I need for my coding task, but this is bookmarked and I will discuss about it more intensively in the future.

No comments:

Post a Comment