Convex Hull Computation with delaunayTriangulation

Compute the convex hull of a set of points in 2-D by using the convexHull method of the delaunayTriangulation class.

Create a Delaunay triangulation of a set of points in 2-D.

X = [-1.5 3.2;1.8 3.3;-3.7 1.5;-1.5 1.3;0.8 1.2; ...
      3.3 1.5;-4.0 -1.0;-2.3 -0.7;0 -0.5;2.0 -1.5; ...
      3.7 -0.8;-3.5 -2.9;-0.9 -3.9;2.0 -3.5;3.5 -2.25];

dt = delaunayTriangulation(X);

Plot the triangulation. Highlight the edges shared only by a single triangle to reveal the convex hull.

triplot(dt)

fe = freeBoundary(dt)';
hold on
plot(X(fe,1),X(fe,2),"-r",LineWidth=2)
hold off

In 3-D, the facets of the triangulation that are shared only by one tetrahedron represent the boundary of the convex hull.

The dedicated convhull function is generally more efficient than a computation based on the convexHull method. However, the triangulation based approach is appropriate if:

• You already have a delaunayTriangulation of the point set and the convex hull is also required.

• You need to add or remove points from the set incrementally and need to recompute the convex hull frequently after you have edited the points.