Constrained Triangulations

Domain with Interior Holes within Interior Holes

Now we consider triangulating a domain which has not only an interior boundary, but also an interior boundary inside that interior boundary. To start, let us load the packages.

using DelaunayTriangulation
using CairoMakie
using StableRNGs

To represent curves inside of curves, note that we have already had to do this for the outer boundary, where interior curves are clockwise - the opposite orientation of the outer boundary. So, similarly, interiors within other interior curves must be counter-clockwise. Basically, the orientation of an interior curve is the opposite orientation to the curve it's inside of. Here are the points we will be triangulating.

curve_1 = [
    [(0.0, 0.0), (5.0, 0.0), (10.0, 0.0), (15.0, 0.0), (20.0, 0.0), (25.0, 0.0)],
    [(25.0, 0.0), (25.0, 5.0), (25.0, 10.0), (25.0, 15.0), (25.0, 20.0), (25.0, 25.0)],
    [(25.0, 25.0), (20.0, 25.0), (15.0, 25.0), (10.0, 25.0), (5.0, 25.0), (0.0, 25.0)],
    [(0.0, 25.0), (0.0, 20.0), (0.0, 15.0), (0.0, 10.0), (0.0, 5.0), (0.0, 0.0)],
] # outer-most boundary: counter-clockwise
curve_2 = [
    [(4.0, 6.0), (4.0, 14.0), (4.0, 20.0), (18.0, 20.0), (20.0, 20.0)],
    [(20.0, 20.0), (20.0, 16.0), (20.0, 12.0), (20.0, 8.0), (20.0, 4.0)],
    [(20.0, 4.0), (16.0, 4.0), (12.0, 4.0), (8.0, 4.0), (4.0, 4.0), (4.0, 6.0)],
] # inner boundary: clockwise
curve_3 = [
    [
        (12.906, 10.912), (16.0, 12.0), (16.16, 14.46), (16.29, 17.06),
        (13.13, 16.86), (8.92, 16.4), (8.8, 10.9), (12.906, 10.912),
    ],
] # this is inside curve_2, so it's counter-clockwise
curves = [curve_1, curve_2, curve_3]
points = [
    (3.0, 23.0), (9.0, 24.0), (9.2, 22.0), (14.8, 22.8), (16.0, 22.0),
    (23.0, 23.0), (22.6, 19.0), (23.8, 17.8), (22.0, 14.0), (22.0, 11.0),
    (24.0, 6.0), (23.0, 2.0), (19.0, 1.0), (16.0, 3.0), (10.0, 1.0), (11.0, 3.0),
    (6.0, 2.0), (6.2, 3.0), (2.0, 3.0), (2.6, 6.2), (2.0, 8.0), (2.0, 11.0),
    (5.0, 12.0), (2.0, 17.0), (3.0, 19.0), (6.0, 18.0), (6.5, 14.5),
    (13.0, 19.0), (13.0, 12.0), (16.0, 8.0), (9.8, 8.0), (7.5, 6.0),
    (12.0, 13.0), (19.0, 15.0),
]
boundary_nodes, points = convert_boundary_points_to_indices(curves; existing_points = points)

([[[35, 36, 37, 38, 39, 40], [40, 41, 42, 43, 44, 45], [45, 46, 47, 48, 49, 50], [50, 51, 52, 53, 54, 35]], [[55, 56, 57, 58, 59], [59, 60, 61, 62, 63], [63, 64, 65, 66, 67, 55]], [[68, 69, 70, 71, 72, 73, 74, 68]]], [(3.0, 23.0), (9.0, 24.0), (9.2, 22.0), (14.8, 22.8), (16.0, 22.0), (23.0, 23.0), (22.6, 19.0), (23.8, 17.8), (22.0, 14.0), (22.0, 11.0)  …  (12.0, 4.0), (8.0, 4.0), (4.0, 4.0), (12.906, 10.912), (16.0, 12.0), (16.16, 14.46), (16.29, 17.06), (13.13, 16.86), (8.92, 16.4), (8.8, 10.9)])

To now triangulate:

rng = StableRNG(123) # triangulation is not unique when there are cocircular points
tri = triangulate(points; boundary_nodes, rng)
fig, ax, sc = triplot(tri)
fig

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
using StableRNGs

curve_1 = [
    [(0.0, 0.0), (5.0, 0.0), (10.0, 0.0), (15.0, 0.0), (20.0, 0.0), (25.0, 0.0)],
    [(25.0, 0.0), (25.0, 5.0), (25.0, 10.0), (25.0, 15.0), (25.0, 20.0), (25.0, 25.0)],
    [(25.0, 25.0), (20.0, 25.0), (15.0, 25.0), (10.0, 25.0), (5.0, 25.0), (0.0, 25.0)],
    [(0.0, 25.0), (0.0, 20.0), (0.0, 15.0), (0.0, 10.0), (0.0, 5.0), (0.0, 0.0)],
] # outer-most boundary: counter-clockwise
curve_2 = [
    [(4.0, 6.0), (4.0, 14.0), (4.0, 20.0), (18.0, 20.0), (20.0, 20.0)],
    [(20.0, 20.0), (20.0, 16.0), (20.0, 12.0), (20.0, 8.0), (20.0, 4.0)],
    [(20.0, 4.0), (16.0, 4.0), (12.0, 4.0), (8.0, 4.0), (4.0, 4.0), (4.0, 6.0)],
] # inner boundary: clockwise
curve_3 = [
    [
        (12.906, 10.912), (16.0, 12.0), (16.16, 14.46), (16.29, 17.06),
        (13.13, 16.86), (8.92, 16.4), (8.8, 10.9), (12.906, 10.912),
    ],
] # this is inside curve_2, so it's counter-clockwise
curves = [curve_1, curve_2, curve_3]
points = [
    (3.0, 23.0), (9.0, 24.0), (9.2, 22.0), (14.8, 22.8), (16.0, 22.0),
    (23.0, 23.0), (22.6, 19.0), (23.8, 17.8), (22.0, 14.0), (22.0, 11.0),
    (24.0, 6.0), (23.0, 2.0), (19.0, 1.0), (16.0, 3.0), (10.0, 1.0), (11.0, 3.0),
    (6.0, 2.0), (6.2, 3.0), (2.0, 3.0), (2.6, 6.2), (2.0, 8.0), (2.0, 11.0),
    (5.0, 12.0), (2.0, 17.0), (3.0, 19.0), (6.0, 18.0), (6.5, 14.5),
    (13.0, 19.0), (13.0, 12.0), (16.0, 8.0), (9.8, 8.0), (7.5, 6.0),
    (12.0, 13.0), (19.0, 15.0),
]
boundary_nodes, points = convert_boundary_points_to_indices(curves; existing_points = points)

rng = StableRNG(123) # triangulation is not unique when there are cocircular points
tri = triangulate(points; boundary_nodes, rng)
fig, ax, sc = triplot(tri)
fig

This page was generated using Literate.jl.