Weighted Triangulations
In this tutorial, we demonstrate how to construct a weighted Delaunay triangulation. For more information about weighted Delaunay triangulations, see the math details here. To summarise, weighted Delaunay triangulations associate with each vertex $p_i$ a scalar weight $w_i$. To pass weights into triangulate
, use the weights
keyword argument, which by default is ZeroWeight()
.
Let's first consider a simple example. We use a triangulation with random weights and compare it to the standard unweighted Delaunay triangulation.
using DelaunayTriangulation, CairoMakie
A, B, C, D, E, F, G, H,
I, J, K, L, M, N = (-1.0, 3.0), (1.0, 3.0),
(2.0, 2.0), (2.0, 0.0), (1.0, -1.0), (-1.0, -1.0),
(-2.0, 0.0), (-2.0, 2.0), (-1.0, 2.0),
(0.0, 1.5), (1.0, 2.5), (-1.0, 0.5),
(1.0, 0.0), (1.5, 1.0)
points = [A, B, C, D, E, F, G, H, I, J, K, L, M, N]
weights = randn(length(points))
tri = triangulate(points; weights)
Delaunay Triangulation.
Number of vertices: 13
Number of triangles: 16
Number of edges: 28
Has boundary nodes: false
Has ghost triangles: true
Curve-bounded: false
Weighted: true
Constrained: false
tri_unweighted = triangulate(points)
Delaunay Triangulation.
Number of vertices: 14
Number of triangles: 18
Number of edges: 31
Has boundary nodes: false
Has ghost triangles: true
Curve-bounded: false
Weighted: false
Constrained: false
fig = Figure()
ax = Axis(fig[1, 1], width = 400, height = 400, title = "Unweighted", titlealign = :left)
triplot!(ax, tri_unweighted, strokecolor = :black)
ax2 = Axis(fig[1, 2], width = 400, height = 400, title = "Weighted", titlealign = :left)
triplot!(ax2, tri, strokecolor = :red)
resize_to_layout!(fig)
fig
The triangles are of course not the same. Also, note that not all vertices appear in the weighted triangulation. To see the effect of the weights, let's reset all the weights to zero and see how the triangulation changes as we vary the weight of the point at $(x, y) = (0, 1.5)$, starting with a weight of $-10$.
w = Observable(-10.0)
weights = @lift (wts = zeros(length(points)); wts[10] = $w; wts)
tri = @lift triangulate(points; weights = $weights)
weight_itr_base = LinRange(-10, 10, 30*5)
weight_itr = vcat(weight_itr_base, reverse(weight_itr_base))
title_obs = lift(w -> L"w_{10} = %$(round(w, sigdigits = 4))", w)
fig, ax, sc = triplot(tri,
axis = (title = title_obs, titlealign = :left),
figure = (fontsize = 24,))
scatter!(ax, [J], color = :red, markersize = 13)
record(fig, "varying_weight.mp4", weight_itr; framerate = 30) do _w
w[] = _w
end;
See that, once the weight gets so large, it essentially dominates the triangulation.
Just the code
An uncommented version of this example is given below. You can view the source code for this file here.
using DelaunayTriangulation, CairoMakie
A, B, C, D, E, F, G, H,
I, J, K, L, M, N = (-1.0, 3.0), (1.0, 3.0),
(2.0, 2.0), (2.0, 0.0), (1.0, -1.0), (-1.0, -1.0),
(-2.0, 0.0), (-2.0, 2.0), (-1.0, 2.0),
(0.0, 1.5), (1.0, 2.5), (-1.0, 0.5),
(1.0, 0.0), (1.5, 1.0)
points = [A, B, C, D, E, F, G, H, I, J, K, L, M, N]
weights = randn(length(points))
tri = triangulate(points; weights)
tri_unweighted = triangulate(points)
fig = Figure()
ax = Axis(fig[1, 1], width = 400, height = 400, title = "Unweighted", titlealign = :left)
triplot!(ax, tri_unweighted, strokecolor = :black)
ax2 = Axis(fig[1, 2], width = 400, height = 400, title = "Weighted", titlealign = :left)
triplot!(ax2, tri, strokecolor = :red)
resize_to_layout!(fig)
fig
w = Observable(-10.0)
weights = @lift (wts = zeros(length(points)); wts[10] = $w; wts)
tri = @lift triangulate(points; weights = $weights)
weight_itr_base = LinRange(-10, 10, 30*5)
weight_itr = vcat(weight_itr_base, reverse(weight_itr_base))
title_obs = lift(w -> L"w_{10} = %$(round(w, sigdigits = 4))", w)
fig, ax, sc = triplot(tri,
axis = (title = title_obs, titlealign = :left),
figure = (fontsize = 24,))
scatter!(ax, [J], color = :red, markersize = 13)
record(fig, "varying_weight.mp4", weight_itr; framerate = 30) do _w
w[] = _w
end;
This page was generated using Literate.jl.