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: 120 samples with 1 evaluation.
Range (min … max): 37.916 ms … 66.509 ms ┊ GC (min … max): 0.00% … 35.06%
Time (median): 40.590 ms ┊ GC (median): 0.00%
Time (mean ± σ): 41.852 ms ± 4.134 ms ┊ GC (mean ± σ): 3.51% ± 6.45%
▃ █▆ ▂▁
▃████▅███▄▅▄▃▄▅▁▄▅▄▅▁▁▃▄▃▄▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃ ▃
37.9 ms Histogram: frequency by time 63.6 ms <
Memory estimate: 16.03 MiB, allocs estimate: 59930.
@benchmark triangulate($points)
BenchmarkTools.Trial: 17 samples with 1 evaluation.
Range (min … max): 293.368 ms … 301.396 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 297.683 ms ┊ GC (median): 0.00%
Time (mean ± σ): 297.725 ms ± 2.586 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
█ █ █ █ █ ██ █ █ █ █ █ ██ █ ██
█▁█▁▁▁▁▁▁▁█▁█▁▁▁▁▁▁▁▁▁▁█▁██▁▁█▁▁█▁▁█▁▁█▁█▁▁▁▁▁▁▁▁▁▁▁██▁▁▁█▁██ ▁
293 ms Histogram: frequency by time 301 ms <
Memory estimate: 16.91 MiB, allocs estimate: 44604.
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.