Triangulation Operations

Edge Splitting

Sometimes you have a point r that you know is on, or is very close to being on, an edge (i, j). In this tutorial, we show how the split_edge! function can be used for putting a point on this edge. First, let us consider the following triangulation.

using DelaunayTriangulation
using CairoMakie

points = [(0.0, 0.0), (0.0, 4.0), (2.0, 3.0), (-2.0, 3.0),
    (-2.0, 7.0), (3.0, 6.0), (2.0, -2.0), (-4.0, 1.0),
    (1.0, 5.0)]
p = (0.0, 3.0)
tri = triangulate(points)
fig, ax, sc = triplot(tri)
scatter!(ax, [p], markersize=14)
fig

We want to add the blue point onto the edge shown, which is (1, 2). To do this, we can use the function split_edge!.

push!(points, p)
r = length(points)
i, j = 1, 2
split_edge!(tri, i, j, r)
fig, ax, sc = triplot(tri)
fig

Notice that this has only split the edge in one direction. This is because the edges in this case are treated as being oriented. To split the edge in the other direction, we simply swap the indices.

split_edge!(tri, j, i, r)
fig, ax, sc = triplot(tri)
fig

If you also want to restore the Delaunay property of the triangulation following this splitting, you need to use legalise_edge!. In this example, though, there are no illegal edges. If there were, we would use

k = get_adjacent(tri, i, r) # get_adjacent(tri, i, j) before split_edge!(tri, i, j)
legalise_edge!(tri, j, k, r)
legalise_edge!(tri, k, i, r)
k = get_adjacent(tri, j, r) # get_adjacent(tri, j, i) before split_edge!(tri, j, i)
legalise_edge!(tri, i, k, r)
legalise_edge!(tri, k, j, r)

Delaunay Triangulation.
   Number of vertices: 10
   Number of triangles: 14
   Number of edges: 23
   Has boundary nodes: false
   Has ghost triangles: true
   Curve-bounded: false
   Weighted: false
   Constrained: false

These steps, in particular the steps of splitting both sides of the edge and then legalising, are also implemented in DelaunayTriangulation.complete_split_edge_and_legalise!.

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 = [(0.0, 0.0), (0.0, 4.0), (2.0, 3.0), (-2.0, 3.0),
    (-2.0, 7.0), (3.0, 6.0), (2.0, -2.0), (-4.0, 1.0),
    (1.0, 5.0)]
p = (0.0, 3.0)
tri = triangulate(points)
fig, ax, sc = triplot(tri)
scatter!(ax, [p], markersize=14)
fig

push!(points, p)
r = length(points)
i, j = 1, 2
split_edge!(tri, i, j, r)
fig, ax, sc = triplot(tri)
fig

split_edge!(tri, j, i, r)
fig, ax, sc = triplot(tri)
fig

k = get_adjacent(tri, i, r) # get_adjacent(tri, i, j) before split_edge!(tri, i, j)
legalise_edge!(tri, j, k, r)
legalise_edge!(tri, k, i, r)
k = get_adjacent(tri, j, r) # get_adjacent(tri, j, i) before split_edge!(tri, j, i)
legalise_edge!(tri, i, k, r)
legalise_edge!(tri, k, j, r)

This page was generated using Literate.jl.