next »

[Thomas Hiatt]

I'm messing around with voronoi diagrams and I'm trying to implement fortune's algorithm. I have started by taking this https://www.cs.hmc.edu/~mbrubeck/voronoi.html code and adapting it to work with my rendering system and it seems to produce correct results, but it seems to me that the intersection function is incorrect. I have worked several equations out algebraically trying to understand the code but I get a different a, b, and c than his code. For example, using a focus of (2, 2) and directrix of (x = 3) I end up with x = -0.5y^2 + 2.5y - 1.25 but the equation that function comes up with is -0.5y^2 + 2y + 0.5 I'm not super confident in my math abilities but I really want to understand the algorithm and I just can't see how that function makes sense. Can anyone better than me at math tell me if that function really is wrong or if it's me thats wrong?

[Thomas Hiatt]

I guess I already figured out what I was doing wrong. I was subtracting from the wrong coordinate to find my vertex. Now I get the same result as the code and I should be able to understand the formula that it uses.

[oahda]

Any pointers to good tutorials on Voronoi diagrams and related algorithms? I tried to find some just the other day but they weren't really clear enough to me.

Good C++ and C# libraries that can do it for me (including the Delaunay triangulation data) would be interesting to know about too, but I want to really understand it myself well enough to implement my own algorithm as well.

Doesn't have to be Fortune's algorithm. I think I'd rather prefer to understand the less optimised, but easier to understand, algorithms first.

[Thomas Hiatt]

I started out by watching this

video. From that I was able to write a brute force algorithm that created lines between a cell and all the other cells then intersecting them to find the edges for that cell. If you store a pointer to the cell on each side of the edges then you can connect those at the end for the Delaunay triangulation. I don't know anything about libraries that do this stuff because I'm only interested in understanding and implementing it myself.

[oahda]

Already watched those, but unfortunately not informative enough. Thanks anyway. I'll keep looking for something that works for me.

[Cheesegrater]

The book 'Computational Geometry in C' by Joseph O'Rourke has a chapter on Voronoi diagrams and various algorithms that pertain to them. Good info, but it is written in a math textbook style, not 'informal internet tutorial' style.

[BorisTheBrave]

I read this recently: http://rykap.com/graphics/skew/2016/02/25/voronoi-diagrams/

It's actually only approximate Voronoi, but it's cool to see a GPU implementation.