World Airports Voronoi (2014) | Hacker News Reader

World Airports Voronoi (2014)

jasondavies.com

424 pointsJoelSanchez107 comments

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 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.

This is probably the most frequently asked question! The data is from here: http://ourairports.com/data/

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 am amused how airports like Lands End (which was grass runways only before 2014), and Chester(!!) made the cut. Plymouth closed in 2011

However that's all nitpicking, this is a pretty cool map, I'd never encountered Voronoi diagrams before.

Interesting. The data is from 2014, which is when I created the visualisation. Perhaps I should auto-update it every so often!

Most recent item on "recent changes" was five years old in 2014. Galway Airport's certainly been shut for a lot longer than that.

St Helena airport is open and technically operational. It's certainly one of the most remote airports on the planet (this happened post 2015)

It would be nice if there was a slider for N. I like to think my computer is recent, but evidently it is not!

You will find the pattern, such as it is, explained at http://ourairports.com/about.html#credits .

Mammoth is also missing, which has commercial flights, as does Bakersfield (also missing).

This is my favorite instance of a voronoi diagram: https://imgur.com/a/zjNWL

I actually wrote into the Reese's company to find out what that was happening to their giant cups, and got no reply unfortunately.

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.

I wasn't aware there was anything below the chocolate-like surface, so I understood you to be saying the same thing as grandparent.

Which country are you in? If you like chocolate and peanut butter (and sugar), I recommend trying a Reese's cup :)

I am in the UK, and I cannot eat nuts.

Well you're not missing out that much. USA chocolate isn't nearly as good as UK chocolate.

> (and sugar)

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.

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

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 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.

crystal seed = peanut butter nozzle crystal growth = peanut butter flow

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.

https://en.wikipedia.org/wiki/Voronoi_diagram#Applications has explanations and an animation.

Yeah thanks, that's not telling me anything new.

I did a similar visualisation a few months ago, but less polished, for my own curiosity: https://twitter.com/iandioch/status/968938231550107649

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.

Depends on the jurisdiction, the FAA applies the same rules to 4-engine aircraft that are carrying passengers now.

e.g. http://boeing.mediaroom.com/2015-03-18-Boeing-747-8-Intercon...

And ETOPS was one of the reason for the trijets. Just recently watched: https://www.youtube.com/watch?v=gxnptDPy47M about this.

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.

> is actually unreachable by any commercial flight from the closest airport.

ETOPS is for twin engines (T for twin). Those restrictions do not apply to 3 and 4 engine 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!

Voronoi diagrams are so fun. I messed around for months with them after I saw Amit Patel's procedural map generator that used them.

http://www-cs-students.stanford.edu/~amitp/game-programming/...

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.

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

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...

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.

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.

This sounds like a good way for me to understand it. I'll have to try this. Thanks!

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

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'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

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.

http://extremelearning.com.au/unreasonable-effectiveness-of-...

Also interesting to compare them with @burfog's comment about the Voronoi / Delaunay diagrams of Penrose Tilings.

I wonder what happens if you "give weight" to each point relative to size of the airport (measured e.g. by number of take-offs/landings per year)?

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

Then you get a "weighted Voronoi diagram," haha.

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).

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

Discussed from 2015: https://news.ycombinator.com/item?id=10161326.

(Posted in 2014 too but there weren't really comments: https://news.ycombinator.com/item?id=7557438)

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)

Great visualisation though :)

It says "2,980 large and medium airports with scheduled services from OurAirports.": http://ourairports.com/data/

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.

https://en.wikipedia.org/wiki/List_of_airports_in_Antarctica

Nice one, actually all Voronoi diagrams are cool.

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 ;-)

Voronoi diagrams of Penrose tilings are extra cool. There are six at the bottom of this page: http://www.josleys.com/show_gallery.php?galid=284

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.

This does the job nicely http://alexbeutel.com/webgl/voronoi.html

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 :-(

Just so that other people don't have to search: http://lpetrich.org/Science/GeometryDemo/GeometryDemo_GMap.h...

and a very good tutorial: https://chriszetter.com/blog/2014/06/15/building-a-voronoi-m...

on how the UK supermarkets Voronoi map was made: https://chriszetter.com/voronoi-map/examples/uk-supermarkets...

also have a look at (code included): http://bl.ocks.org/shimizu/5610671

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.

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.

A lot of the subantarctic islands have similar weather to the Faroe Islands in the North Sea.

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.

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.

If you want to know more about those Antarctic airstrips, there's a great Wendover video on them:

https://www.youtube.com/watch?v=-s3j-ptJD10

Most of them are just hard packed ice.

As someone who studied Voronoi diagrams in college, I find this really fascinating. It's a really cool way of visualizing the data.

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?

http://voronoi.surge.sh/

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.

Thanks, you are totally right. Was zoomed in too far.

Come on now what about Willy Field or the South Pole skiway? The USAP kind of has a schedule...

I assume it's using the great circle distance metric. I wonder how it would look like if the metric was "shortest land/sea travel time".

This is awesome. Now I'd love to be able to visualize which aiports are flown to/from the one under the mouse... Where can one get this data?

https://openflights.org/data.html

awesome, ty!

What would happen if distance over sea is penalized by a certain factor? Is there an extension of Voronoi diagrams that addresses this issue?

Voronoi diagrams work for any definition of `distance` that may suit your needs. So weighting by airport size and/or sea distance is pretty trivial.

I don't think it's that simple if the definition of distance is a function of position.

Yeah I'm pretty sure that whilst the 'mid' points on Delauny triangulation would be correctly scalped the edges of the Voronoi diagram would be wrong?

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.

There must be a correlation with population density

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.

Hmm, could be, but how can you definitively determine that? :)

This is gorgeous. For me it recalls Fuller's Dymaxion map.

He would be cheering if he had this in his web browser.

Am I missing something, there are a number of airports in Antartica, I assume that none of these are commercial though:

https://en.wikipedia.org/wiki/List_of_airports_in_Antarctica

From the bottom of the page:

"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."

It's also a (population density) x (per capita income) map.

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.

#whut? (headline)

Doesn't work on my mobile (OnePlus5t) without requesting desktop site

There are obviously more airports in the world than this. What are the criteria for inclusion in the visualization?

It's at the very top of the description, just below the globe.

"2,980 large and medium airports with scheduled services from OurAirports."

Inclusion by http://ourairports.com/data/ in the categories "medium" or "large".

> 2,980 large and medium airports with scheduled services from OurAirports.

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.

It doesn't seem to me that it's designed to be "useful" as much as just interesting.

I guess that would be useful in a case where you'd want a representation with an importance that is reversely proportional to the airport importance.

Ability to divert in an emergency?

Absolutely. It's a map of closest airport for any location on earth.

You could do different versions of this for different classes of plane (e.g. select a minimum runway length).

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

And diversion airports of course vary with things like weather

Reply on news.ycombinator.com