Update Dec 2014

  • Improved handling of "degenerate" data (regular grids, etc.). See examples 4DelaunayAndVoronoiWPF and 7DelaunayWPF for basic usage of the new features. It is still not perfect but seems to be a step forward.
  • Performance is improved by up to ~40% mostly due to changing internal representation of data (for example Delaunay tri. of 50k random 3D points down from ~3.2s to ~1.9s on my machine).

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 code is written in C# and provides a template based API that allows extensive customization of the underlying types that represent 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 by the MIConvexHull algorithm.


The timings are illustrative and were obtained on Core i7-5930 using the version from Dec 20 2014 and the Helix Studio example.

26328 vertices: Convex hull in 0.009s. Triangulation in 0.743s. 34835 vertices: Convex hull in 0.018s. Triangulation in 1.225s.
ferrari_thumb.png ferrariwrap_thumb.png bunny_thumb.png bunnywarp_thumb.png
26332 vertices: Convex hull in 0.003s. Triangulation in 0.761s. 500 2D vertices - Delaunay Triangulation and Voronoi Mesh.
eiffel_thumb.png eiffel-wrap_thumb.png 2dDelau.png 2dVoronoi.png
Voronoi mesh of regular grid with an ellipse inside. Delaunay triangulation of regular grid
miregularvoronoi.png miregulartri.jpg

Last edited Dec 20, 2014 at 4:20 AM by davecz, version 62