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: 1184 samples with 1 evaluation.
 Range (min … max):  3.417 ms … 414.093 ms  ┊ GC (min … max): 0.00% … 98.92%
 Time  (median):     3.769 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.218 ms ±  11.942 ms  ┊ GC (mean ± σ):  8.80% ±  4.42%

         ▁▇█▆▄▂ ▁▄▆▃                                           
  ▆▇▄▅▆▅▆████████████▄▅▄▁▄▁▁▁▅▁▄▄▁▁▁▁▁▁▁▁▄▁▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▄ █
  3.42 ms      Histogram: log(frequency) by time      5.51 ms <

 Memory estimate: 1.22 MiB, allocs estimate: 2691.

@benchmark triangulate_rectangle($a, $b, $c, $d, $nx, $ny)

BenchmarkTools.Trial: 8406 samples with 1 evaluation.
 Range (min … max):  446.577 μs … 389.825 ms  ┊ GC (min … max):  0.00% … 99.72%
 Time  (median):     502.466 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   591.723 μs ±   4.274 ms  ┊ GC (mean ± σ):  12.16% ±  5.64%

     ▁▁▂▄▆███▇▇▇▆▅▅▄▄▄▃▃▂▂▁▁                         ▁ ▁▂▁▁     ▃
  ▅▆███████████████████████████▇▇▆▅▄▆▄▃▄▅▃▁▃▁▃▄▆█▇▆████████▇██▆ █
  447 μs        Histogram: log(frequency) by time        751 μs <

 Memory estimate: 1.16 MiB, allocs estimate: 2425.

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.