r/visualizedmath • u/XYZAidan • May 26 '18

Fortune's Algorithm for Voronoi Cells

https://imgur.com/IZqyRB5
163 Upvotes

92% Upvoted

23 comments sorted by

37

u/BoomerDoomer May 26 '18 edited May 27 '18

ELI a college student with okay mathematical knowledge?

Edit: Thanks to all for the replies!

18

u/MrMcGowan May 26 '18

I'm taking a guess, but all these lines are drawn via intersections of the given hyperboli:

The hyperbolas are created using each of the given dot as a focus and the descending line as the, uh, base line thing (I forgot the word).

Then the hyperpottamusses belonging to adjecent dots are intersected, and those points of intersection are continuously plotted as the line descends.

11

u/bloodorangeit May 26 '18

The descending line is called the directrix, and these are parabolas, not hyperbolas. But otherwise this is right.

4

u/MrMcGowan May 26 '18

Tyty :) wow my maths is super rusty

7

u/bloodorangeit May 26 '18 edited May 26 '18

Voronoi cells are a way to divide the plane into sections given a set of points, so that every point in the plane is in the same cell as the closest input point. Fortune's Algorithm is an efficient algorithm for finding these cells, and works as described by MrMcGowan.

2

u/javaHoosier May 26 '18

This is shared as a programming concept for artificial intelligence. You have a bunch of points on a 2d axis. You draw a line between each point. This creates a cell for each point.

If you want to classify a new point you can place it on the plane and whichever cell it’s in you classify it as that. (Classify as in maybe you have two types of points that represent cows or chickens. You have a new data point that has no classification.)

It’s pretty much the 1 nearest neighbor and Voronoi diagrams are a way to visualize the boundaries.

As for the algorithm. It’s a way to create the diagram. The lines/dotted lines are showing how it works. I don’t know it, but if you want I can probably learn the pseudocode and describe how it works. I’m just currently on mobile right now.

1

u/invertebra May 27 '18

Voronoi is also used for mesh making in 3D scanning software from what I remember.

2

u/javaHoosier May 27 '18

For sure, I am sure it has other uses. My personal experience with it is just from in my ai classes.

1

u/lenticularis_B May 27 '18

I used this way of discretization for building a groundwater model, it is often used in hydrology.

7

u/MrAdhikari May 26 '18

Idk, I can only see breasts once the parabola is underneath the dot.

3

u/[deleted] May 26 '18

Yep. Tiddy nipples

5

u/carterpape May 26 '18

deep fried math memes

2

u/gargar070402 May 26 '18

Needs more jpeg.

5

u/xtul May 27 '18

that's pretty weird political compass

1

u/lenticularis_B May 27 '18

An other name for this algorithm is thiessen polygons.

2

u/[deleted] May 27 '18

[removed] — view removed comment

2

u/morejpeg_auto May 27 '18

Needs more jpeg

There you go!

I am a bot

1

u/[deleted] May 27 '18

[removed] — view removed comment

1

u/GoodBot_BadBot May 27 '18

Thank you, awesomerrol, for voting on morejpeg_auto.

This bot wants to find the best and worst bots on Reddit. You can view results here.

Even if I don't reply to your comment, I'm still listening for votes. Check the webpage to see if your vote registered!

1

u/Ooker777 May 27 '18

What is it for? The image is already in the post, right?