2D Voronoi diagram (demo for windows)
Mouse interaction:
- left click: insert new generator
- right click & drag: move generator
- two buttons: display triangle circumcircles (to highlight empty circumcircle property when Delaunay edges are displayed)
Generators:
Press "R" to generate a new set of random points
Press "O" to change the number of generators (speed ~ 30K/s on a modern laptop)
Rendering options:
Press "V" to toggle Voronoi edges
Press "D" to toggle Delaunay edges
Press "C" to toggle centroids of Voronoi cells (center of mass)
Simplest demo
Incremental construction of a Voronoi diagram:
- menu Generators / clear
- insert one generation at a time, show partition of plane into cells (closest from each generator)
- show dual Delaunay triangulation ("D"): a Delaunay edge connects two generators if a Voronoi edge is common between two generators. Move one generator using right click&drag to trigger an edge flip wich maintains the Delaunay property.
- Show empty circumcircles incident to one generator (choose one generator, and press both mouse buttons & drag). This property is always maintained during relocation.
More advanced demo:
Lloyd iteration: to illustrate a Voronoi diagram "at work" for uniform point sampling.
A typical demo script:
- generate a random point set ("R")
- toggle display of center of mass of each Voronoi cell ("C"). Move one generator using right mouse button + drag to show that it is dynamic.
- Run one Lloyd iteration ("L"): moves each generator to center of mass, and update Voronoi diagram.
- Run several iterations (press "L" several times) to show convergence toward a uniform point sample distribution.
- Run Lloyd iteration in repeat mode ("CTRL+L"), you can even continue inserting generators using left click on the window. Press Ctrl+L again to toggle the Lloyd iteration off.
- Show Lloyd iteration on a larger point set ("O", 20K points, then "R" and "Ctrl+L")