SOS

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 http://mbostock.github.com/d3/ex/voronoi.html

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?

    sbell@morganmckinley.ie

  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.

    http://imgur.com/a/rWhOH

    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:

WordPress.com Logo

You are commenting using your WordPress.com 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

 
Follow

Get every new post delivered to your Inbox.

Join 535 other followers

%d bloggers like this: