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: 122 samples with 1 evaluation.
Range (min … max): 37.008 ms … 70.113 ms ┊ GC (min … max): 0.00% … 43.58%
Time (median): 39.321 ms ┊ GC (median): 0.00%
Time (mean ± σ): 41.149 ms ± 4.561 ms ┊ GC (mean ± σ): 3.84% ± 7.23%
▁█▄▄▁ ▁
▃▆█████▄█▆▃▄▃▁▁▁▁▃▃▁▄▅▅▅▄▁▃▁▁▁▁▁▁▃▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃ ▃
37 ms Histogram: frequency by time 61.2 ms <
Memory estimate: 16.04 MiB, allocs estimate: 59983.
@benchmark triangulate($points)
BenchmarkTools.Trial: 17 samples with 1 evaluation.
Range (min … max): 296.445 ms … 322.178 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 308.834 ms ┊ GC (median): 0.00%
Time (mean ± σ): 309.062 ms ± 4.910 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
█ ▃█ ▃
▇▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▇▁▇▁█▁██▇▁▁▇▁█▁▁▁▁▇▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▇ ▁
296 ms Histogram: frequency by time 322 ms <
Memory estimate: 16.92 MiB, allocs estimate: 44646.
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.