World Airports Voronoi (2014)

Interesting to compare with ETOPS (good maps: gc.kls2.com) which governs how far away from acceptable alternate airports a commercial plane can be. It corresponds to safe flying time with a single functional engine. So a lot of the area in some of the larger Voronoi regions, especially in the Southern Hemisphere, is actually unreachable by any commercial flight from the closest airport.

Patterns like this form in cooling rocks although I have no idea whether that's related to peanut butter cups.

I also consider Voronoi diagrams fun, and in my life I've implemented three different algorithms for generating 2D Voronoi diagrams (or Delaunay triangulations, which are the duals of Voronoi diagrams):

1. Fortune's algorithm [0]

2. The Bowyer-Watson algorithm for generating the Delaunay triangulation incrementally [1]

3. Quickhull (which generates the 3D convex hull of points, which is the 2D delaunay triangulation of points). [2]

Of these, Quickhull is the simplest, and Bowyer-Watson is by far the hardest. Bowyer-Watson seems very simple, but there are demons hiding in that algorithm, and almost every implementation you can find online is incorrect (for instance, this one [3]). You can tell that these implementations of Bowyer-Watson are incorrect, because every Delaunay triangulation contains the convex hull of the points, and it's easy to tell when they don't. In fact, even the description in Computational Geometry: Algorithms and Applications (a standard textbook) is subtly wrong.

The reason Bowyer-Watson is hard is this: it's an incremental algorithm where you add the points one-by-one to an already constructed Delaunay triangulation, you make sure all edges are flipped right, and at the end you have the full triangulation. However: you have to have a triangle to start with. In order for the algorithm to work, this initial "super-triangle", has to contain all the points in the set, and also be made up of points that are not contained in any circumcircle of any combination of three points in the set. However: if three points are colinear (or very close, which it is almost guaranteed some points are going to be), the circumcircle of those three points is MASSIVE (essentially "infinite", covering the entire half-plane). But the super-triangle points still have to be outside of it. This means that the super-triangle points have to be essentially "symbolic" points (not normal points with coordinates, but special magic points), and you have to hard-code special rules for them. It is extremely difficult to implement these rules correctly.

Fortune's algorithm is on the surface more complex, but there's less goblins hiding in that algorithm. There's some tricky data-structure stuff, but it's not too bad. Quickhull is fairly straight-forward, and is the algorithm I would recommend if you want to give this whole Voronoi adventure a go (also has the benefit of giving you a 3D convex hull algorithm, which you can have all sorts of fun with!).

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

[1]: https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorith...

[2]: https://en.wikipedia.org/wiki/Quickhull (this description is for the 2D version, but the 3D version is similar)

[3]: https://cdn.rawgit.com/axelboc/voronoi-delaunay/v2.1/index.h...

It is related.

When rocks cool, crystals start to grow from multiple seeds because of thermal/chemical impurities. If the material is sufficiently homogenous in composition and temperature, then the crystals from different seeds will grow at the same rate. When they grow into each other, a boundary between different crystal domains will form. Crystal domains formed this way look like Voronoi cells.

The peanut butter cup looks like this because it's injected from several outlets with an approximately constant flow rate. Each injector outlet forms a Voronoi cell of peanut butter under it.

I'd guess more likely that they are chocolate nozzles -- it seems more straightforward to me to produce a precise chocolate "cup", pour or place the filling inside of it, then pipe a chocolate "lid" onto the cup. Presumably the multiple nozzles of chocolate would help it to settle flatter faster.

Edit: there's a video on Facebook that covers the whole process in a minute. My hunch is partly right: the wrapper and chocolate cup are indeed completed first, then a circle of peanut butter is indeed placed in, then the thing is shaken to encourage that peanut butter to fill the space uniformly. However the chocolate "lid" is just plopped on as one wide dollop from a hose, and then blown out across the cup with compressed air: so the Voronoi cells probably come either from this blowing phase, or else the hose has some sort of "spreader" inside of it or so.