Shane O'Sullivan's technical blog… really ties the room together

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

About these ads

9 Responses to “Sweep line Voronoi algorithm in JavaScript”

  1. 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?

  2. 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.

    Thank you.

  3. 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.

    • 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.

      • 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?

  4. Hi there! I just wanted to ask if you ever have any problems with hackers?
    My last blog (wordpress) was hacked and I ended up losing
    several weeks of hard work due to no backup. Do
    you have any methods to prevent hackers?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 533 other followers

%d bloggers like this: