What algorithm does the convhull() function in Matlab use?

Question

What algorithms do the convhull and convhulln functions in MATLAB implement to compute the convex hull?

I cannot find any references..

Answer 1

In the past, both convhull and convhulln used the Qhull library internally.

Then starting with R2009b, convhull switched to using the CGAL library as implementation, (but not convhulln).

---

If you go through the release notes, you can confirm these facts:

• In R2009a release notes:

Upgrade to Computational Geometry

MATLAB includes a new object-oriented suite of computational geometry tools, together with a new underlying library called CGAL. The new library provides improved robustness, performance, and memory efficiency. The new tools are presented in three classes:

• New class TriRep provides topological and geometric queries for triangulations in 2-D and 3-D space.
• New class DelaunayTri provides increased functionality for Delaunay triangulation including topological and geometric queries, incremental modification, and edge constraints.
• New class TriScatteredInterp provides fast robust scattered data interpolation and a new natural-neighbor interpolation technique.

• Then in the R2009b release notes:

Computational Geometry Functions Being Changed

2- and 3-D computational geometry functions (delaunay, convhull, griddata, voronoi, delaunay3, griddata3) no longer use QHULL or the QHULL options arguments. The N-D functions gridatan, delaunayn, convhulln, and voronoin still use QHULL.

...

• Finally in R2013a release notes, those classes were deprecated in favor of the currently preferred methods:

scatteredInterpolant class that replaces TriScatteredInterp

TriScatteredInterp will be removed in a future release. Use the new scatteredInterpolant class instead. The scatteredInterpolant class performs interpolation on 2-D and 3-D scattered data with support for extrapolation outside the convex hull of the sample points. scatteredInterpolant also supports queries in grid vector format to conserve memory.

...

triangulation class to replace TriRep

TriRep will be removed in a future release. Use the new triangulation class instead. The triangulation class represents 2-D and 3-D triangulations using a similar form and syntax as TriRep.

...

delaunayTriangulation class to replace DelaunayTri

DelaunayTri will be removed in a future release. Use the new delaunayTriangulation class instead. delaunayTriangulation represents 2-D and 3-D Delaunay triangulations using a similar form and syntax as DelaunayTri.

...

---

TL;DR:

• convhull is based on CGAL.
• convhulln is based on Qhull.

Answer 2

(making my comment an answer)

According to MathWorks convhulln documentation

"convhulln is based on Qhull. For information about Qhull, see http://www.qhull.org/"

See also qhull.m for more info.

Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Trans. on Mathematical Software, 22(4), 1996.