Support for clipped/centroidal Voronoi tessellations on non-convex geometries and multiply-connected/disjoint triangulations

[DanielVandH]

[DanielVandH]

A good example that almost works is

using CairoMakie, DelaunayTriangulation
outer_boundary = [[(0.0, 0.0), (1.0, 0.0), (1.0, 0.3), (0.8, 0.3), 
(0.8, 0.5), (1.0, 0.5), (1.0, 1.0), (0.0, 1.0), (0.0, 0.0)]]
inner_boundary = [[(0.2, 0.2), (0.2, 0.6), (0.4, 0.6), (0.4, 0.2), (0.2, 0.2)]]
boundary_nodes, points = convert_boundary_points_to_indices([outer_boundary, inner_boundary])
edges = Set(((2, 8), (5, 7)))
tri = triangulate(points; boundary_nodes, edges)
A = get_total_area(tri)
refine!(tri; max_area = 1e-3A, min_angle = 31.5)
vorn = voronoi(tri)
smooth_vorn = centroidal_smooth(vorn; maxiters = 2500)
cmap = cgrad(:jet)
colors = get_polygon_colors(vorn, cmap)
voronoiplot(smooth_vorn, show_generators = false, strokecolor = :red, strokewidth = 0.2, polygon_color = colors)

[DanielVandH]

Note that sort_convex_polygon! inside the clipping code probably also needs to be changed once this works.

[CNOT]

Any news on when to expect this feature? I'm thinking about using this package for producing high quality Voronoi meshes over geographical regions which are typically not convex, and this feature would certainly be handy.

[DanielVandH]

No guarantees on any timeline, sorry @CNOT. Development on the package has temporarily stalled due to some life responsibilities, so can't say much for sure. I did have some ideas on how to address this, but haven't worked on anything yet.

e: See new notice on the README.

[DanielVandH]

@charperflow: In response to https://discourse.julialang.org/t/community-package-for-delaunay-triangulation-and-voronoi-cells/113249, specifically

I implemented an approach that would be able to do this, but now it appears that the DelaunnayTriangulation documentation has vanished and the creators github project page is unreachable.

Just wondering what your approach was for clipping to general convex boundaries? Is it similar to the current approach with a convex hull (I also have clipping to a general rectangle, but it's a bit specific to rectangles I think...)?

[CNOT]

@DanielVandH: I don't know about @charperflow, but I did dig into this issue a fair bit. IMO the cleanest method for voronoi mesh construction on non-convex 3D geometries is the VoroCrust algorithm https://github.com/sandialabs/vorocrust-meshing. The 2D case is a bit hacky, however it can be done using their package as well. One needs to build a 3D object by stacking 2 copies of the 2D object on top of each other and then extract the cell generator coordinates near the boundary. I'm pretty certain there is a more direct and less hacky solution for 2D objects using the same ideas, however it hasn't been implemented in their software.
I would love to see this being implemented in Julia!

[charperflow]

@DanielVandH Sorry for the latest response! Wrapping up the term and a bunch of applications, so it's quite hectic in my little corner of the world. Once things calm down in the transition to summer, I can dig back up the project, reorient myself, and give you a better response (probably 2-3 weeks)! Sorry!!

[DanielVandH]

@DanielVandH: I don't know about @charperflow, but I did dig into this issue a fair bit. IMO the cleanest method for voronoi mesh construction on non-convex 3D geometries is the VoroCrust algorithm sandialabs/vorocrust-meshing. The 2D case is a bit hacky, however it can be done using their package as well. One needs to build a 3D object by stacking 2 copies of the 2D object on top of each other and then extract the cell generator coordinates near the boundary. I'm pretty certain there is a more direct and less hacky solution for 2D objects using the same ideas, however it hasn't been implemented in their software. I would love to see this being implemented in Julia!

Thanks for the reference. I looked at VoroCrust some time ago but the ideas seemed to be a bit difficult to fit into the existing code which is best suited for a workflow of triangulation -> tessellate -> clip. It's certainly possible to implement it, but at the time I was hoping for an algorithm that relies on clipping. I guess a new interface would be defined for voronoi to be like triangulation, namely voronoi(points; boundary_nodes, kwargs...), and boundary_nodes defines the PLC to be clipped against in this instance (something like this at least). It probably won't be who implements this though, sorry, since I have some other research priorities currently, none of which actually need clipping (or even Voronoi for that matter). Especially with how complicated their algorithm seems to be.

@DanielVandH Sorry for the latest response! Wrapping up the term and a bunch of applications, so it's quite hectic in my little corner of the world. Once things calm down in the transition to summer, I can dig back up the project, reorient myself, and give you a better response (probably 2-3 weeks)! Sorry!!

No worries, no rush at all.

[DanielVandH]

@charperflow You might be interested in the latest release https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/11?u=danielvandh. I now allow you to provide a convex polygon to voronoi that the tessellation gets clipped to. Still no support for non-convex clipping boundaries, though.