koobas.hobune.stream
C# - Simple Voronoi/Delaunay Diagrams For Starters
Hi,
I would like to use voronoi and delaunay diagrams for the generation of different road network types. So far, I haven't found a package offering both adapted for unity. I know there are a couple of huge packages containing all sorts of algorithms, there are smaller ones that don't yield the desired results or simply don't work in unity and some that are only used for terrain manipulation. However I need one I can feed with a list of points or something similar, which then outputs a list of edges and vertices I can connect easily.
Is there a small package for starters I can use right off the bat or with little modification?
trying typing "Delaunay" in to the search field here for many leads
http://answers.unity3d.com/questions/307544/mesh-from-vertices-polygon-from-spline.html
I would if the answer was actually helpful. It is not like I haven't used the search field, but that the search query in no case returned something I could use. Therefore I am still searching for a working algorithm or one that can be easily modified.
It doesn't need to be all fancy and contain a hundred other algorithms I could use at some point in development. Only a working voronoi and delaunay diagram generation algorithm is required to fit my needs. But this algorithm needs to be spot on.
Bottom line: I am still doing research on this matter.
if you click on the link in the comment, someone has provided full code for the desired or very close algorithm. hope it helps. here is the link again
http://answers.unity3d.com/questions/307544/mesh-from-vertices-polygon-from-spline.html
This is old but for anyone else looking, here's the Fortune Voronoi Graph algorithm implemented in C#
http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C
With a little fenangling, I was able to convert this to a Unity-friendly version and build a mesh from it :D
Do you $$anonymous$$d sharing your code with us?
This is really old now but is still unanswered (I had the same problem as OP_toss when I tried using the C# implementation here).
I just finished porting one of the best AS3 implementations of Fortune's algorithm to C# for Unity. You can get it here: https://github.com/jceipek/Unity-delaunay (MIT licensed).
It's probably not perfect, but it doesn't seem to suffer from the same verts at infinity problems that seem to exist in every other version I tried: 
Seems like a few people were wanting to write up a new delaunay implementation at the same time. Frit wrote one up too a week or two ago. I was writing one up too.
https://github.com/PouletFrit/csDelaunay
I've gotten almost all of AmitP's graphing rewritten. http://tinyurl.com/q5s6ub8
I'd rather create a mesh out of this data ins$$anonymous$$d of just drawing screen lines or texture lines. But I'm not sure how to go about that. Creating a mesh out of the delaunay triangles should be trivial. But how do you represent the voronoi polygons?
Thank you for your effort in this matter. I really appreciate it!
$$anonymous$$eshire, I'm pretty sure my port lets you get the verts of each polygon. From there, you can delaunay triangulate each polygon. If you need a continuous mesh of all polygons, just merge overlapping points. Sorry I can't be more help right now - answering from my phone because I can't get online.
Hey jceipek,
is there a way to generate a list of nodes that have a reference to their respective neighbors with your library?
as3delaunay works. well sometimes. I got Unity freeze in 20% cases. 30% more cases I got:
/** Something has gone badly wrong */ Debug.LogError("$$anonymous$$ajor error: was trying to close the loop of an outer Cell, but couldn't find a restart point");
also is there a way to fill corners too. because this implementation seems to cut all the corners. I mean points [0,0], [0,height], [width,0] and [width,height]. here's how it looks http://pix.academ.org/img/2015/01/29/3eedbc33f1e3f49675b25479667f427e.png
meshes http://pix.academ.org/img/2015/01/28/640x480_8585791640386f9297265e1ee05fb225.png
jceipek, in other words - if I connect vertices, and create meshes from them, corners will never be inside.
For 2017...
I had a look around, and really
https://github.com/jceipek/Unity-delaunay
seems to be the best one out there, still ! Thanks, jceipek !
