• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Translating delaunay triangulation to Game maker

Rivo

7014
Hi, i'm looking for a way to translate this: https://en.wikipedia.org/wiki/Delaunay_triangulation into game maker. I have already created a voronoi generator based off random points, and now i would like to combine the two together. I'm not really an expert at game maker just yet (or any other language) and the info i find online confuses me.

so i'm looking for some help or any info at all!

All help is appreciated, thank you.
 

jo-thijs

Member
The site only gives conceptual algorithms, no pseudo code, so direct translation is not possible.
We first need to know what kind of data structures you use to represent the set of points, the result of the triangulation and/or the voronoi diagrams (I assume that's what you mean with voronoi generator).

If you've already got the voronoi diagram of your set of points, then I would personally try to use an algorithm based on that solution first.
We know the delaunay triangulation as a graph is the dual of the voronoi diagram,
in the sense that the sites of the voronoi diagram form the nodes of the delaunay triangulation
and that the voronoi-edges seperating two neighbouring voronoi-regions represent edges in the tringulation between the sites of the two neighbouring regions.

You should have the nodes of the triangulation for free, as they are the input for generating voronoi diagrams.
If you can loop through every edge of the voronoi diagram in a linear time and decide which two sites got seperated by that edge in a constant time,
then you can create the triangulation graph in linear time of the output size.

In order to be certain this works though, we need to know how you represent voronoi diagrams in GameMaker and how you want to represent delaunay triangulations.
 
Top