World Airports Voronoi | Hacker News Reader

World Airports Voronoi

jasondavies.com

338 pointsmorgante82 comments

This is really cool. If I remember right international passenger flight regulations insist that there be atleast one airport that can handle your class of aircraft within 180 minutes of flying time at one engine operative speeds at all times. If we assume a passenger jet flies at roughly 0.8 Mach or ~960 kph, and one-engine operative speed is roughly 40% of that or ~384 KPH. That means an airport needs to be within a circle of radius 1152 kms. That's an area of ~4.16M km-squared. Simplifying that all airports can handle all passenger jets, not one of those voronoi cells can have an area greater than 4.16M km-squared.

Is there an easy way to calculate the area of each cell?

Did I mention this is really cool!!

The regulations you're thinking of are ETOPS (Extended-range Twin-engine Operational Performance Standards or, alternatively, Engines Turn or Passengers Swim).

Lol! Engines Turn or Passengers Swim! Excellent.

And those only pertain when you fly out of reach of a suitable airport to land on, in the case of flying on one engine, in still air for > 60 minutes.

ETOPS clearance has now reached 330 minutes for the latest aircraft types

http://boeing.mediaroom.com/2014-05-28-Boeing-Receives-330-M...

ETOPS also now applies to new-build quads.

"Regulation 14 CFR 121.161 requires four-engine passenger airplanes built after February 2015 to observe ETOPS if the flight route is more than 180 minutes (3 hours)"

I believe that's only true for 2 engine aircraft.

Virgin Australia briefly ran a service from Melbourne to Johannesburg using 777s, which was 2 hours longer than it needed to be for this reason. Looking at this map, it's clear why: the great circle path almost goes over Antarctica, and the closest airports over the path are in Australia and South Africa.

This runs slower on my computer than MGSV in ultra settings running on 4k resolution.

It’s projecting thousands of sphere geodesics at pixel precision via breaking them into a large number (hundreds of thousands?) of little line segments and evaluating several expensive nonlinear functions at each of those points with considerable Javascript dataflow overhead for each one, not to mention the cost of putting thousands of polygons with dozens or hundreds of points each into SVG.

It would take either a domain expert or someone willing to spend a few months studying the problem to write an optimized version, but then it could probably be made to run a couple orders of magnitude faster by using slightly coarser approximations for various function evaluations (no need for 10^-15 precision for drawing on screen), or by simplifying the problem to require fewer function evaluations overall (e.g. by using Bézier curve segments instead of straight line segments), rewriting the core of the library to be vectorized, and rendering via a raster- rather than DOM-based drawing system. I’m sure a GPU could handle such a problem very effectively, though working with WebGL might be a pain.

Anyway, go for it!

It runs Voronoi every step instead of building polygons once?

Why?

No it does not. Computing the spherical polygons that make up the Voronoi diagram just happens once.

The expensive part is rendering them in an arbitrary map projection.

Considering this is an orthographic projection, and therefore spherical polygon edges are all ellipses, rendering this picture could certainly be special-cased to only draw ellipses and thereby run much faster. But it’s using a very general D3-geo framework. If you want you can easily tweak the code and the map will be drawn on whatever projection you like.

To see some of the possibilities, go to http://bl.ocks.org/mbostock and scroll down a bit.

Completely unusable on my iPad Air. Damn.

It's amazing how fast computers are. And it's amazing how slow we make them with layers and layers of cruft built atop more layers and layers of cruft.

The difference is that all you have to do to view this is punch a URL into a browser, on virtually any computer in any form factor, and it's on your screen instantly with absolutely zero setup. Of course there's a performance cost to this incredible convenience.

Imagine if the author had instead used, say, DirectX and C++ and only bothered compiling it for his own platform. Not only would it be nearly impossible for this to have reached the same audience so quickly, but it likely would have taken the author longer to make as well because JavaScript + D3.js are uniquely suited towards rapidly making these sorts of prototypes.

Hmm, that's not really fair. Programmer time is a major consideration.

We live in a time where a complicated, interesting visualization like this can be built in a day or two, and appear as #3 on hacker news. Less than 10 years ago it probably would have taken 10x the time, maybe more, and your iPad Air didn't exist.

Without those layers of 'cruft' putting together something like this would involve weeks of work by a team of domain experts, rather than a few hours of work by a single person in his free time.

Hmmm, which one is the result of a team of experts competing with other major corporate entities, getting paid to optimize a set of well-known algorithms for months prior to delivery to an audience of millions who will spend thousands of hours with it and which one is a one-off hack meant to demo the first iteration of some new code for the first time on its new platform?

I know right?? It's mind-blowing! My PC can push millions (is that the order of magnitude?) of polygons per second. But it locks up an entire core to render a couple hundred polygons (plus the layers of cruft), and can't do it at more than ~10Hz.

Rendering isn't the slow part here. The projection is (and map projections are quite expensive to calculate).

It's projecting polygons/lines on a sphere (all the rest could and should be precalculated), am I missing something or how would this be expensive on a modern computer five years ago?

It's not like it's doing global illumination pathtracing or anything.

It's not smooth, but totally usable on my i7-3770K workstation.

For what it's worth, it's also fun that key elements of the text are dynamic. When I first landed on the page with noscript suppressing any script, I saw:

> Most Remote Airport

> … at … is the most remote; from the nearest airport, .

Usually if I see any text, I don't bother enabling script, so this confused me. Luckily I did enable the script and then saw the principle UI element on the page. :)

What's really needed is an OpenGL/WebGL implementation of D3.js

cesium.js is kinda in that direction (for the specific case of visualizations on a globe).

CPU bottleneck, not graphics card.

Of course. And JS is not a compiled language. And a language that was not created with performance in mind. I mean, I know this stuff, I can think of a lot of reason for it.

But the end result is just toooooooooo much for any reasons.

Pretty soon there's going to be a nice big new polygon added in the middle of the South Atlantic: https://en.wikipedia.org/wiki/Saint_Helena_Airport

Looking at the map, I am liking some of the place names on St. Helena;　"The Gates of Chaos" is a particular favourite.

Something tells me you'll like the noun the inhabitants use for themselves. Hint: They don't call themselves "helens".

What a cool project! This is very fun to play with in conjunction with the ETOPS (extended twin-engine operations) settings on the Great Circle Mapper. http://www.gcmap.com

Among other things it drives home how remote the waters MH370 disappeared in are.

I recently did ORD-HKG and spent quite a lot of time thinking about ETOPS diversion airports over Siberia (because honestly what else are you gonna do). Now I'm wondering if you can even land a fully laden 777 at any of them. Most of them don't even seem to have wikipedia pages.

A few years ago I flew to the north of Sweden in January and as expected the ground was covered in snow. What surprised me was that the runway wasn't cleared - we actually landed on the snow. This was in a Boeing 737 so not exactly a small aircraft.

I suspect there's a lot of places in Siberia where you can land a 777 just fine. It's the amenities in the terminal building (if there is one) that won't be too appealing.

In Soviet times, a lot of civil infrastructrure was built with an eye to military use, so you get some suspiciously long runways at rinky-dink airports.

Two comments.

1) This appears to be only airports that offer commercial passenger service.

2) Easter Island has an airport! I was under the impression you could only get there by boat.

Easter Island doesn't just have an airport on it, it's got an airport with a runway built long enough to accommodate the Space Shuttle.

It's an awesome place to visit - a town of a few thousand people, surprisingly good food, breathtaking moai, and due to its relative remoteness, not particularly crowded with tourists. I liked it enough to want to go back.

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

The upgrade of the runway to support the Shuttle started in May 1986 (https://news.google.com/newspapers?nid=2245&dat=19860423&id=... ) and ended by August 1987 (https://news.google.com/newspapers?nid=860&dat=19870817&id=Y... ).

"In addition, astronauts now carry passports and other documents, including traveller's cheques, in case of emergency landings."

Given the high cost of every pound when launching things into space this seems at first glance to be a pretty lousy idea. It seems to me solving this problem through diplomatic channels would be a much better plan given the fairly low probability of this event.

Space shuttle cargo was something like $20,000/pound. If each astronaut needs a pound of paperwork for contingencies (which seems like a vast overestimate) then that's $20,000 each, which is tiny. And the marginal cost per pound was small. Given that you're doing a launch anyway, you're probably not exactly at the mass limit, so a few extra pounds of paperwork costs almost nothing.

The problem has been even more economically solved by cancelling the shuttle

Note the '[citation needed]' - I think that text comes from the publisher's comments in the book. If so, well, publishers aren't known to be scrupulously honest.

https://www.hipmunk.com/flights#f=JFK;t=Easter+Island,+Chile...

Hipmunk comes up with this amazing itinerary: New York to Los Angeles, then LA to Sydney (!), then back across to Santiago, spend 22 hours in the airport and finally 6 hours to the final destination.

The second LA to Sydney flight takes off September 2nd and lands on September 4th!

https://www.hipmunk.com/flights#f=JFK;t=Easter+Island,+Chile...

It reminds of play the amazing retro-future 80days game: http://www.inklestudios.com/80days/

> The second LA to Sydney flight takes off September 2nd and lands on September 4th!

But when you fly from Sydney to LA you arrive before you left :) All thanks to the international date line.

I flew to IPC (aka Easter Island Airport) in 2013. It actually has a massive runway due to being a Space Shuttle diversion site, although the terminal itself is a glorified shack. Flying there (from Santiago) was a bit terrifying knowing how far away you are from any alternate airport, or any civilization at all really.

There are a couple of airports with regular commercial service missing from this map. They're quite new though (0-3 years). Probably just old data.

There's definitely a handful of airports in Antarctica. Are they not "official"?

Well they certainly have iata codes and serve larger aircraft than places like albany wa.

Wilkins supports normal commercial aircraft like the a319

Curious if there's any region smaller than that of LaGuardia Airport. A glance doesn't find any.

London City is probably smaller.

L'Esperance and (maybe?) Caye Caulker airport are smaller.

As a South African, I never realised we have a few airports that are actually the closest to a large part of the Antarctic coast. I know there are flights from Chile and New Zealand to Antarctica, but none that I'm aware of from South Africa.

I thought that a voronoi partition is not possible with only straight lines on a non-euclidean space like that; this leaves me confused.

You are in fact correct that the boundaries of the Voronoi cells on a non-Euclidean manifold need not be geodesics. Consider for instance the manifold which is a cone with a circular base, and let the sample points be the apex of the cone and the center of the base. The boundary of the two cells thus produced will be a circle parallel to the base, which is not a geodesic on the cone.

The edges are segments of great circles, which are the reasonable equivalent to a straight line on the surface of a sphere.

Or another way to look at it: if you model the earth as a perfect sphere, there's a one-to-one monotonic relationship between geodesic distance and distance in a straight line through the earth. Points that are equidistant by one metric are also equidistant by the other.

So you could get exactly the same diagram by finding the 3D Voronoi diagram of the airports as a collection of points in space, and then taking the intersection of that with the geoid.

They must be geodesics, not straight lines

I believe Voronoi can be applied on high-dimension points, producing polytopes.

So, run Voronoi on 3D points that happen to all be on the sphere... Then intersect the polytopes with a sphere. Tada - great arcs.

It looks like you still just use delaunay triangulation on the points on the surface of the sphere. And then he is connecting the resulting vertices with lines along the surface of the sphere. The lines look straight from head on, but are curved in 3d space.

Actually I think you use delaunay tetrahedrization on the points in 3-space. The points HAPPEN to be on the surface of the sphere.

Then you intersect the sphere with the polytopes, which result in great arcs.

It looks like the furthest point from any airport is (not surprisingly) about the same place as Point Nemo (https://en.wikipedia.org/wiki/Pole_of_inaccessibility#Oceani...), the furthest point from land.

Off-topic, but if you want to see a great talk about working with Voronoi in Clojure, watch this:

https://www.youtube.com/watch?t=627&v=hzLAX_pr-Wc

Hm, appears to be missing a lot of smaller airports in the USA. My home airport (E45) in particular. I'm guessing it's only using airports that have commercial air carrier service of some sort.

They're using OurAirports data, filtered to exclude all but "large" and "medium" airports. Anything smaller than that includes all sorts of cruft like African bush landing strips, heliports, etc.

http://ourairports.com/data/

I think there is about 10,000 airports in the US, so I bet it is missing quite a few.

This is the type of thing that's so simple and rewarding that it makes me annoyed that I hadn't thought of it and made it first! Really cool, good work!

Looks cool, but would have been a lot smoother in webGL

This is awesome, and I really wish it would give me information on which airport each tile represents.

You can hover over a tile to get the airport's name.

So cool (though it includes Plymouth City Airport, which is sadly closed)

Neat, but it would be nice if it could zoom out a little more or adjust to the browser window size. I have 2560x1600 display split into four equally sized panes, and it's difficult to use and view in a single pane.

This badly wants labels.

This is awesome!

Very nice!

@shitsandwich just in case you see this, you are hellbanned.

I check someone's comment history before alerting them - the previous comments by that handle were all trolls. Hellbanning is meant to block these users; no point telling them.

Hellbanning (as opposed to the many, many other options available to a moderator) is one of the most disrespectful and passive-aggressive types of moderation.

To clarify, a hell-ban is the type of ban where a user's posts are hidden from everybody except themselves (and on HN, those with "showdead" enabled in their profile settings).

It ranks right between simply redirecting a login to a browser-bomb page (which is slightly more evil, except for the part where it doesn't potentially waste months of a person's time) and slow-bombing/random timeouts/delays (which is ever so slightly less of a dick move to do to someone's account, yet almost always works better than a hell-ban).

Except in the most extreme cases (anything short of a mentally disturbed, obsessive, or dangerous person that otherwise just won't go away), reaching for a hellban is always the wrong choice, because there's always another moderation option that deals with the situation both more effectively, as well with more respect and dignity to one's entire userbase.

Reply on news.ycombinator.com