[ANN] DelaunayTriangulation v1.0: Curved domains and improved docs/code

Package Announcements
,
11

I’ve now released DelaunayTriangulation.jl 1.3.0 which is a pretty big release, bringing with it three really nice new features:

  1. Weighted Delaunay triangulations. These are triangulations of point sets where each point has an associated weight.
  2. Power diagrams. These are dual to the weighted Delaunay triangulations. Here, the Voronoi cells are defined in terms of the power distance metric instead of the Euclidean distance, i.e. the metric \pi(p, q) = d(p, q)^2 - w_p - w_q, where d(p, q) is the Euclidean distance and w_p and w_q are the weights of p and q, respectively. This could be a nice way to add non-Euclidean metric support to NaturalNeighbours.jl if anyone was interested in that (note that calls to triangle_circumcenter would be replaced with appropriate calls to triangle_orthocenter when is_weighted(tri), in addition to whatever else is needed.)
  3. Clipped Voronoi tessellations to convex polygons other than just the convex hull or rectangles (still no support for non-convex boundaries). The limitation to convex polygons is because the Sutherland-Hodgman algorithm is used. Hopefully, in the future, I can eventually use the much better VoroCrust algorithm.

I show examples of these three features below. Please see the docs for more examples Introduction · DelaunayTriangulation.jl.

image
image1003×349 75.8 KB

using DelaunayTriangulation, CairoMakie, StableRNGs
using DelaunayTriangulation: EllipticalArc 
# Weighted triangulation 
rng = StableRNG(123)
points = rand(rng, 2, 50)
weights = randn(rng, 50)
tri1 = triangulate(points; weights, rng)

# Power diagram: Just pass a weighted triangulation to voronoi! 
vorn2 = voronoi(tri1; rng)

# Clipping to an ellipse 
points = 5randn(rng, 2, 100)
weights = rand(rng, 100)
tri3 = triangulate(points; rng, weights)
ellipse = EllipticalArc((2.0, 0.0), (2.0, 0.0), (0.0, 0.0), 2.0, 4.0, 0.0)
t = LinRange(0, 1, 200)
clip_points = ellipse.(t)
clip_vertices = [1:(length(clip_points)-1); 1]
clip_polygon = (clip_points, clip_vertices)
vorn3 = voronoi(tri3; rng, clip = true, clip_polygon)

fig = Figure()
ax1 = Axis(fig[1, 1], title = "Weighted", width = 300, height = 300)
ax2 = Axis(fig[1, 2], title = "Power", width = 300, height = 300)
ax3 = Axis(fig[1, 3], title = "Clipped", width = 300, height = 300)
triplot!(ax1, tri1)
voronoiplot!(ax2, vorn2, show_generators = false, clip = (-5, 5, -5, 5))
voronoiplot!(ax3, vorn3, show_generators = false)
resize_to_layout!(fig)
fig
11 Likes