Construct tessellation from arbitrary shape, not just a Rectangle

[jacobusmmsmit]

In my application, it would be nice to calculate a tessellation inside an arbitrary bounding shape. What needs to be implemented for this to work? With some guidance I could implement it myself, but it seems that Rectangle is a key part of this as many of the Cells functions take rect as an argument, as such it may take some effort.

[robertdj]

You're right -- Rectangle is a key part. It would indeed be nice to allow a more general bounding region (and has been requested before in #17).
Unfortunately, when I looked into this in the spring I realized it would take quite some work and did not proceed.
But when there are multiple people who request this I'll try to look into this.

[robertdj]

Looking more in to this I think it should be possible to compute the intersection of a tessellation with a convex polygon, but there is work to be done.

The major obstacle is a way to clip line segments to their intersection with such a polygon. The clipping packages in this org have not been updated in a while and I don't know how much work it is to updated them/implement such a clipping algorithm.

The remaining things are about updating types and minor computations (like determining whether a point is inside a polygon or not). That should be doable.

Are you up for looking into how big of a task the clipping is?

[robertdj]

@juliohm I recall from discussions in this org/Discourse that you intend for Meshes.jl to also include functionality for computing Voronoi tessellation/Delaunay triangulations?
When that becomes a reality a package like VoronoiCells is probably obsolete. But I have not seen anything related to Voronoi tessellations in Meshes, yet. Do you know when you plan to work on this? I'd prefer not to work in parallel :-)

[juliohm]

Hi @robertdj thanks for pinging. We have some research planned for next year that may overlap with this set of planned features. It would be really nice if we could join efforts to define an API in Meshes.jl for tesselations that is flexible enough and works out of the box with the geometries that are being extensively tested in our test suite. Currently we only have discretization methods implemented, i.e. methods that take a 2D or 3D geometry and divide it into elements: https://juliageometry.github.io/Meshes.jl/stable/algorithms/discretization.html and refinement methods that take an existing mesh and subdivide the elements: https://juliageometry.github.io/Meshes.jl/stable/algorithms/refinement.html

Given an initial mesh, we can also generate well-spaced points for the Voronoi-Delaunay tesselation: https://juliageometry.github.io/Meshes.jl/stable/algorithms/sampling.html#Meshes.MinDistanceSampling so we can easily create well-spaced points inside a surface mesh for example to start the tesselation routine and produce a mesh of higher-quality.

If you have a real demand to get tesselations working in more general settings, I think that is the most important ingredient. We are happy to review PRs and share directions. You will notice that we are super pedantic with our code style and source code organization and that is to make sure that anyone can master it after a couple of weeks reading the files.

[robertdj]

Thanks for the detailed answer @juliohm
The holidays is where I have most time to work on open source, so that's why I'm picking this up now :-)

Just to align expectations: Would you like input only on the design of methods for tessellations or also code contributions?
Do you imagine an implementation of Voronoi / Delaunay capabilities to resemble the algorithm used in VoronoiDelaunay?

Finally, I cannot promise how much time I have next year.

[juliohm]

Just to align expectations: Would you like input only on the design of methods for tessellations or also code contributions?

Both are very welcome! I mentioned design because that is where things start usually.

Do you imagine an implementation of Voronoi / Delaunay capabilities to resemble the algorithm used in VoronoiDelaunay?

Yes, ideally we should be able to revamp and cleanup the code to be more aligned with the existing design patterns in Meshes.jl I didn't have a chance to read the algorithm, but we should aim for a design that accommodates different algorithms and implementations like we do with discretization methods.

[robertdj]

Sorry about my long absence! We're probably derailing this issue, so let's continue elsewhere if needed :-)

After reading up on VoronoiDelaunay and Meshes I'm not sure how much I can contribute with. The inner workings of VD is kinda opaque to me -- I just use it as a black box. Using weeks on getting familiar with Meshes is unfortunately not something I can do currently.

But if you want my input on anything specific I'll be happy to provide that.

[DanielVandH]

FYI @robertdj @jacobusmmsmit, for your interest, DelaunayTriangulation.jl has a feature similar to what is needed in this issue, namely clipping the tessellation to a boundary that isn't just a rectangle. Currently the boundary that is guaranteed to work is the convex hull of the underlying generators (e: as of v1.3, any convex polygon works), but the functionality is pretty close to working on any boundary formed by the generators (JuliaGeometry/DelaunayTriangulation.jl#48). I imagine it wouldn't be too complicated to generalise this to be a boundary that isn't just from the generators also, but I've not looked into that.

You can look at the actual implementation here https://github.com/DanielVandH/DelaunayTriangulation.jl/blob/main/src/voronoi/clipped_construction.jl, or the discussion here https://danielvandh.github.io/DelaunayTriangulation.jl/dev/tessellations/clipped/, if you wanted to see what goes into it.