Sweep line Voronoi algorithm in JavaScript
Posted by Shane O'Sullivan on March 22, 2011
Years ago I translated Steven Fortune’s sweep line Voronoi algorithm to C++, and have been meaning to make a JavaScript version for some time, but never got around to it.
Now, someone has actually done it with the D3 charting library, and it’s fantastic. Check it out at http://mbostock.github.com/d3/ex/voronoi.html
Steve said
Hi, I am recruiting for a Senior DOJO Developer for a daily rate contract in Belfast, can you recommend anyone that might be interested in this?
sbell@morganmckinley.ie
Shane O'Sullivan said
Sorry no, the only Dojo developers I know in Ireland are fully employed
Joey Gentry said
Hello Shane,
I have been trying to use your code for generating a Voronoi Diagram the past couple days. I got it working without much issue but I do have a strange issue that I can’t figure out. I have some screenshots below if you wouldn’t mind taking a look. The first uses 10000 points, the second is 5000 and the first is using 1000 points. It seems the more points I have the more stray lines I get. These lines seem to stretch across the entire diagram and are not pretty, At first I thought it was my line drawing lib but it turns out it isn’t. I tried using this in a windows forms app and in a xna app and both draw exactly the same lines.
Do you have any ideas what would cause this? I am literally just iterating through the edges your code creates and drawing the lines.
http://imgur.com/a/rWhOH
Thank you.
Shane O'Sullivan said
Hi Joey,
I think this can happen if you have two identical points. You should try filtering them out before passing them to the Voronoi algorithm
Shane
Joey Gentry said
Ahh perfect. Thank you. For some reason I just assumed that it wouldn’t very very likely to have 2 points. Well my mistake. Thank you very much.
Joey Gentry said
I have one more question. This one may sound odd.
Lets say I want to generate a very large diagram. Lets say 10,000,000 points. Now I don’t need the entire thing in memory but I could save it to disk. As a test I ran this on your code and it actually crashes from running out or memory (gets to like 2gb and blows up). Now does this sound like that should be a problem? If so what would be the best way to generate a huge “map” or voronoi diagram. I am going to use this in a game in lieu of a tile based system.
Shane O'Sullivan said
Given that the sweep line algorithm uses quite a bit of memory, you’d have to reduce the dimensionality of the problem, perhaps by grouping a number of nearby points together. Alternatively you could divide the map into segments and somehow join them together later, though this could be tricky.
Joey Gentry said
I was thinking about the join thing. Should it work fine if I were to know the out points then make sure those are part of the following generation? The results should tile correctly right?