A good, reliable and performant Voronoi implementation

[gestaltist]

Hi everyone.

I have been looking for quite a while to find a good Lua implementation of the Voronoi diagram. (For those who don’t know - look it up on Wikipedia - it’s very useful for creating maps.)

The libraries I was able to find have proven unsatisfactory: iVoronoi is buggy and others were doing the Delaunay triangulation and I would have to compute the Voronoi diagram from that.

I finally found a great thread on the topic which presented a Voronoi implementation for the Corona SDK:
http://forums.coronalabs.com/topic/1947 ... eneration/

I decided to reimplement it so it can be used with Love (or with anything for that matter).
You use it like this:

Code: Select all

voronoi = require”voronoi”

and then:

Code: Select all

vertex, segments = voronoi(list_of_points)

(I.e., you feed the function a list of point coordinates and it returns a list of vertices and segments of the Voronoi diagram.)

vertex, segments and list_of_points are lists of points in the form {x=x; y=y}. Points in the list_of_points have additional fields “dx” and “dy” so you can move them around but you can easily edit this away for simplicity.

The attached love file implements the demo found in the original thread where the points keep moving and are recalculated on the fly - which shows how well-performing this algorithm is.

voronoi-demo.love

(4.76 KiB) Downloaded 470 times

BTW:
There have been two related threads on this forum:
http://www.love2d.org/forums/viewtopic. ... noi#p74268 - gives a nice demo of a Voronoi diagram but it uses a simplistic method to derive the diagram and the performance plummets for as low amounts of points as a few hundred. The implementation I have used remains usable for even 100,000 points on my machine.

The other thread:
http://www.love2d.org/forums/viewtopic. ... noi#p40235 - I only found it now and it is based on the same algorithm I used but I couldn’t get it to work in the current form, and it also uses Love-specific drawing commands in the voronoi file directly - with my version, you can do the calculations separately from displaying them.

I hope you find this useful.

Edit. Adding a screenshot:

Zrzut ekranu 2014-07-16 o 13.18.28.png (123.46 KiB) Viewed 9041 times

[bdjnk]

This is an amazing library. I read the Wikipedia article, and was thrilled by the possibilities. Excellent work.

p.s. It was probably left in by accident, but voronoi.run should not be drawing points (or anything).

p.p.s I would also move movement out of voronoi.run to make movement more flexible.

[gestaltist]

Good catch bdjnk! I totally forgot to move that one bit to main.lua. I also agree with the movement part. I simply got excited and wanted to share this ASAP.

I’ll update the library and repost it here later today if I find the time.

[gestaltist]

OK, I have updated the thing to not rely on point movement and to separate the drawing from the library.

The returned function can now optionally accept the borders of the bounding box.

Enjoy.

voronoi-demo2.love

(4.83 KiB) Downloaded 376 times

[bdjnk]

So I'm back, and I have a couple questions.

Occasionally this will happen:

voronoi bug.png (26.65 KiB) Viewed 8935 times

Are these errant lines the result of points in the same location, or is something else going wrong?

Also, is there any simple way to get the vertices associated with a given point? More specifically, I'm thinking use those vertices to draw a polygon for each point's area.

[gestaltist]

Hi bdjnk.

First off: As you know, I am not an author of this algorithm. I just found a good one on the web and decided to adapt it and share it. So take my answers with a grain of salt. I will surely dig deeper into it as I go along.

Regarding the errant lines - they are only happening in the demo, at least for me. I think this is a result of the quickly mutating state but I haven’t given it much thought as I only need static diagrams. If you remove point movement and still encounter this error, please let me know. I don’t think that this error is otherwise worth troubleshooting, as you wouldn’t be mutating the state like that in any real-life situation.

The answer to the second question is: no, currently there isn’t an easy way to do it. I would have to play around with the algorithm to add this. I can see how this could be useful. There actually is a single place where the vertex is being updated so I think it shouldn’t been to hard. As I don’t have that much free time on my hands, feel free to try and add this option yourself. I will gladly integrate it.

[Roland_Yonaba]

Just dropping in to say 'nice job'.
I have always wanted to write my own Voronoi diagram implementation, for the sake of understanding (and I probably will, when I fond some time). I took a quick peek at this, and it is quite clean. Nice job. The demo is beautiful, too.

[gestaltist]

Thanks for the nice words.

I was thinking about the fact that this library only gives you a list of vertices and lines. I would like to add a way to detect polygons and relate them to the original points, as per bdjnk’s suggestion. Maybe someone more experienced would have a suggestion on how best to do this? I was thinking to integrate something like this:
https://github.com/vrld/HardonCollider/ ... olygon.lua

[rexjericho]

Hey, your implementation demo looks cool and runs very fast!

I think the flickering lines may be caused by collinear vertices. The algorithm does not seem to be reporting collinear vertices when it should (maybe line 275 in voronoi.lua). I tried to force a bunch of collinear points and this is what I got:


I noticed in the run demo that when vertices go out of range their position is set to the boundary edge. If three or more points cross the boundary in the same frame, their x or y coordinate will all become the same, creating a collinear set of vertices. This might be why the flickering lines only show up rarely in the running demo.

[DaedalusYoung]

Looks good, very useful.

As for the weird lines, don't know if this is related, but I've noticed love.graphics.polygon, in line drawing mode, sometimes draws strange lines when angles become narrow. If you're using polygons to draw the cells, that may contribute. You should try to see what happens when you change it to draw polygons in fill mode.