MHB What Type of Math is Used in Fortune's Algorithm?

  • Thread starter Thread starter RidiculousName
  • Start date Start date
  • Tags Tags
    Algorithm Type
Click For Summary
Fortune's Algorithm is recognized as one of the fastest methods for generating Voronoi diagrams, which are essential in procedural generation. To understand this algorithm, familiarity with computational geometry is crucial. Key mathematical concepts include geometry, algorithms, and possibly some aspects of calculus. Exploring the sweep line algorithm can provide foundational knowledge that aids in grasping how Voronoi diagrams are constructed. Additionally, attempting to create a simple algorithm based on visual examples, such as those found in GIFs on Wikipedia, can enhance understanding and practical skills in this area.
RidiculousName
Messages
28
Reaction score
0
I've heard that Fortune's Algorithm is the fastest algorithm yet found to generate a voronoi diagram. I am far from being able to understand it, but I got interested in it because I want to learn about procedural generation. My question is, what sort of mathematics would I have to be familiar with to understand it?

In case you are unfamiliar with it, there is a pseudocode version here.
I can't copy/paste it because it has unusual characters that don't seem to translate on this forum.
 
Technology news on Phys.org
You could look into the sweep line algorithm first, and then go back to how the diagram is generated. This algorithms hail from the realm of "computational geometry". It might be useful to look at a text on this topic.

Another thing I would try to do is just try come up with an algorithm yourself from looking at the gif in the wiki page.
 

Thread 'For those who ask: "What programming language should I learn?"'

Learn If you want to write code for Python Machine learning, AI Statistics/data analysis Scientific research Web application servers Some microcontrollers JavaScript/Node JS/TypeScript Web sites Web application servers C# Games (Unity) Consumer applications (Windows) Business applications C++ Games (Unreal Engine) Operating systems, device drivers Microcontrollers/embedded systems Consumer applications (Linux) Some more tips: Do not learn C++ (or any other dialect of C) as a...
View full post »

Similar threads

Searching for unusual characters in a Word document
  • · Replies 2 ·
Replies
2
Views
2K
What are the different types of memory used for data entry?
  • · Replies 5 ·
Replies
5
Views
1K
WaveGrid - Non-equilibrium Emergence Sandbox
  • · Replies 1 ·
Replies
1
Views
2K
Help in Explaining POSIT algorithm (3D maths)
  • · Replies 6 ·
Replies
6
Views
8K
Mathematica How to type mathematical equations using LaTeX
  • · Replies 3 ·
Replies
3
Views
2K
High School Understanding Spacetime Diagrams from "Reality is not What it Seems
  • · Replies 6 ·
Replies
6
Views
2K
What types of illness would be allowed on a generation ship and why?
  • · Replies 8 ·
Replies
8
Views
3K
Programs How good is this applied math program?
  • · Replies 13 ·
Replies
13
Views
3K
Converting Simulink model to C code, integration
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Request for Input: 2D Minkowski Spacetime Diagram Generator
  • · Replies 6 ·
Replies
6
Views
3K