Skip
# Sphere Factory

Voronoi polygons contain all points that are

Delaunay triangulation is a first-step in the calculation to producing the Voronoi polygons (which for my purposes have always been much more relevant).

posted by Jimbob at 5:19 PM on May 8 [3 favorites]

oceanjesse, as I tweeted when I saw this: "Now I want to see a live 3D voronoi diagram of all orbiting spacecraft."

posted by jjwiseman at 5:39 PM on May 8 [1 favorite]

posted by ignignokt at 7:17 PM on May 8

Heh. Now, the scandinavian countries make sense. Also, Mexico gets its land back.

posted by vacapinta at 3:46 AM on May 9

...How many capitals does South Africa have?

posted by psoas at 4:32 AM on May 9

Yeah I can't quite figure out what's going on there, even with Lesotho. That map really needs labels. I'm trying to figure out south-east Asia, too, because something seems to be missing in regards to Cambodia/Vietnam/Laos.

posted by Jimbob at 5:04 AM on May 9

Voronoi tessellations are fairly intuitive, and other people have explained them well. It's simply that for each dot (airports in this case), the cell surrounding it are all the points closest to that dot. So in this case, each cell is the area of the world closest to to the airport dot inside that cell.

Delaunay triangulations are a little tricker to explain. A triangulation is simply a thing where you take a bunch of points and make triangles out of them. No cell can have more than three edges, and edges can't cross each other. What's special about a Delaunay triangulation is that if you make a circle of each triangle (if you have three points which are do not lie on the same line, you can make only one circle where all three points lie on the perimeter), no circle contains a dot that's not part of the triangle. As it turns out, for any given set of non-collinear points, there's only one way to do this (in other words, the Delaunay triangulation is unique).

Also, as it turns out, Voronoi tesselations and Delaunay triangulations are intimately connected. They're "duals" in graph theoretic language. Basically, if you sort-of "flip" the edges in the triangulation and connect them, you get a Voronoi tesselation.

Voronoi tessellations tend to be more interesting and useful than Delaunay triangulations, but they're also much harder to calculate directly. The algorithms for quickly calculating Voronoi tessellations directly (like Fortune's algorithm) can be incredibly complex and hard to implement. Implementing something that calculates the Delaunay triangulations is also hard, but not nearly as complex. As a result, most programmers who wish to make a computer program that calculates a Voronoi tessellations usually actually write a program that computes the Delaunay triangulation, and then calculates the tessellation from that. It's not as efficient a method, but it's a hell of a lot easier.

I should know. I spent about a week in my spring of youth trying to properly understand and implement Fortune's algorithm, at which point I said "fuck this shit!", and started from scratch doing it the other way. I've always sort-of regretted that I didn't stick with it and cracked the nut, because Fortune's algorithm is so damn cool.

posted by gkhan at 6:12 AM on May 9 [2 favorites]

klang- a couple people have talked about voronoi diagrams but not given much love to Delaunay triangulations, so I'll talk a little about them.

There's actually a really easy way to imagine how they work. Imagine a bunch of points on the plane. Now, connect every point to every other point with a line segment. Notice that with any set of points with more than 4 points in it, some of those lines will intersect. For each intersection, we're going to choose a single line segment participating in that intersection that we want to keep and delete the rest. The segment we want to keep should be the shortest (in case of ties, just pick one randomly, it's all good).

Intuitively, you can imagine all the points sitting around and having conversations with each other. The Delaunay triangulation of a set of points will connect the points that can converse with each other without the awkwardness of having to talk past another person or through another conversation.

posted by Jpfed at 6:15 AM on May 9 [2 favorites]

Europe is, interestingly, mostly preserved.

posted by So You're Saying These Are Pants? at 6:19 AM on May 9

Weird, must be a mistake in the dataset. Joburg isn't a capital of South Africa.

posted by Lemurrhea at 10:56 AM on May 9

Post

# Sphere Factory

May 8, 2014 3:25 PM Subscribe

Spherical Voronoi diagram of world airports

(Note: At first, I missed the fact that you can drag the sphere to turn it around, but you can! You can also add your own points to the model on the main Spherical Voronoi Diagrams page. Scientifically speaking, the way the new region squidges around as you move the potential seed position is really neat.)

(Note: At first, I missed the fact that you can drag the sphere to turn it around, but you can! You can also add your own points to the model on the main Spherical Voronoi Diagrams page. Scientifically speaking, the way the new region squidges around as you move the potential seed position is really neat.)

By the amazing Jason Davies, who works with Mike Bostock on D3.js. Jason has contributed a lot of the d3 geo code, he does all sorts of fun work with projections and the like.

posted by Nelson at 3:32 PM on May 8 [4 favorites]

posted by Nelson at 3:32 PM on May 8 [4 favorites]

Lots of great stuff! I like the countries visually sorted by area.

Greenland is smaller than the Congo.

posted by vacapinta at 3:41 PM on May 8 [2 favorites]

Greenland is smaller than the Congo.

posted by vacapinta at 3:41 PM on May 8 [2 favorites]

I find it hard to rotate that globe without the Katamari Damacy song going in my head.

posted by crapmatic at 3:43 PM on May 8 [3 favorites]

posted by crapmatic at 3:43 PM on May 8 [3 favorites]

Very cool. Another reason on the already lengthy list of reasons to learn D3.

However, the GIS analyst in me keeps on complaining about MAUP.

posted by graxe at 3:56 PM on May 8 [1 favorite]

However, the GIS analyst in me keeps on complaining about MAUP.

posted by graxe at 3:56 PM on May 8 [1 favorite]

Holy shit. I saw a demo of d3.geo.voronoi a few months ago, and it was awesome then but is

posted by ignignokt at 4:02 PM on May 8

*amaze*now.posted by ignignokt at 4:02 PM on May 8

A pretty awesome application of 2D voronoi diagrams: Bostock and co. at NYT Graphics use it to create optimal mouseover targets on graphs in which there's a lot of mouseover-able points densely packed together.

posted by ignignokt at 4:05 PM on May 8 [10 favorites]

posted by ignignokt at 4:05 PM on May 8 [10 favorites]

I like that my airport covers a fair slice of Antarctica.

posted by Jimbob at 4:07 PM on May 8 [3 favorites]

posted by Jimbob at 4:07 PM on May 8 [3 favorites]

I would love to see a Voronoi diagram of the world's

posted by oceanjesse at 4:40 PM on May 8 [2 favorites]

*airplanes*.posted by oceanjesse at 4:40 PM on May 8 [2 favorites]

This is the sort of thing I would never have thought I needed to see, but now that I know it exists I am very glad I have seen. Thanks!

posted by Joe in Australia at 4:51 PM on May 8

posted by Joe in Australia at 4:51 PM on May 8

Surprised myself by being able to identify LaGuardia without a label.

posted by ardgedee at 4:56 PM on May 8

posted by ardgedee at 4:56 PM on May 8

I read the wikipedia page, but I'm still not sure how Delaunay triangulation functions. I kinda wish they'd had a diagram with just once circumcircled triangle. From the airports page, it looks like the largest circle without any other points within it, but I don't understand the way they phrased it and I'm afraid I'm missing something.

posted by klangklangston at 5:04 PM on May 8

posted by klangklangston at 5:04 PM on May 8

Nifty, thanks.

posted by Alexandra Kitty at 5:08 PM on May 8

posted by Alexandra Kitty at 5:08 PM on May 8

Delaunay/voronoi diagrams are one of my

These are

posted by BungaDunga at 5:09 PM on May 8 [2 favorites]

*favorite things*. So are globe projections.These are

*lovely*.posted by BungaDunga at 5:09 PM on May 8 [2 favorites]

*I read the wikipedia page, but I'm still not sure how Delaunay triangulation functions.*

Voronoi polygons contain all points that are

*closest*to the input point, quite simply. Each of those polygons covers an area of the earth, where every location within it is closer to that airport than any other.

Delaunay triangulation is a first-step in the calculation to producing the Voronoi polygons (which for my purposes have always been much more relevant).

posted by Jimbob at 5:19 PM on May 8 [3 favorites]

ignignokt, I hope I'm not outing myself as a very boring person but that's the most sublimely clever thing I've seen all week.

posted by figurant at 5:38 PM on May 8

posted by figurant at 5:38 PM on May 8

*I would love to see a Voronoi diagram of the world's*airplanes

*.*

oceanjesse, as I tweeted when I saw this: "Now I want to see a live 3D voronoi diagram of all orbiting spacecraft."

posted by jjwiseman at 5:39 PM on May 8 [1 favorite]

Here's an intuitive demo of Voronoi Tesselation. Your mouse makes one more black dot. And here's a fancier interactive. The Delauney triangulation is just the dual of the Voronoi, they're equivalent.

posted by Nelson at 7:08 PM on May 8 [2 favorites]

posted by Nelson at 7:08 PM on May 8 [2 favorites]

OK, I'll say it: seems kind of arbitrary in which airports are included? This is going to be meaningless to most people reading this, but: Modesto but not Stockton?

posted by psoas at 7:12 PM on May 8

posted by psoas at 7:12 PM on May 8

**figurant**, I saw Mike Bostock present that (it was a passing part of his talk), and I was super charmed and amazed. The whole room was, really.

posted by ignignokt at 7:17 PM on May 8

I like the one of world capitals.

I'm not sure which country comes out worse if you reorganise territory by capital.

The Us certainly loses a lot of ground to Canada and Mexico (Also, Cuba)

Most of the UK is closer to Dublin than London.

posted by Just this guy, y'know at 3:01 AM on May 9 [2 favorites]

I'm not sure which country comes out worse if you reorganise territory by capital.

The Us certainly loses a lot of ground to Canada and Mexico (Also, Cuba)

Most of the UK is closer to Dublin than London.

posted by Just this guy, y'know at 3:01 AM on May 9 [2 favorites]

*I like the one of world capitals.*

Heh. Now, the scandinavian countries make sense. Also, Mexico gets its land back.

posted by vacapinta at 3:46 AM on May 9

*I like the one of world capitals.*

...How many capitals does South Africa have?

posted by psoas at 4:32 AM on May 9

*...How many capitals does South Africa have?*

Yeah I can't quite figure out what's going on there, even with Lesotho. That map really needs labels. I'm trying to figure out south-east Asia, too, because something seems to be missing in regards to Cambodia/Vietnam/Laos.

posted by Jimbob at 5:04 AM on May 9

Oh it does have labels, I see, and I've figured out Asia. But yeah, wtf South Africa...

posted by Jimbob at 5:05 AM on May 9

posted by Jimbob at 5:05 AM on May 9

The map has 4 (Pretoria, Johannesburg, Bloemfontein, and Cape Town).

posted by psoas at 6:09 AM on May 9

posted by psoas at 6:09 AM on May 9

*I read the wikipedia page, but I'm still not sure how Delaunay triangulation functions.*

Voronoi tessellations are fairly intuitive, and other people have explained them well. It's simply that for each dot (airports in this case), the cell surrounding it are all the points closest to that dot. So in this case, each cell is the area of the world closest to to the airport dot inside that cell.

Delaunay triangulations are a little tricker to explain. A triangulation is simply a thing where you take a bunch of points and make triangles out of them. No cell can have more than three edges, and edges can't cross each other. What's special about a Delaunay triangulation is that if you make a circle of each triangle (if you have three points which are do not lie on the same line, you can make only one circle where all three points lie on the perimeter), no circle contains a dot that's not part of the triangle. As it turns out, for any given set of non-collinear points, there's only one way to do this (in other words, the Delaunay triangulation is unique).

Also, as it turns out, Voronoi tesselations and Delaunay triangulations are intimately connected. They're "duals" in graph theoretic language. Basically, if you sort-of "flip" the edges in the triangulation and connect them, you get a Voronoi tesselation.

Voronoi tessellations tend to be more interesting and useful than Delaunay triangulations, but they're also much harder to calculate directly. The algorithms for quickly calculating Voronoi tessellations directly (like Fortune's algorithm) can be incredibly complex and hard to implement. Implementing something that calculates the Delaunay triangulations is also hard, but not nearly as complex. As a result, most programmers who wish to make a computer program that calculates a Voronoi tessellations usually actually write a program that computes the Delaunay triangulation, and then calculates the tessellation from that. It's not as efficient a method, but it's a hell of a lot easier.

I should know. I spent about a week in my spring of youth trying to properly understand and implement Fortune's algorithm, at which point I said "fuck this shit!", and started from scratch doing it the other way. I've always sort-of regretted that I didn't stick with it and cracked the nut, because Fortune's algorithm is so damn cool.

posted by gkhan at 6:12 AM on May 9 [2 favorites]

*I read the wikipedia page, but I'm still not sure how Delaunay triangulation functions. I kinda wish they'd had a diagram with just once circumcircled triangle. From the airports page, it looks like the largest circle without any other points within it, but I don't understand the way they phrased it and I'm afraid I'm missing something.*

klang- a couple people have talked about voronoi diagrams but not given much love to Delaunay triangulations, so I'll talk a little about them.

There's actually a really easy way to imagine how they work. Imagine a bunch of points on the plane. Now, connect every point to every other point with a line segment. Notice that with any set of points with more than 4 points in it, some of those lines will intersect. For each intersection, we're going to choose a single line segment participating in that intersection that we want to keep and delete the rest. The segment we want to keep should be the shortest (in case of ties, just pick one randomly, it's all good).

Intuitively, you can imagine all the points sitting around and having conversations with each other. The Delaunay triangulation of a set of points will connect the points that can converse with each other without the awkwardness of having to talk past another person or through another conversation.

posted by Jpfed at 6:15 AM on May 9 [2 favorites]

Nice explanation, gkhan. But

This cannot be true. Counterexample: the corners of a square.

posted by Jpfed at 6:17 AM on May 9

*As it turns out, for any given set of non-collinear points, there's only one way to do this (in other words, the Delaunay triangulation is unique).*This cannot be true. Counterexample: the corners of a square.

posted by Jpfed at 6:17 AM on May 9

*I like the one of world capitals.*

Europe is, interestingly, mostly preserved.

posted by So You're Saying These Are Pants? at 6:19 AM on May 9

The big winners seem to be Iceland (which gets Greenland and chunks of Canada), Japan (which gets the east of Alaska and Russian Far East) and North Korea (which gets northeastern China and the bits of the Russian Far East just west of Japan's). Also, Mongolia and Kazakhstan get chunks of the Arctic, largely due to Russia being lopsided. Russia doesn't have much luck in the West either, with Finland and the Baltic states taking parts of its territory.

posted by acb at 7:02 AM on May 9

posted by acb at 7:02 AM on May 9

I had no idea these things existed at all, and the math is kind of "What? Me left brain!" but this is totally cool.

posted by feckless fecal fear mongering at 8:21 AM on May 9

posted by feckless fecal fear mongering at 8:21 AM on May 9

Too freaky. I just imagined such a map over the last few days, due to weird flight costs. I wanted distance to be replaced though, by ticket prices.

posted by Goofyy at 10:26 AM on May 9

posted by Goofyy at 10:26 AM on May 9

*The map has 4 (Pretoria, Johannesburg, Bloemfontein, and Cape Town)*

Weird, must be a mistake in the dataset. Joburg isn't a capital of South Africa.

posted by Lemurrhea at 10:56 AM on May 9

I really like that, according to the capital visualization, most of the UP still belongs to Michigan and not Wisconsin.

posted by ChuraChura at 11:44 AM on May 9 [1 favorite]

posted by ChuraChura at 11:44 AM on May 9 [1 favorite]

"

Thanks! Drawing that out and then using a highlighter to select shortest lines really brought that home for me. I'm still not sure how that relates to the circumcircles, and the voronois make intuitive sense, but I feel like I've got a better handle on what the triangles are and how they function.

Thanks again.

posted by klangklangston at 12:03 PM on May 9

*klang- a couple people have talked about voronoi diagrams but not given much love to Delaunay triangulations, so I'll talk a little about them.*

There's actually a really easy way to imagine how they work. Imagine a bunch of points on the plane. Now, connect every point to every other point with a line segment. Notice that with any set of points with more than 4 points in it, some of those lines will intersect. For each intersection, we're going to choose a single line segment participating in that intersection that we want to keep and delete the rest. The segment we want to keep should be the shortest (in case of ties, just pick one randomly, it's all good)."There's actually a really easy way to imagine how they work. Imagine a bunch of points on the plane. Now, connect every point to every other point with a line segment. Notice that with any set of points with more than 4 points in it, some of those lines will intersect. For each intersection, we're going to choose a single line segment participating in that intersection that we want to keep and delete the rest. The segment we want to keep should be the shortest (in case of ties, just pick one randomly, it's all good).

Thanks! Drawing that out and then using a highlighter to select shortest lines really brought that home for me. I'm still not sure how that relates to the circumcircles, and the voronois make intuitive sense, but I feel like I've got a better handle on what the triangles are and how they function.

Thanks again.

posted by klangklangston at 12:03 PM on May 9

psoas: "

I shared this map with my dad, who is a transportation nut. He agrees that it seems kind of arbitrary. Significant regional airports are omitted, while there are a few airports included that to his knowledge don't accept commercial traffic. It's a bit of a weird list. (But fun to look at!)

posted by ocherdraco at 9:10 AM on May 10

*OK, I'll say it: seems kind of arbitrary in which airports are included? This is going to be meaningless to most people reading this, but: Modesto but not Stockton?*"I shared this map with my dad, who is a transportation nut. He agrees that it seems kind of arbitrary. Significant regional airports are omitted, while there are a few airports included that to his knowledge don't accept commercial traffic. It's a bit of a weird list. (But fun to look at!)

posted by ocherdraco at 9:10 AM on May 10

AFAIU, regular grids like rectangular and hexagonal grids are special cases of Voronoi diagrams. Or to put it another way, Voronoi diagrams are one sort of generalization of the aforementioned. One way I explain myself why I find Voronoi diagrams pretty is that 'they are just

posted by Anything at 9:18 PM on May 10 [1 favorite]

*liberated grids*'.posted by Anything at 9:18 PM on May 10 [1 favorite]

Speaking of hexagonal grids & Voronoi diagrams, check out the photo at the top of this NYT article: "Satellite Firm to Release Data on Missing Malaysian Jet" (imgur)

The caption doesn't explain what it is, but my guess is that it's a projection of the coverage areas of an Inmarsat-4 satellite's approx. 200 narrow spot beams.

posted by jjwiseman at 3:42 PM on May 21 [2 favorites]

The caption doesn't explain what it is, but my guess is that it's a projection of the coverage areas of an Inmarsat-4 satellite's approx. 200 narrow spot beams.

posted by jjwiseman at 3:42 PM on May 21 [2 favorites]

« Older you do not control a machine you embody a bird | I AM FEELING IT TODAY! HIGH-FIVE! Newer »

This thread has been archived and is closed to new comments

Also, you can do this stuff in JavaScript now? Hellloooo, JavaScript grid generator...

posted by indubitable at 3:27 PM on May 8 [2 favorites]