Triangulation Operations

Edge Flipping

This tutorial shows we can flip edges in a triangulation. Edge flipping is the flipping of some edge (i, j) to the edge (k, ℓ), where (i, j) and (k, ℓ) are diagonals of the quadrilateral formed by $p_ip_jp_kp_l$. The edge flip is illustrated below.

Note that this edge flip only makes sense if the quadrilateral is convex. If the quadrilateral is not convex, then the edge flip will not be valid; no checks are made for whether the quadrilateral is convex inside the flip_edge! function.

Let us now showcase how we can flip edges. First, we load in the packages we need.

using DelaunayTriangulation
using CairoMakie

Let us now define our initial triangulation.

points = [(0.0, 0.0), (0.8, 0.0), (1.3, 1.0), (0.0, 1.0)]
tri = triangulate(points);

Now, flipping the edge is simple. We simply provide the indices i and j for the edge we want to flip. Let us flip the edge (2, 4).

fig, ax, sc = triplot(tri, axis = (title = "Before flipping",))
ax2 = Axis(fig[1, 2], title = "After flipping")
flip_edge!(tri, 2, 4)
triplot!(ax2, tri)
fig

As simple as that. Note that no checks are made for whether the edge is actually in the triangulation, on the boundary, or if the associated quadrilateral is convex. It is up to you to check this if needed; one way to check would be to use DelaunayTriangulation.is_legal, as is done inside legalise_edge! – see the next tutorial.

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.8, 0.0), (1.3, 1.0), (0.0, 1.0)]
tri = triangulate(points);

fig, ax, sc = triplot(tri, axis = (title = "Before flipping",))
ax2 = Axis(fig[1, 2], title = "After flipping")
flip_edge!(tri, 2, 4)
triplot!(ax2, tri)
fig

This page was generated using Literate.jl.