Triangulation: Bounded Random Voronoi Diagrams

In an upcoming blog series, we will have need of a randomly-generated Voronoi diagram. Specifically, we will want a diagram for which all of the bounded Voronoi cells lie within a given square. Equivalently, we would like the Voronoi vertices to all lie within a given square.

At first glance, this would seem like a hard problem. We have already seen that if a Delaunay triangle is obtuse, its associated Voronoi vertex lies outside the triangle, and for angles approaching 180 degrees, the vertex could end up arbitrarily far from the Voronoi sites. How can we quickly generate a random set of Voronoi sites while guaranteeing that none of the resultant Delaunay triangles along the convex hull are too obtuse?

It turns out that this problem is actually fairly straightforward. The 'One Weird Old Trick' (in internet parlance) is to ensure that none of the sites you randomly generate are on the convex hull of the Delaunay triangulation, and to also include a set of sacrificial points which will form the convex hull. Through a careful selection of hull points and bounds on the extent of the random points, you will get the result you desire.

To make the example complete: let us start with a unit square centred at the origin. We will then create twenty sacrificial points, five along each side. These points, and the resulting Voronoi diagram, are arranged to look like this:

We want the random sites we generate to lie within the convex hull of these points; otherwise, the site in question must belong in the convex hull. There is another restriction on the random points, though: we do not want them to lie inside of any circle whose diameter is one of the convex hull edges:

Why this restriction? We are trying to prevent an obtuse angle amongst the Delaunay triangles which make up the convex hull of our point set. It is a known result in geometry, provable from the Inscribed Angle Theorem, that if you make a triangle with one side being the diameter of a circle and the opposite point being on the circle, the opposite angle will be 90 degrees. Therefore, the random points generated must be on, or outside of, these diameter circles in order to guarantee that the Voronoi vertices are in the range we desire.

We now have two strategies available for us to generate our random Voronoi sites. The first option is to generate a random point inside the box, and reject it if it is within any of the diametric circles. This will allow your resulting Voronoi diagram to completely fill the box, in theory:

The second, faster option is to recognize that there is a 'safe' square inside of our unit square. We can thus generate random points that are within +/- 0.4 of the origin along each axis, and then no testing against circles is necessary. If you do this, your resulting Voronoi diagram will have a distinctive, stamp-like edge if you fill it with enough points:

A few closing remarks:

There is nothing special about the square shape we have used. The key to the technique is simply to start with a convex hull, and then to generate random points that are within the convex hull, but not within diametric circles of that convex hull. This technique can be trivially extended from squares to rectangular shapes. It can also be extended to any convex polygon: generate the polygon, divide up the polygon edges into short segments, and then generate/test random sites. This will only require more logic to test a randomly-generated site for whether it is valid or not. The choice of a square (or other axially-aligned quadrilateral) was to trivialize the validity check.

By splitting the edges of the square into shorter line segments, you can make the 'safe' box inside of the convex hull come closer to the edges of the full box.