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: 125 samples with 1 evaluation.
Range (min … max): 36.537 ms … 69.208 ms ┊ GC (min … max): 0.00% … 38.97%
Time (median): 38.947 ms ┊ GC (median): 0.00%
Time (mean ± σ): 40.114 ms ± 4.119 ms ┊ GC (mean ± σ): 3.18% ± 6.32%
▂▂█▃▁▃▁
▆▆███████▇▇▄▄▃▁▁▃▁▄▄▄▄▆▄▄▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▁▁▃ ▃
36.5 ms Histogram: frequency by time 58 ms <
Memory estimate: 16.02 MiB, allocs estimate: 59765.
@benchmark triangulate($points)
BenchmarkTools.Trial: 17 samples with 1 evaluation.
Range (min … max): 295.111 ms … 309.823 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 298.710 ms ┊ GC (median): 0.00%
Time (mean ± σ): 299.343 ms ± 3.883 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
▁▁█ █ ▁▁ ▁▁ ▁▁ ▁ ▁ ▁ ▁ ▁
███▁▁▁▁█▁▁▁██▁██▁▁██▁█▁▁█▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
295 ms Histogram: frequency by time 310 ms <
Memory estimate: 16.91 MiB, allocs estimate: 44558.
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.