Convex Hulls

In this tutorial, we show how we can compute convex hulls. The main method for this is to compute them directly from the triangulation, noting that for an unconstrained triangulation the boundary is the convex hull. We also provide a method for computing the convex hull from the point set directly, using the monotone chain algorithm.

Let us first demonstrate how we compute convex hulls from a triangulation. This is only possible from triangulations without a constrained boundary

using DelaunayTriangulation
using CairoMakie
using StableRNGs

We construct a triangulation of a point set.

rng = StableRNG(123)
points = randn(rng, 2, 250)
tri = triangulate(points; rng)

Delaunay Triangulation.
   Number of vertices: 250
   Number of triangles: 489
   Number of edges: 738
   Has boundary nodes: false
   Has ghost triangles: true
   Curve-bounded: false
   Weighted: false
   Constrained: false

To get the convex hull, just use get_convex_hull:

get_convex_hull(tri)

Convex hull.
   Vertices:
10-element Vector{Int64}:
 151
  96
  43
 159
  25
 147
  65
 206
 199
 151

You can also obtain the vertices directly from get_convex_hull_vertices:

get_convex_hull_vertices(tri)

10-element Vector{Int64}:
 151
  96
  43
 159
  25
 147
  65
 206
 199
 151

The vertices refer to indices of points in points, and they are given in counter-clockwise order. To obtain the convex hull directly from the points without constructing the triangulation, use convex_hull:

ch = convex_hull(points)
ch_points = [get_point(tri, i) for i in DelaunayTriangulation.get_vertices(ch)]
fig, ax, sc = lines(ch_points, color = :red, linewidth = 4)
scatter!(ax, points)
fig

Just the code

An uncommented version of this example is given below. You can view the source code for this file here.

using DelaunayTriangulation
using CairoMakie
using StableRNGs

rng = StableRNG(123)
points = randn(rng, 2, 250)
tri = triangulate(points; rng)

get_convex_hull(tri)

get_convex_hull_vertices(tri)

ch = convex_hull(points)
ch_points = [get_point(tri, i) for i in DelaunayTriangulation.get_vertices(ch)]
fig, ax, sc = lines(ch_points, color = :red, linewidth = 4)
scatter!(ax, points)
fig

This page was generated using Literate.jl.