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.
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.
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.
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.
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