Update Nov 21 2012

The code for the higher dimensional convex hulls has been greatly improved. For example when computing the convex hull of 500 random 8D points, the new version runs ~9s versus ~212s when using the old one.

Update Oct 22 2011

There is a newer version available (in the Source Code section) that is a complete rewrite of the code. It contains new API, a very significant performance increase (25k points triangulated in 1.5s) and is much more efficient in memory usage. I think we are getting close to "official 2.0" version. The timings on this page are for the latest push (on i7 860).

Current performance tests can be seen in PerformanceTests.pdf (includes a comparison with the CGAL library).

Project Description

This project is a convex hull algorithm and library for 2D, 3D, and higher dimensions. The code can also be used to compute Delaunay triangulations and Voronoi meshes of the input data. The benchmarks indicate that the convex hull code and 4 and higher dimensional triangulation code is on par or better than the solution provided by the C++ library CGAL.

The code is written in C# 4.0 and provides a template based API that allows extensive customization of the underlying types that represents vertices and faces of the convex hull. The algorithm itself is technically an implementation of the QuickHull algorithm. Nevertheless, it's not just a simple port of QHull as a different approach and data structures are used in the MIConvexHull algorithm.

Currently, one drawback of the algorithm is that it cannot handle degenerate data and noise has to be manually introduced to achieve some results. However, in many practical applications, the degeneracy is not an issue. The problem occurs for example when the algorithm tries to triangulate 4 3D points that all lie in a plane (this happens when triangulating the Eiffel Tower model).

Examples

26328 vertices: convex hull in 0.023sec. 34835 vertices: convex hull in 0.04 sec.
ferrari_thumb.png ferrariwrap_thumb.png bunny_thumb.png bunnywarp_thumb.png
26332 vertices: convex hull in 0.005 sec. 500 2D vertices - Delaunay Triangulation and Voronoi Mesh.
eiffel_thumb.png eiffel-wrap_thumb.png 2dDelau.png 2dVoronoi.png

Last edited Nov 22, 2012 at 11:10 PM by davecz, version 60