Triangulating Convex Polygons

In this tutorial, we show how we can triangulate convex polygons. The function triangulate_convex is used for this. Let us start with a simple example.

using DelaunayTriangulation
using CairoMakie

points = [
    (10.0, 12.0), (7.0, 11.0), (8.0, 6.0),
    (10.0, 3.0), (14.0, 5.0), (15.0, 10.0),
    (13.0, 12.0),
]
S = 1:7
tri = triangulate_convex(points, 1:7)

Delaunay Triangulation.
   Number of vertices: 7
   Number of triangles: 5
   Number of edges: 11
   Has boundary nodes: false
   Has ghost triangles: true
   Curve-bounded: false
   Weighted: false
   Constrained: false

fig, ax, sc = triplot(tri)
fig

This tri is our triangulation of the convex polygon. The first input is the set of points, and S defines the vertices to take from these points and their order, which must be provided in a counter-clockwise order. Note that points does not have to contain only the points of the polygon, since S will be used to define the points needed.

Let us give a larger example. For simplicity, we triangulate a a discretised circle.

θ = LinRange(0, 2π, 5000) |> collect
pop!(θ)
x = cos.(θ)
y = sin.(θ)
points = tuple.(x, y)
S = 1:4999 # can also be [1:4999; 1], if you want the array to be circular
tri = triangulate_convex(points, S)

Delaunay Triangulation.
   Number of vertices: 4999
   Number of triangles: 4997
   Number of edges: 9995
   Has boundary nodes: false
   Has ghost triangles: true
   Curve-bounded: false
   Weighted: false
   Constrained: false

fig, ax, sc = triplot(tri)
fig

Here is a comparison of the time it takes to triangulate this using triangulate_convex or triangulate.

using BenchmarkTools
@benchmark triangulate_convex($points, $S)

BenchmarkTools.Trial: 106 samples with 1 evaluation.
 Range (min … max):  40.044 ms … 443.072 ms  ┊ GC (min … max): 0.00% … 89.81%
 Time  (median):     42.879 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   47.537 ms ±  38.960 ms  ┊ GC (mean ± σ):  9.23% ±  9.94%

     ▄▆▆▆█ ▃                                                    
  ▇▃▅█████▇█▅▇█▃▄▅▃▃▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▃ ▃
  40 ms           Histogram: frequency by time         64.1 ms <

 Memory estimate: 17.25 MiB, allocs estimate: 59818.

@benchmark triangulate($points)

BenchmarkTools.Trial: 16 samples with 1 evaluation.
 Range (min … max):  323.144 ms … 348.266 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     329.239 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   331.701 ms ±   7.300 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▁    ▁ ▁ ▁█ ▁ ▁█ ▁     ▁         ▁       ▁            ▁     ▁  
  █▁▁▁▁█▁█▁██▁█▁██▁█▁▁▁▁▁█▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁█ ▁
  323 ms           Histogram: frequency by time          348 ms <

 Memory estimate: 17.88 MiB, allocs estimate: 44688.

For the smaller example that we started with above, triangulate_convex is also faster, although not by much (≈15.10 μs versus ≈10.7 μs).

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

points = [
    (10.0, 12.0), (7.0, 11.0), (8.0, 6.0),
    (10.0, 3.0), (14.0, 5.0), (15.0, 10.0),
    (13.0, 12.0),
]
S = 1:7
tri = triangulate_convex(points, 1:7)

fig, ax, sc = triplot(tri)
fig

θ = LinRange(0, 2π, 5000) |> collect
pop!(θ)
x = cos.(θ)
y = sin.(θ)
points = tuple.(x, y)
S = 1:4999 # can also be [1:4999; 1], if you want the array to be circular
tri = triangulate_convex(points, S)

fig, ax, sc = triplot(tri)
fig

using BenchmarkTools
@benchmark triangulate_convex($points, $S)

@benchmark triangulate($points)

This page was generated using Literate.jl.