Forum

Voronoi / Delaunay

Hi,

I’m trying to implement a Voronoi C# Node, doing my first steps at the moment. Could it be that it is possible to get with Delaunay and some basic Math the same results like Voronoi? According to this link (“The Voronoi Diagram is built on-the-fly from the Delaunay Triangulation”) it should be possible to get a voronoi graph from a delaunay triangulation. … hmm but I don’t get it!

sorry i can’t help you, but i just want to say that would be great to have a voronoi node in vvvv, really hope someone will make it…

yeah I’m working on it. found a c# implementation of voronoi here but first have to get all the dependencies of this bit of code. could take a while I’m little busy at the moment - but hope to come around the corner with a working version next 1 or 2 weeks. maybe some of the meso guys who coded the delaunay node could answer my question above?! and maybe I even could look at the delaunay code - that would be super nice (joreg?gregsn?)

ok, best would be to check google before asking lame questions ;) (-> how to convert delaunay to voronoi)

maybe you can somehow use the fact that a voronoi diagram is (mathematically) the dual graph to a delaunay triangulation? (maybe using this there’s a quick way to invert the delaunay into a voronoi diag)

also, voronoi diags are used in solis state physics (see also wigner-seitz cells), so there should already be a number of algorithms out there.

primarily i think creating it from the delaunay would be best because you could use existing code, and maybe the delaunay node could then get a toggle to switch between delaunay and voronoi? (cf. period/velocity-based LFO…) although, then it would have to be renamed… Delaunoi or Voronay maybe? :-P

jep I’m also checking that fact. reading some documents at the moment about using the same codebase for them booth/converting delaunay to voronoi. … hope to get that all - I’m more a designer than a coder (expect for php)

nice! i thought of something like this, too. looking forward to your first results.
i focus myself on a Delaunay (2d) helppatch then :)

edit:
cool, linking to the node reference just brought me one.
so what now? writing diploma? :/

I have a lot to do at the moment so I don’t think I’m ready with the node before end of the next week. hopefully thats ok for you?!
Ah and the next thing would be to implement a 3d version, which would be the next step … maybe that would be a interesting task for you.

best andreas

something new on the voronoi front out there? i’d really like to play around with it :)

I’m sorry, I have had to freeze the development because I’m very short of time at the moment. maybe I will find some time to finish the plugin this weekend.

best m9d

you know, i often wish that this forum had a structure more accomodating a search/forum functionality…
if i didn’t by accident stumble over this thread again i would have totally forgotten it…

it would be really nice if the forum would let you subscribe to a thread, which seems fairly standard nowadays. bookmarking all threads and checking from time to time can’t be a solution…
:-(
also, a more intelligent search function…
ah, why…maybe i am just to dumb or demanding [rant over](rant over)

voronoi?.. no text …

Found another implementation here,

Voronoi c#

I Like this one as it has only vectors as input/output, so it should be easy to encapsulate in a Plugin.

This version would welcome some cleanup/optimization (was made in .NET 1.1, so using generics would help, and splitting all code in one class per file would be better), but seems to work out of the box so a version with it would be fine as well.

While waiting for better version, posted the one from the code I found:

Voronoi Plugin

Have fun

http://vvvv.org/tiki-browse_image.php?galleryId=11&imageId=6025

yay!
how fast is it?
recently, i found two papers containing maybe viable approaches (maybe per shader):
http://www.comp.nus.edu.sg/~tants/jfa.html


unfortunately, i didn’t have time to develop anything… :-(

@bilderbuchi

I run a voronoi with 2 randomspreads of 500 each with no performance impact (using gdi for rendering).

Starts to go slower at around 700 by 700, but might be a bit due to display as well.

By optimizing the code I found (eg removing his vector class and replacing by the vvvv vector2d implementation, and using some generics for lists), we can definitely improve that)