Neil's Notes

Uploaded my python code for implementing (grid-based) Voronoi diagrams. Available on github: https://github.com/outofmbufs/voronoi

See my previous post for discussion too.

Following up on my previous post about Voronoi diagrams on finite grids.

By a “finite grid” I mean something like this that you might write for a game:

PSEUDO-CODE (not in any particular language syntax)
# create a 100 x 100 map of the world
# start with SEA squares
for x in 0 .. 99
    for y in 0 .. 99
        grid[x, y] = SEA

# now make some LAND 
 ... (some algorithm goes here) ...

I wrote some code to create Voronoi cells from random seeds in such a grid, and ran into some odd situations as described in that previous post.

Today I figured out that it is impossible to create a finite-grid Voronoi diagram that is “correct” in the sense that it meets both of these criteria:

VORONOI CORRECTNESS CRITERIA:

1. All grid squares are assigned to their closest Voronoi seed.
2. All Voronoi cells are contiguous

Criterion #1 simply means that each grid square is assigned to the “correct” Voronoi cell. This seems pretty basic and obvious.

Criterion #2 simply means that each Voronoi cell is one contiguous “blob” of points, that it doesn’t have any isolated points elsewhere in the map that are not connected to it.

As it turns out you can’t guarantee that both of those will be true. There are situations where you will have to choose either between violating #1 and assigning a grid square to the “wrong” Voronoi cell, or violating #2 and assigning a grid square to the “correct” Voronoi cell even though it does not have any immediate neighbors (including diagonally) that are in that cell.

This surprised me until I understood it; then I realized it was obvious. It is an “obvious” two-dimensional implication of sampling and aliasing problems that are to be expected when you take a continuous domain (the actual Voronoi diagram) and sample it into a digital (discrete) domain. High frequency components will introduce aliasing errors in this situation, and in this case the definition of a “high frequency component” amounts to Voronoi cells that are “too pointy.”

Here’s an example you can plug into any Voronoi generation code:

Grid size: 25 x 25
Voronoi sites: (0, 6), (4, 3), (0, 12)

I plugged these into the Matlab Voronoi code, which computes a continuous solution and got this output:

The three Voronoi sites are shown: A=(0,6), B=(4,3), C=(12,0) and the entirety of the diagram is divided into three Voronoi cells accordingly.

Let’s zoom in where the three cells meet:

I’ve put coordinates on this zoom-in that would correspond to a finite grid using 1 unit squares, but in the drawing above they are subdivided into quarter squares that are each a half unit in size (in each of x and y). Thus each of our “integer grid” squares consists of four of these half-unit squares, centered on its coordinate. This diagram which zooms in even more illustrates that:

And now we can clearly see the dilemma. Look at the four colored grid-squares:

• RED: Centered on (15, 23)
• ORANGE: Centered on (16, 23)
• YELLOW: Centered on (15, 22)
• GREEN: Centered on (16, 22)

The Voronoi computation for each of these squares, computed at their center point (because, by definition, this is how we compute them in a finite grid), will assign them as follows:

• RED: A
• ORANGE: B
• YELLOW: A
• GREEN: C

You can run these calculations yourself if you want to verify what seems obvious from the picture. For example, for the YELLOW square at (15, 22) those calculations look like this:

(P.x, P.y) = (15, 22)
Distance (squared) to A=(0, 6): 
     deltaX**2 = (15 - 0)**2 = 225
     deltaY**2 = (22 - 6)**2 = 256
Distance (squared) to site A = 481
   .. using same method ..
Distance (squared) to site B = 482
Distance (squared) to site C = 493

If we run these calculations on all the grid squares (1-unit by 1-unit squares centered on the integer coordinates in that picture) we’d get this diagram for assigning the squares to cells:

For the 3 x 3 grid worked out in this diagram (remember: grid squares are centered on their integer coordinates):

• Five yellow squares are all assigned to Voronoi A.
• Two green squares are assigned to Voronoi C.
• Two purple squares, which do not touch each other, are assigned to Voronoi B.

There is no avoiding this. If we zoomed back out we’d see a large contiguous yellow cell for Voronoi A, a large contiguous green cell for Voronoi C, and a large, discontiguous, purple cell for Voronoi B.

The issue is rooted in the resolution (1 unit, in this example) of the finite grid we have imposed on top of a continuous-domain Voronoi diagram. Voronoi cell B is simply “too pointy” — in effect it has frequency components that are higher than the Nyquist rate. Or another way of thinking about it is that it is pointy enough so that it can reach the coordinate (16, 23) while dodging all of the immediately-neighboring (integer grid) coordinates.

There is good news and bad news here. The bad news is – there is no way to ensure that a Voronoi diagram computed on a finite-resolution grid will be “correct” if by “correct” we mean: obeys the VORONOI CORRECTNESS CRITERIA I listed up top.

The “good” news, if you think of it this way, is that this means that any approximation that runs efficiently and gets things right within reason can be considered “good enough” because fundamentally there is no one right way to do this computation anyway.

So, finally, bringing this back to the problem that sent me down this rabbit hole (in the midst of the enclosing Voronoi rabbit hole): My “expanding rings” algorithm faces a dilemma when trying to decide which Voronoi cell to choose for a grid square when two cells are equidistant from that grid square. And as I wrote in the other post, I was concerned that making the “wrong” choice might cut off the perimeter of an active Voronoi cell prematurely, leading to possible mischaracterizations of later cells. And I started searching for smart ways to determine what the “right” choice for those instances would be, to avoid causing wrong Voronoi assignments later.

That was turning out to be difficult as my random test generator kept finding cases that didn’t work out no matter what additional algorithm I tried for assigning the equidistant cases. Now I know that the underlying problem for at least some of those random test cases that got generated is this problem described here: sometimes there literally is no choice that is “correct” (that meets both of those correctness criteria laid out).

So, we’re back to the easy answer: “Who cares!” 🙂

Voronoi Diagrams

Day 2 of COVID-19 social distancing. All of my meetings and travel for the upcoming week are cancelled, my calendar is now strangely empty, and I could probably make use of this extra time to do something wildly productive.

Instead, I have randomly dived into this particular rabbit hole:

https://en.wikipedia.org/wiki/Voronoi_diagram

Read the Wiki page for the real details, but in summary: take a set of points called “seeds” (or sites). For each seed, the corresponding Voronoi cell is the set of points that are closer to that seed than to any of the other seeds. That set will be a polygon around the seed (and every point in that polygon will be closer to its own seed than to the seed of any other polygon).

An example Voronoi diagram:

Let’s say we are writing a map generator for a “world consisting of land and sea grid squares” game. We want to generate random blobs of land and sea that seem plausibly arranged. Voronoi diagrams are one way to do that – create some random Voronoi cells and choose a subset of them to be land and the rest to be sea. You can imagine how that would work using the above picture and visualizing some of those polygons as being land and the rest sea. In practice you would probably want more individual cells (i.e., finer-grained), so that as they clump together when randomly selected they look less obviously like the Voronoi polygons that they are. You might also still need to do additional post-processing on the results; you can go down another rabbit hole googling this topic. The Voronoi idea just gets you close as a starting point. But I digress… so: back to the Voronoi computation.

The “gold standard” algorithm for generating a Voronoi diagram appears to be Fortune’s algorithm.

https://en.wikipedia.org/wiki/Fortune%27s_algorithm

And of course the right answer to most questions of “how to implement something in python” is “google it; because five people have probably already done it” and that is definitely the case here.

But there’s time to kill and this seems like a fun project so I decided to play with these diagrams. I did not (or have not, yet) tried implementing Fortune’s algorithm. It is complicated and requires study. Instead I plowed ahead with the somewhat-obvious “brute force” approach:

Let G be a grid
      Each G[x, y] being a point a.k.a "grid square"

Let S be a list of points
      Each S[i] being the (x, y) point for the "seed" of a cell

For each point, pt, in grid G:
    For each site, s, in list S:
        compute distance between pt and s
        assign pt to the closest Voronoi site

This works. It is not fast.

This brute-force algorithm has order n