Ideas for (constrained/visibility-constrained) Voronoi tessellations about delaunaytriangulation.jl HOT 3 CLOSED

Edited the title since I need to add back in the Voronoi feature in general. I'm not sure what people do here when working with constrained triangulations, so for now Voronoi tessellations would probably only be created from unconstrained triangulations.

Trimmed tessellations will still be important. It's very complicated to get it correct apparently...

from delaunaytriangulation.jl.

Now that constrained triangulations and mesh refinement are added, Voronoi tessellations are probably the next important thing to add. I probably won't get around to it for a while, but there was some time ago where I did have this feature, I just wasn't so satisfied with the data structure - e.g. in the data structures in the gist below, do I really need to store a mapping that takes circumcenters to their associated triangle, and triangles to their associated circumcenters? - maybe I should just assume that people will carry with them both Triangulation and Tessellation). If all you want is the unbounded tessellations, that's quite easy.

For posterity, here is what I did actually have for Voronoi tessellations (this was incomplete, and the package has been rewritten since). Most of the complexity is in trying to find a way to trim unbounded tessellations so that they clip to the boundary (or the convex hull), since I didn't know much at the time about when circumcenters are outside of the domain.

https://gist.github.com/DanielVandH/83b6a0ce4d6b2866d865f173cd686530

from delaunaytriangulation.jl.

Likely what will end up happening is that I define a struct that can be defined entirely separately from Triangulation. It should be able to support:

• Accessing all sites
• Accessing all Voronoi cells. This must be a vector rather than a Set, since it is typical that we want to enumerate the polygons.
• Query the cell adjacent to an edge.
• Query the site adjacent to an edge.
• Query all cells adjacent to a site.
• Query all edges adjacent to a vertex.
• Query all obstacles (for the dual graph to a constrained DT, i.e. a constrained Voronoi or visibility-constrained Voronoi diagram)
• Query all boundary cells

This last point allows for unbounded cells to be queried. When the obstacles include the boundary, this becomes less relevant as all cells will be bounded, so boundary cells might be better named unbounded_cells to make this point clear? Or we can use both.. So, perhaps something like

struct VoronoiTessellation # (or just Tessellation? too close to Triangulation maybe)
    sites::P # the circumcenters + added points from obstacles 
    polygons::Vector{VoronoiCell} # the polygons
    adjacent_cell::Adjacent{Int64, NTuple{2, Int64}} # map edge to adjacent polygon 
    adjacent_site::Adjacent{Int64, NTuple{2, Int64}} # map edge to adjacent site 
    site_to_cells::Adjacent2Vertex{Int64, VoronoiCell, Int64}
    site_to_sites::Graph{Int64}
    cell_to_cells::Graph{Int64} # maybe? 
    obstacles::Set{NTuple{2, Int64}}
    boundary_cells::Set{Int64}
    unbounded_cells::Set{Int64}
end

struct VoronoiCell
    nodes::Vector{Int64}
end

These data structures need also support point location and (equivalently, actually) nearest neighbour queries. Not sure if we should just use methods for searching planar subdivisions, or somehow re-use the jump and march code so that the problem becomes taking a triangle to its associated Voronoi cell (derived from its circumcenter). In this latter case, there are two options:

• Store the triangulation in the VoronoITessellation. I'm not so sure about this, but we could.
• If people want to perform point location, they provide both the VT and the DT

I don't intend to add support for point deletion/insertion or obstacle insertion for Voronoi tessellations. Not against it, but I don't have a need for it.

e: Using site pretty loosely here. I probably mean polygon vertex in most cases.

from delaunaytriangulation.jl.