This diagram is oddly selective about which airports it includes. It has some class D airports (Modesto, Santa Maria) but not others (Palo Alto, El Monte, Fullerton). There is no pattern that I can discern other than eliminating airports that are too close to each other, which kind of defeats the purpose of this exercise.
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.
Suppose that'll explain why there are at least three airports included in Ireland that have no scheduled services at all: the data's from nearly a decade ago
I noticed they included most all the tiny regional airports in Iceland, but left out ones like Kulusuk in Greenland, which receives international air traffic.
Receiving international traffic is actually not a good measure of an airport's significance. Grand View International (WN23), for example, receives international traffic (from Canada), but has only a single 1700-foot grass runway. (It's also private.)
LHPR does a lot of business for Audi, 33 000 passengers a year between the Hungarian factory and the Ingolstadt parent plant in Germany and also some cargo as well. There are charters as well. So it receives international air traffic, alright but there are no scheduled flights simply because the area airports have no capacity problems. With three capitals -- Vienna, Budapest and Bratislava -- all within an hours drive in an imaginary scenario where those would be congested it would be booming but this is not London.
That is weird indeed. Especially since there are regular scheduled flights from the Reykjavík airport[1] to Kulusuk. Reykjavík airport is included, along with most airports that have scheduled flights from there (like Ísafjörður and Egilsstaðir) but not Kulusuk.
[1]: not to be confused with the larger Keflavík international airport that handles almost all international flights to Iceland
Agreed - this leads to many of these subset areas being displayed as much larger than they should be, while others should be larger. Either eliminate class D, or don't - to be inconsistent seems pretty pointless.
I would guess they have injectors for the filling at the centers of those cells. A Voronoi edge is equidistant from the two points it bisects, so it kind of makes sense that this would happen naturally if the filling is injected at a constant rate.
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.
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 know the former bit. I don't see how the latter obviously follows. You're basically saying it's related because it looks the same but it's clear from the picture it looks the same.
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.
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.
It's worth noting that ETOPS only applies to 2-engine aircraft; a 4-engine aircraft can travel outside the ETOPS-permitted areas as long as it has enough fuel.
When people say "ETPOS" these days, it's understood that they're talking about the maximum distance an aircraft of any size can fly from an airport - various regulators still apply such restrictions on aircraft with more than two aircrafts.
I thought it stood for "Engines turn or passengers swim"
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 agree, Voronoi diagrams are so much fun! For that map project, at the last minute I switched to something slightly different. The page still says "Voronoi" but the actual demo doesn't use Voronoi. The Voronoi diagram uses the circumcenters of the triangles produced from Delaunay triangulation. I found that for my needs, the centroids worked better ("barycentric dual mesh"). Some comparison pictures here: https://www.redblobgames.com/x/1721-voronoi-alternative/ The graph connectivity is the same but the shapes are rounder.
I also love using Voronoi diagrams as well as Delaunay diagrams (via Mathematica).
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.
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!).
I spent a couple weekends trying to implement Voronoi via Fortune's algorithm in PHP, since there is no existing library for generating them.
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.
To be clear: quickhull is not "easy" compared to other things you might program, it's an involved algorithm. But honestly, all Voronoi/Delaunay algorithms are difficult to implement in performant fashion, there's no free lunch.
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
When I did it, I basically had to break down to the point of making a WinForms app that I could step through the algorithm iteration by iteration, drawing out the beach-line and and all the circles and edges as it progressed; I had to have that visualization to see that it was correct.
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).
Since Voronoi is a distance based measure, I'm not sure it would look any different. However, if airports were removed by weight, that would be quite interesting - to get a similar view but only for major airports
I've flown in and out of Mataveri and I know it sounds superstitious or whatever, but I felt that isolation. It's amazing to me that the Polynesians were able to colonize so widely.
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.
I am in love with the so-so reviews they happily places on the homepage of the airport: https://www.mataverinternational.com/ - "It's a small airport with just one place to eat and a few store to buy stuff." Truth in advertising lives!
What I thought was curious about this airport was that yes, it is indeed very small and very basic (the departure lounge included outdoor seating overlooking the tarmac - a small waist-high fence separating you from the apron), but the flights in and out were on brand new 787s!
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...
787 can land because the airstrip there is really long (more than 3Kms according to wikipedia. This airport was chosen by NASA at some point as an emergency landing stop for the shuttle, and paid for it's extension.
https://en.wikipedia.org/wiki/Mataveri_International_Airport
I cant see Baltra Airport in the Galapagos Islands (https://goo.gl/maps/x9PW5i4VWMH2) - it is "near" the most remote Mataveri Airport on Easter Island and may skew the most remote result to another airport?
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)
Yeah, he mentions that: "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."
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.
Yes, thank you. Looks nice, clean is operational and configurable and with ~80% of the functionality I had in mind.
I'm sure that with a few tweaks and a map as background/layer it would be perfect.
Strange that there isn't something like this around, would be useful for finding the nearest Starbucks, Pizza Hut, drugstore, whatever...
If only I/we could have some extra time for all those side projects :-(
I did some work on Voronoi a few years ago. I made an overlay in Voronoi transparent colored cells that would show for example where the nearest convenience store was to a given location in the city and this would overlay the regular map of the city. I was going to try to sell these to the convenience store as they always had a map of the city they were in somewhere in each store. An improvement would be to run a google map from each store to each house and actually use the mileage to the store the store. This would account for rivers etc that would block the shortest path. There is probably an idea for a startup somewhere there....
I've been grinding on an observation about the distribution of people on Earth. It can be reduced to the observation that the city of Ushuaia, AR at 55 degrees south is the most southerly city (FWIW the other two contenders for that title are near Ushuaia), while the city of Copenhagen, DK at 55 degrees north is definitely not the most northerly city. Although there is a great deal of land below the Antarctic Circle, there are only research stations there. There isn't as much land above the Arctic Circle, but civilians live above it.
I think this is more of an observation on the distribution of land masses than people. Ushuaia is as far south as you can go on a non-Antarctic continent. Conversely there is a ton of accessible and (relatively) resource-rich land north of Copenhagen (much of Canada and Russia, all of Scandinavia). Obviously the "great deal of land" below the Antarctic circle is extremely inhospitable and inaccessible to early settlers.
That's really interesting. Do you think it could be related to the effect of map projection biases? Is that a thing dates far enough back to affect settlement decisions?
I haven't done the research but if you look at the kinds of groups that are settled above the Arctic Circle and how they got there, vs how a group would have got to Antarctica, it may just boil down to accessibility. Whalers eventually patrolled Antarctica's seas but, if they tried to farm its shores they didn't get very far. The Polynesian settlers of the South Seas are hard to beat for navigation ability, but one imagines that either the seas were not worth crossing, or the lands were not worth populating, to those navigators. On the other hand, Greenland and Iceland have at times supported Europeans and their agriculture.
Antarctica was not well bounded on maps until the Wilkes expedition and others in the 1830's.
Interesting - was looking at some of the larger area ones in the US and learned that Santa Fe has a tiny airport - smaller than the one here near Bend, Oregon in Redmond. Seems Bend is bigger than Santa Fe for that matter... didn't realize that.
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.
When I did work on Voronoi, i used the Mathematica built in function. I would get the gps coordinants from Google maps and use them as input. The output put into a google function that could make rectangular colored transparent regions on the map. But this was all 2d.
I bet the vertices are correct, but shouldn't the lines in between them look like curves? They are projected solutions for the points that are equidistant by great circle distance to two airports, so I think they should themselves be great circle arcs.
They are great-circle arcs, but the presentation is a projected sphere, so the lines in the center will look straight because you're looking down on the curved part. Zoom out and look at the lines near the edges.
A different approach: you can distort the map underneath, similarly to those maps that scale regions as a function of population rather than actual geographic area.
It doesn't look like it. You can have different size airports serving vastly different volumes. It looks like the spacial distance is first factor, and then municipal boundaries. The boundaries are historical and can be based on population.
You misread the intention of the parent's comment. It's not that population _is_ taken into account (your interpretation), but that is _should be_ taken into account.
This is interesting because normally I'd assume this would just follow population density (Europe, the NA, Japan, see xkcd.com/1138) but India and China barely have any airports relative to their populations. That's a lot of traveling just to get to an airport.
This gives a lot of importance to small airports in small islands. Big international airports are surrounded by other smaller airports. They are associated with a tiny surface. I can not see how this representation may be of any use for airports.
This has a big influence on which routes a plane can fly. You can’t be more than a certain distance from a usable airport at any time during the flight to mitigate the risk of engine failure resulting in an off-airport landing/crash. See: https://en.m.wikipedia.org/wiki/ETOPS
