Voronoi Diagram Problems on a Grid

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!” 🙂

One Reply to “Voronoi Diagram Problems on a Grid”

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.