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: 1278 samples with 1 evaluation.
Range (min … max): 3.658 ms … 19.505 ms ┊ GC (min … max): 0.00% … 75.48%
Time (median): 3.777 ms ┊ GC (median): 0.00%
Time (mean ± σ): 3.908 ms ± 878.399 μs ┊ GC (mean ± σ): 2.05% ± 6.44%
█
██▆▄▄▃▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▁▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▁▂▂▁▁▂ ▂
3.66 ms Histogram: frequency by time 8.58 ms <
Memory estimate: 1.15 MiB, allocs estimate: 2627.
@benchmark triangulate_rectangle($a, $b, $c, $d, $nx, $ny)
BenchmarkTools.Trial: 8584 samples with 1 evaluation.
Range (min … max): 414.826 μs … 24.705 ms ┊ GC (min … max): 0.00% … 94.81%
Time (median): 475.594 μs ┊ GC (median): 0.00%
Time (mean ± σ): 579.225 μs ± 722.202 μs ┊ GC (mean ± σ): 13.83% ± 11.37%
█
██▃▃▂▂▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▁▁▁▂▁▁▁▁▂▂▂▁▂▂▂▂▂▂▂▂▂▂ ▂
415 μs Histogram: frequency by time 4.7 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.