Triangulating Rectangular Regions
In this tutorial, we show how you can easily triangulate rectangular regions of the form $[a, b] \times [c, d]$. Rather than using triangulate
, you can use triangulate_rectangle
for this purpose. To start, we give a simple example
using DelaunayTriangulation
using CairoMakie
a, b, c, d = 0.0, 2.0, 0.0, 10.0
nx, ny = 10, 25
tri = triangulate_rectangle(a, b, c, d, nx, ny)
fig, ax, sc = triplot(tri)
fig
This can be much faster than if we just construct the points in the lattice manually and triangulate
those. Here's a comparison of the times.
using BenchmarkTools
points = get_points(tri)
@benchmark triangulate($points; randomise = $false) # randomise=false because points are already in lattice order, i.e. spatially sorted
BenchmarkTools.Trial: 1291 samples with 1 evaluation.
Range (min … max): 3.653 ms … 20.331 ms ┊ GC (min … max): 0.00% … 77.92%
Time (median): 3.736 ms ┊ GC (median): 0.00%
Time (mean ± σ): 3.871 ms ± 937.984 μs ┊ GC (mean ± σ): 2.21% ± 6.80%
█
██▅▄▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂▂▂ ▂
3.65 ms Histogram: frequency by time 8.95 ms <
Memory estimate: 1.15 MiB, allocs estimate: 2627.
@benchmark triangulate_rectangle($a, $b, $c, $d, $nx, $ny)
BenchmarkTools.Trial: 8955 samples with 1 evaluation.
Range (min … max): 405.953 μs … 33.129 ms ┊ GC (min … max): 0.00% … 96.21%
Time (median): 449.749 μs ┊ GC (median): 0.00%
Time (mean ± σ): 555.552 μs ± 800.635 μs ┊ GC (mean ± σ): 14.05% ± 11.13%
█▅▃▄▂ ▁
█████▅▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▆▇▆▆▆ █
406 μs Histogram: log(frequency) by time 4.65 ms <
Memory estimate: 1.09 MiB, allocs estimate: 2371.
This difference would be more pronounced for larger nx, ny
.
Note that the output of triangulate_rectangle
treats the boundary as a constrained boundary:
get_boundary_nodes(tri)
4-element Vector{Vector{Int64}}:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100 … 160, 170, 180, 190, 200, 210, 220, 230, 240, 250]
[250, 249, 248, 247, 246, 245, 244, 243, 242, 241]
[241, 231, 221, 211, 201, 191, 181, 171, 161, 151 … 91, 81, 71, 61, 51, 41, 31, 21, 11, 1]
This boundary is split into four separate sections, one for each side of the rectangle. If you would prefer to keep the boundary as one contiguous section, use single_boundary=true
. Moreover, note that this tri
has ghost triangles:
tri
Delaunay Triangulation.
Number of vertices: 250
Number of triangles: 432
Number of edges: 681
Has boundary nodes: true
Has ghost triangles: true
Curve-bounded: false
Weighted: false
Constrained: true
You can opt into not having these by using delete_ghosts=true
:
tri = triangulate_rectangle(a, b, c, d, nx, ny; single_boundary = true, delete_ghosts = true)
tri
Delaunay Triangulation.
Number of vertices: 250
Number of triangles: 432
Number of edges: 681
Has boundary nodes: true
Has ghost triangles: false
Curve-bounded: false
Weighted: false
Constrained: true
get_boundary_nodes(tri)
67-element Vector{Int64}:
1
2
3
4
5
6
7
8
9
10
⋮
81
71
61
51
41
31
21
11
1
DelaunayTriangulation.has_ghost_triangles(tri)
false
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
a, b, c, d = 0.0, 2.0, 0.0, 10.0
nx, ny = 10, 25
tri = triangulate_rectangle(a, b, c, d, nx, ny)
fig, ax, sc = triplot(tri)
fig
using BenchmarkTools
points = get_points(tri)
@benchmark triangulate($points; randomise = $false) # randomise=false because points are already in lattice order, i.e. spatially sorted
@benchmark triangulate_rectangle($a, $b, $c, $d, $nx, $ny)
get_boundary_nodes(tri)
tri
tri = triangulate_rectangle(a, b, c, d, nx, ny; single_boundary = true, delete_ghosts = true)
tri
get_boundary_nodes(tri)
DelaunayTriangulation.has_ghost_triangles(tri)
This page was generated using Literate.jl.