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: 117 samples with 1 evaluation.
Range (min … max): 38.896 ms … 67.522 ms ┊ GC (min … max): 0.00% … 39.09%
Time (median): 41.415 ms ┊ GC (median): 0.00%
Time (mean ± σ): 42.890 ms ± 4.302 ms ┊ GC (mean ± σ): 3.22% ± 6.29%
▄▇█▆▃ ▄
▅██████▇██▃▅▁▆▃▁▄▄▅▅▇▅▁▃▁▃▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▃ ▃
38.9 ms Histogram: frequency by time 61.8 ms <
Memory estimate: 16.02 MiB, allocs estimate: 59857.
@benchmark triangulate($points)
BenchmarkTools.Trial: 16 samples with 1 evaluation.
Range (min … max): 318.182 ms … 333.614 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 326.932 ms ┊ GC (median): 0.00%
Time (mean ± σ): 327.078 ms ± 4.277 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
▃ █ ▃
▇▁▁▁▁▁▁▁▇▁▁▁▁▁▁▁▁▁▁▇▇▁▁▁▁▁▁▁▁▁▁█▁▁█▁▇▁▁▁▁▁▁▁▁▁▁█▇▁▇▁▁▁▁▁▇▁▁▁▇ ▁
318 ms Histogram: frequency by time 334 ms <
Memory estimate: 16.91 MiB, allocs estimate: 44652.
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.