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: 121 samples with 1 evaluation.
Range (min … max): 37.473 ms … 67.007 ms ┊ GC (min … max): 0.00% … 38.13%
Time (median): 39.971 ms ┊ GC (median): 0.00%
Time (mean ± σ): 41.374 ms ± 4.326 ms ┊ GC (mean ± σ): 3.40% ± 6.34%
▂▃██▄▃▁▄
▅████████▃█▄▁▁▃▅▄▆▁▁▁▆▅▃▃▃▃▅▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▃ ▃
37.5 ms Histogram: frequency by time 60.6 ms <
Memory estimate: 16.01 MiB, allocs estimate: 59763.
@benchmark triangulate($points)
BenchmarkTools.Trial: 17 samples with 1 evaluation.
Range (min … max): 292.576 ms … 311.280 ms ┊ GC (min … max): 0.00% … 0.00%
Time (median): 297.242 ms ┊ GC (median): 0.00%
Time (mean ± σ): 297.427 ms ± 4.203 ms ┊ GC (mean ± σ): 0.00% ± 0.00%
▁ █ ▁ ▁▁▁ ▁█▁█▁ ▁ ▁ ▁
█▁█▁█▁▁▁▁▁███▁█████▁▁█▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
293 ms Histogram: frequency by time 311 ms <
Memory estimate: 16.90 MiB, allocs estimate: 44565.
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.