Voronoï diagram corresponding to constrained Delaunay triangulation

[stla]

Hello,

A couple of years ago, I did a R package for Delaunay and Voronoï tessellations. Now I'd like to implement the Voronoï tessellation dual to a 2D constrained Delaunay triangulation.

• Am I right to believe that CGAL is only able to compute the Voronoï diagram for an unconstrained Delaunay triangulation? I took a look at the doc, and I understood that it is computed from a given set of sites, so my guess is that the unconstrained Delaunay triangulation of these sites is constructed.

• If yes, I'll have to implement the construction from the constrained Delaunay triangulation. Would you know if the principle of the construction is the same as the unconstrained case? Or is there any difference?

[MaelRL]

The class Voronoi_diagram_2 is a simple wrapper around a Delaunay triangulation.

It does not compute anything, it only access combinatorial and geometric information of the primal graph and converts it on the fly to a Voronoi representation: for example, the Voronoi vertex v1 adjacent to a Voronoi vertex v0 is the dual of the adjacent face f1 adjacent to f0, the face dual of v0.

As such, there shouldn't be anything that prevents using it with a CDT, but you probably need to define the adaptation helper classes (see concepts AdaptationTraits_2, AdaptationPolicy_2).

You can find some examples of implementations for different Delaunay graphs in the include directory of the Voronoi package (https://github.com/CGAL/cgal/tree/master/Voronoi_diagram_2/include/CGAL). Here is for example the adaptation traits to construct Voronoi diagrams of the Triangulations on sphere package.

[stla]

Thanks. That sounds complicated to me. I will "manually" construct the Voronoï diagram from the constrained Delaunay triangulation (Joseph O'Rourke confirmed it's the same as the unconstrained case).

[stla]

I get it. But it remains to truncate the Voronoi edges that go outside the Delaunay triangulation...

[MaelRL]

I get it. But it remains to truncate the Voronoi edges that go outside the Delaunay triangulation...

You can use mark_domain_in_triangulation(), and not draw edges for which at least one incident face of the Delaunay graph is not in the domain.

[MaelRL]

Ah, no, you're already doing that and you want to truncate Voronoi edges. Then you can use CDT::locate() with the Voronoi vertices in the triangulation and if it finds a face that is not in the domain, you have to clip (or even fully remove) the edge.

[stla]

Thanks. Fine for locating. But I don't see yet how to clip. Is there some tool in CGAL that could help? The mesh clipping would not help, because it is restricted to triangle meshes.

[stla]

Maybe with the polygons intersection...

[stla]

I see, I can paint the inner hexagon in white (easy) and the complementary of the outer hexagon in white (using the CGAL features for polygons).

[stla]

I'm not sure this is a constrained Voronoï diagram... because the constraining edges are edges of the Delaunay triangulation here. Shouldn't they be edges of some Voronoï cells rather? This is my impression when I look at this picture:

So I mean a constrained Voronoï diagram is not a Voronoï diagram of a constrained Delaunay triangulation... What do you think? Will see if I find a definition somewhere.

[MaelRL]

https://hal.inria.fr/inria-00523812/file/centroidal-vd.pdf is probably of interest. @janetournois will know if/where there is some code (in CGAL or somewhere else).

[stla]

I'm right: this paper claims that the constrained Voronoi diagram is not the dual of the constrained Delaunay triangulation.

So I think the constrained Voronoï diagram is some job for CGAL ;-)

Thanks for the link, will take a look.

[stla]

[janetournois]

Hello,
indeed the "Bounded Voronoi diagram" described by Seidel is implemented in CGAL as an implementation detail of lloyd_optimize_mesh_2().

The full construction of the BVD is described in this paper and the main header is CGAL/Constrained_voronoi_diagram_2.h

[stla]

Thanks. Unfortunately understanding this code is beyond my skills.

I'm happy with my implementation, except I don't know how to clip the Voronoï cells that go outside the constraining region.