Delaunay triangulation help

At the moment, i am attempting Delaunay triangulation. I’ve wrote up a function to calculate circumcenter and circumcircle, but i’m stuck now; how do I know which points to include in a circumcircle? At the moment, I generate 100 dots on a plane at random. The purpose is to create paths between stars (Like hyperlanes in Stellaris, see image) but the wikipedia page isn’t really helping. Any help is well appreciated.

3 Likes

I am not an expert in this so did a google search for a solution in lua and there are a number of hits one of which is in github so maybe one of those will help you.

1 Like

This is all too confusing… I’ll just find another method to doing this.

I’ve done the exact same thing you were describing while trying to create a strategy game. If you’re willing to use an incremental algorithm, you can run the Bowyer-Watson algorithm on your list of points. With this algorithm, you’ll know which points to include in your circumcircle because you’ll be updating a list of triangles (you can write a simple Polygon class if you want to store the vertices and edges) representing the current triangulation of the map in each step.

Algorithm Pseudocode

1 Like

I suggest you look into doing the Divide and conquer algorithm for Delaunay triangulation. I believe it is the easiest, and I have done this before in Roblox, and so has EgoMoose. I believe he has a open source code for this.

1 Like

Ill try that and the DAC @KinqAndi was talking about. Thanks for the help.

1 Like

Do you have a link to EgoMoose’s source code? I’m trying to implement procedural dungeon generation using DT, MST, and A-Star algorithms.

Closest thing I’ve seen is their implementation of a different triangulation algorithm

3 Likes