I had to limit the number of airports displayed for performance reasons. I filtered the airport data so that only those airports with scheduled services and which are denoted "large" or "medium" are included (according to OurAirports), bringing the number down to 2,980.
However that's all nitpicking, this is a pretty cool map, I'd never encountered Voronoi diagrams before.
: not to be confused with the larger Keflavík international airport that handles almost all international flights to Iceland
I actually wrote into the Reese's company to find out what that was happening to their giant cups, and got no reply unfortunately.
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.
That's the important part. Oh and you should like butyric acid too (most commonly found in vomit).
I love chocolate and peanuts. Can't stand any chocolate flavoured "candy" coming from the US.
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.
Imagine that the peanut butter is not poured from the top, rather coming from holes at the bottom of the cup. Initially there's a radially growing patch of peanut butter around each hole. When the peanut butter patches grow large enough, they touch, and form an approximately straight boundary (if the flow rate is equal for all outlets) like the boundary between crystal domains.
Of course, peanut butter is a fluid, so its dynamics are ultimately different from crystal growth, but at this scale, it produces a very similar phenomenon thanks to its high viscosity.
ETOPS is for twin engines (T for twin). Those restrictions do not apply to 3 and 4 engine aircrafts.
I'm not sure I'd like to be on a plane 6 hours from an airport -- better hope you don't have any sudden medical requirements that would lead to a diversion!
Fortune's Algorithm is pretty simple, but it's tricky to get right, particularly if you're also maintaining the information in a form that lets you do something useful with it besides spitting out the points of the Voronoi centers.
I've not implemented Fortune's myself. I use the Delaunator library, which maintains all the additional information I wanted in the form of a half-edge triangle mesh: https://github.com/mapbox/delaunator ; Mike Bostock wrote a Voronoi wrapper on top it: https://beta.observablehq.com/@mbostock/the-delaunays-dual
My most recent exploration with them was to understand and visualize the different structures and characteristics of various low discrepancy quasirandom point distributions in two dimensions.
Also interesting to compare them with @burfog's comment about the Voronoi / Delaunay diagrams of Penrose Tilings.
1. Fortune's algorithm 
2. The Bowyer-Watson algorithm for generating the Delaunay triangulation incrementally 
3. Quickhull (which generates the 3D convex hull of points, which is the 2D delaunay triangulation of points). 
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 ). 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!).
: https://en.wikipedia.org/wiki/Quickhull (this description is for the 2D version, but the 3D version is similar)
I couldn't get past the point of creating a seemingly random mass of intersecting lines. My math knowledge is lacking (I'm not good at groking geometry for some reason), so I wasn't sure what was wrong or how to approach fixing it.
Maybe I should give Quickhull a go. I think I understand what it's doing.
The hardest part of quickhull in 3D is the "horizon" calculation: basically, every time you add a point to the hull, you have to find all the faces that the point can "see", and the horizon of all those faces, and replace them with new faces. This page describes the horizon part well: http://algolist.manual.ru/maths/geom/convhull/qhull3d.php
If the weights are multiplicative, the edges between adjacent cells become circular arcs. It looks cool, but it's much more difficult to generate and analyze. For instance, the region belonging to a generating point is no longer guaranteed to be convex, and may even have holes or be in multiple disconnected pieces.
Weighted Voronoi diagrams show up sometimes in multi-agent systems where agents have different speeds, e.g. pursuit-evasion problems, or in facility placement (where to build a new store/warehouse, etc).
Also, I love Voronoi diagrams. I ran across them many moons ago when I was building a wayfinding application and was looking for ways to generate map meshes—this was not that—but I thought they were super interesting.
Easter Island really does feel very remote though. Even though the 787s are jam-packed with tourists, you're flying due-west from Chile for 6 hours to a tiny spec in the middle of the pacific. The in-flight map was mostly just entirely blank the whole time since the island itself is so tiny it didn't really show up!
In the museum there they had some really interesting exhibits about how the original inhabitants used interesting navigation aids to find land - e.g. looking for the directions birds were flying or sea-turtles were swimming, or the sea swell etc. Fascinating stuff. https://en.wikipedia.org/wiki/Polynesian_navigation#Navigati...
(Posted in 2014 too but there weren't really comments: https://news.ycombinator.com/item?id=7557438)
I guess not all airports are included (e.g there is one I've flown into as a tourist to the antarctic peninsula that is missing (https://goo.gl/maps/u54LnTDYb8N2)
Great visualisation though :)
The list of airports in Antarctica is surprising long, but most of them are ice or snow and probably need to be remade each year. Some are hard to impossible to see on google maps, but many are quite visible.
If only there was a webpage/software where someone could click/select points on a map (or even better enter coordinates) and a user Voronoi diagram would be created ;-)
I'd love to see it as real tiles. The nicest looking might be pearly-white granite or quartzite, with pink granite for the pentagons. Adding grey into the mix, I think a floor could be done without same-color adjacent tiles. I wonder where I could buy this.
If only I/we could have some extra time for all those side projects :-(
and a very good tutorial:
on how the UK supermarkets Voronoi map was made:
also have a look at (code included):
Antarctica was not well bounded on maps until the Wilkes expedition and others in the 1830's.
However, the Polynesians were not cold weather people, and the subantarctic islands are extremely remote.
It was hard enough as it was for the Polynesians to settle New Zealand, I can't imagine them settling any further south.
Most of them are just hard packed ice.
Which means that the Albuquerque one ends up as the largest, it looks like, followed (eyeballing it) by Elko?
Recently, I was working on a WebGL version that renders all 54,000+ airports and got it working again today after seeing this.It's quite pretty and runs well but needs some love.
He would be cheering if he had this in his web browser.
"There are in fact airports on Antarctica, but they are not classed as medium or large, and do not have scheduled services according to this dataset."
> 2,980 large and medium airports with scheduled services from OurAirports.
"2,980 large and medium airports with scheduled services from OurAirports."
You could do different versions of this for different classes of plane (e.g. select a minimum runway length).