Doing NYT crosswords from 1994; this clue is a reminder how much things have changed since then. Can you even get a computer with a modem any more??
python Voronoi implementation
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.
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:
- All grid squares are assigned to their closest Voronoi seed.
- 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 on Discrete Grids
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:
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.
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
Went down a long and winding rabbit hole and stumbled upon this:
Scientific studies have been conducted to determine if cow tipping is theoretically possible, with varying conclusions. All agree that cows are large animals that are difficult to surprise and will generally resist attempts to be tipped.
And so now you know as well. Source (such as it is): https://en.wikipedia.org/wiki/Cow_tipping
Also, should you be planning on attempting a cow-tip:
Estimates suggest a force of between 3,000 and 4,000 newtons (670 and 900 pounds-force) is needed, and that at least four and possibly as many as fourteen people would be required to achieve this.
It’s a foggy morning on the hilltop.
Supreme Ruler of the Universe: Weep Holes
When I am Supreme Ruler of the Universe, no one will seal up weep holes. Not more than once, anyway.
Vote for me!
Supreme Ruler of the Universe: Non-profit Overhead
When I am Supreme Ruler of the Universe, everyone will be required to read and understand this:
Measuring a non-profit by how little “overhead” it has is wrong. Seriously, deeply, destructively, wrong. Please stop doing it. Read the paper and other related material to understand why.
Does Anyone Have a Pen?
I try to look at problems at the right level of abstraction. Here’s my illustration of why I think that’s important.
You’re in a group of people and someone asks: “Hey, does anyone here have a pen?”
What they are likely really asking is “does anyone have something to write with” because most of time a pencil would also be ok. Obviously there are exceptions — if they are signing a legal document. But most of the time people just idiomatically ask for a pen regardless of whether there is a strict requirement for a pen and not a pencil.
“Does anyone have something to write with” opens up the solution space and admits pencils, markers, crayons, and maybe even a lump of coal (lol) as possible answers. In contrast, “does anyone have a pen” presupposes the type of the solution within the question itself.
Go up a level of abstraction in your questions and thinking. Maybe go up multiple levels; even “does anyone have something to write with” could be too specific. Need to remember where you parked your car at the airport? You could write it down in a notebook. Or you could take a picture of the lot location with your phone. But maybe your phone is out of battery so you can’t … prompting you to ask a stranger to borrow something to write with. If whoever you are asking doesn’t have a pen but has a phone they could still help you (let’s ignore some privacy concerns for this illustration). They could take the picture with their phone and send it to you (to receive when you charge back up). Going up another level of abstraction to “how can I remember this” instead of “anyone have something to write with” admits even more potential solutions into the equation. At least we can think about them even if in this case we might decide not to share our phone number with a stranger.
Go as high up the abstraction chain as you can. That’s where all the good ideas come from.
Supreme Ruler of the Universe: Thermostats
When I am Supreme Ruler of the Universe, people who crank the room thermostat down to 50 because they think it will somehow cool the room off faster will be forced to live one week in a room that is 50 degrees, without any warm clothes, coats, or blankets.