Site removal for 2D Voronoi Diagrams?

[pkomiske]

Based on lines 761-792 of Voronoi_diagram_2.h, it looks like site removal for Voronoi diagrams is being considered but is not yet implemented. Is there a time frame for when this might be expected? I am developing a new high-energy particle physics tool for the LHC that would greatly benefit from this sort of functionality.

Thanks, Patrick

[lrineau]

The package Voronoi_diagram_2 from CGAL dates from 2006 (CGAL-3.2), and nobody is adding any feature to it since then. The CGAL project only maintains the code as it is. Do not expect anybody to add that sort of functionality.

Note that the functionality exists in the Delaunay_triangulation_2 of CGAL. Do you really need the voronoi diagram adapter?

[pkomiske]

Yes, I need the areas of the Voronoi regions as I remove sites from the graph. I assume that removing points from a Delaunay_triangulation_2 and then recomputing the Voronoi diagram is an unnecessarily expensive operation since a lot of redundant computation will be done. Perhaps it's possible to only recompute locally, but this is what I would hope that Voronoi_diagram_2 does. In any case, thanks for the response.

[MaelRL]

The class Voronoi_diagram_2 is only an adapter: it does not build the Voronoi diagram, it merely provides an interface that makes a Delaunay graph (Delaunay_triangulation_2, Segment Delaunay Graph 2, ...), which is actually built, to look like a Voronoi diagram. For example, if you call vd2.vertices_begin() to iterate over vertices, it is simply iterating over the (finite) faces of your primal Delaunay graph and constructing a Voronoi vertex from it on the fly.

When you create a Voronoi_diagram_2, it takes ownership of the Delaunay graph and stores it internally and only gives you a const& to the graph (via the function dual()). But I actually cannot recall any caching or anything requiring the dual to not be modified, so you could try a tiny hack and remove the const in the return type of dual() and see if you can just grab the Delaunay graph and remove a vertex with vd2.dual().remove(Vertex_handle v). It seems like it should just work. Obviously, if you modify the primal graph, any pre-existing Voronoi vertex or Voronoi face should be considered invalidated.

All in all, as @lrineau said, it might just be simpler to work on the Delaunay triangulation directly rather than trying to twist the adapter to do something that does not exist. For example, the area of the Voronoi face can be obtained with a Face_circulator and the function Delaunay_triangulation_2::incident_faces(Vertex_handle v) and getting the Voronoi vertices (face circumcenters) via Delaunay_triangulation_2::dual(Face_handle f). Feel free to ask if some things are not clear / if you're having trouble working on the primal (if you go that way).

[pkomiske]

Ok, this is helpful for understanding how Voronoi diagrams are handled in CGAL. I am now thinking about phrasing what I want to do entirely in terms of the Delaunay triangulation. I am considering the following: 1) Construct the Delaunay triangulation from my set of points. 2) Iterate over the points and the incident Delaunay faces to get the Voronoi vertices as the face circumcenters. 3) Compute the area of each region and store this. 4) Remove a point from the Delaunay triangulation. Recompute the area of adjacent regions only (these are the only ones that should change). Repeat this step.

You mention that removing a point invalidates existing vertices or faces. Does this mean, for instance, that I would not be able to use cached values from step 2 for the circumcenters of the Delaunay faces? In principle it seems possible that removing a point only affects the graph locally, so that faces that are incident on the neighboring points to the one that was removed, but didn't change as a result, could still be valid (and hence when they show up in a Face_circulator I could recognize this and use the cached value for the circumcenter). Does the implementation have any property like this, or should all faces be considered invalidated? Thanks again for the helpful answers!

[MaelRL]

The invalidation of vertices and faces I was talking about was only for the Voronoi adapter, if you were to choose to use the hack of modifying the underlying graph. If you are manipulating the Delaunay triangulation directly, only the removed vertex and faces naturally become invalid, but the rest will remain valid (namely, your handles to the adjacent vertices will still be valid).

As for the caching, you can find some inspiration in the 3D triangulations, for which there are cell base classes that compute and cache the circumcenter of the cell (https://github.com/CGAL/cgal/blob/master/Triangulation_3/include/CGAL/Delaunay_triangulation_cell_base_with_circumcenter_3.h and https://github.com/CGAL/cgal/blob/master/Triangulation_3/include/CGAL/Delaunay_triangulation_cell_base_3.h).

[MaelRL]

Feel free to reopen if you have any further questions.