1
$\begingroup$

In the course of trying to implement algorithms for Voronoi and Laguerre diagrams, I realized I needed to verify if my implementation is working correctly using a point (or circle) configuration with a known Voronoi (or power) diagram.

I have not been successful in looking for datasets with known diagrams. Does anyone know a good source for these diagrams?

|cite|improve this question
$\endgroup$
2
$\begingroup$

The most trivial pointsets are regular grid of points. They look innocent, but are the most difficult to handle in Voronoi/Laguerre codes because the Delaunay triangulation is non-unique, so they can be used to detect bugs in your code. They can be handled by adapted geometric predicates (see my publication [6] on geometric predicates and the references herein).

To detect bugs in my Voronoi/Laguerre diagram code in 2D and 3D [1], I used the following approach:

  1. Compute the Voronoi/Laguerre diagram for a collection of pointsets (random) and test that the output of your code satisfies the empty ball property. For Voronoi, this means that the circumscribed circle(2d) or sphere(3d) of each Delaunay triangle does not contain any point. For Laguerre, there is a similar condition;

  2. Compute the Voronoi/Laguerre diagram of random pointsets with a code that you trust [1] (if you trust me), [2],[3] (I trust them) and compare with the output of your code;

  3. Add to the list of pointsets difficult ones. The difficult datasets are those that have cocyclic (2d) / cospheric (3d) points such as regular grids that I mentioned before. Note that when you got cocyclic / cospheric points, the Delaunay triangulation is non-unique (then the output of your code may differ as compared to other codes);

  4. When all the weights are set to zero, the Laguerre diagram is a Voronoi diagram, then you can compare the output of your algorithms (if they mismatch, then both are probably wrong, like it happened to me).

I strongly recommend to use a continuous integration platform [4] to do automatic non-regression testing. Voronoi/Laguerre code is not very complicated (approx. 300 lines of code), but there are some gotchas/subtleties, in particular in the predicates for handling cocyclic points. Automatic daily tests (doing 1., 2., 3., 4. + Valgrind [5] memory test) allowed to detect several bugs in my own code.

[1] Geogram: http://alice.loria.fr/software/geogram/doc/html/index.html

[2] CGAL: http://www.cgal.org

[3] Tetgen:http://wias-berlin.de/software/tetgen/

[4] https://jenkins.io/

[5] http://valgrind.org/

[6] https://hal.inria.fr/hal-01225202

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I already had a good routine for making 3D convex hulls, so I was looking into exploiting it for making 2D Voronoi and Laguerre diagrams. I'm still stuck on generating the boundary cells, but I will be adapting your suggestions. Thank you! $\endgroup$ – J. M. Sep 1 '17 at 13:52
  • $\begingroup$ You can take a look at the documentation of qhull (www.qhull.org), it is a nD convex hull algorithm, and they got examples on how to use it to compute (n-1)D Voronoi (and maybe Laguerre) diagrams. $\endgroup$ – BrunoLevy Sep 1 '17 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.