koobas.hobune.stream
Help with Delaunay Triangulation using specific library
So I'm still a bit of an amateur when it comes to C#, and I recognize that this is a bit of a broad question not entirely related to Unity, but I was hoping someone would be kind enough to spare me the time to help anyway...
So. I'm currently trying to work on random dungeon generation, using a method some of you may have heard of before using randomly positioned adjacent (but not overlapping) cubes, where one of the steps involves creating a graph between hub rooms using Delaunay Triangulation.
However, I'm honestly really stuck. I'm using the Delaunator-Sharp library, and I can't for the life of me figure out how to go about using it. It's been imported and I'm including it in my C#/.cs file, but I'm unsure how to go about generating the data from my array of points. I've also looked at the page with the Java documentation, and despite knowing Java better than C#, I still find myself stuck.
I did also ask a friend about this, but unfortunately they're a bit too busy to help.
Can anyone give me a hand?
Thanks.
After a brief glance through the code, it looks like what you need to do is make an array of Points, so if for example you currently have an array of positions you will need to go through and create their corresponding Point objects
using DelaunatorSharp;
Vector3[] positions;
void MakeDelaunay(){
Point[] points = new Point[positions.Length];
for(int i = 0; i < points.Length; i++){
points[i] = new Point(positions[i].x, positions[i].y);
}
.....
Then you just need to take that point array and create a new Delaunator
Delaunator dn = new Delaunator(points);
Which looks like it goes and calculates all of your triangles, edges, ect. Then you can use the public methods inside of Delaunator to access the calculated data, for example:
foreach(Triangle t in dn.GetTriangles()){
....
}
Thank you very much! One extra question if you don't $$anonymous$$d, slightly related:
If I've understood correctly, I need to now convert this to a graph for generating a $$anonymous$$imum spanning tree. Is this true, and if so what should I read to go about that? I did some googling, but found something related to networks that seems to be unrelated to my usecase. I know about Kruskal's algorithm which should be easy enough to figure out, but it's the graph bit that's stumping me, since it doesn't seem to be entirely clear...
Its been a while since I knew what a $$anonymous$$imum spanning tree or Kruskal's algorithm are, but if you just need a graph representation then you should have all that information ready to go, since a graph is just a set of vertices and edges between vertices. You can call GetEdges from your Delaunator object to get the set of edges, and the vertices should just be the points that you fed into the constructor.
(Whoops, deleted my response...) Neat, thanks! For context, Kruskal's algorithm is just a way of generating a $$anonymous$$imum spanning tree. Which takes a graph representation and removes all unnecessary edges. There's definitely a better and more complex explanation, which I have no idea how to write, so I'll just send an image to better demonstrate: https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/1200px-Minimum_spanning_tree.svg.png
