Voronoi diagram in JavaScript

I always wanted to try programming in JavaScript, so I decided to rewrite my implementation of Fortune's algorithm from C++ and ActionScript 3 into JavaScript.

What is interesting about JS

Up until now, I knew that JS is very similar to ActionScript and that it doesn't have classes and data types. It sounds a little weird, but it's true :) JS is object-oriented language, just like C++ or AS3 are, but there are no classes and data types. Instead of it, Prototype-based programming is used. It is a little hard to get used to it, but after some time it doesn't mind you, or even more, you start to like it :)

Rewriting AS3 into JS

I started my learning with an article on Wikipedia. To get some practice with JS, I decided to rewrite my library for generating Voronoi diagrams, which I already had written in AS3 and C++, into JavaScript. I was a little worried, that it will be too hard, but finally it was pretty easy, and what's more, it really worked! I had finished in about an hour.

The result

You can see the result above. I draw diagrams into HTML element "canvas". Unfortunatelly, I didn't have an implementation of a heap or priority queue in JS, so i used a classic array. Thus, asymptotic time complexity is $O(n^2)$ instead of $O(n * log(n))$, which AS3 and C++ versions have.

When you rewrite a common object-oriented imperative language into JS, it can be summarized into few steps:

  • Remove type specification in variable and function definitions
    • int a = 5; var a:int = 5; => var a = 5;
  • Rewrite the definitions of classes into function definitions. When you call this function with a "new" keyword, it works as a constructor.
  • Attach all class' methods to it's prototype.

Old comments (closed because of spam)

10 Comments

  1. shaurya said:

    Fun stuff! very elegantly implemented.
    I wish you’d make it open source.

    I wonder how you came up with the asymptotic time complexity measurements (or is there a reference out there that I can look at too?).

    Very interesting stuff, I see a lot of possibilities when expanded to haptic devices like the smartphones or iPad etc.

    Kudos!

    Shaurya

    July 31st, 2011
  2. Ivan Kuckir said:

    Hey thank you!

    My original code file is this one http://www.ivank.net/blogspot/jsVor/Voronoi.js + other files (see source code).

    When you know some algorithm, it is easy to determine it’s time complexity. In Fortune’s algorithm we have linear number of events, to get each event, we remove it from queue data structure, which can be a heap (binary tree – logarithmic time) or a simple array (linear time).

    I have written an article about it, but it’s in Czech.

    August 1st, 2011
  3. Sean Esopenko said:

    I’m working on porting your code to Python. You can see the github project at https://github.com/sesopenko/Python-Voronoi-Map

    Before I get too far I wanted to know if you’re ok with me doing this? I didn’t see any license agreements in your code. I attached an MIT agreement to the ported code. Is that ok with you?

    July 20th, 2012
  4. Ivan Kuckir said:

    Hello, I am ok with that :) But I am afraid that there are some bugs or “special cases”, which I did not treat well :(

    July 20th, 2012
  5. Hob said:

    Wow that’s awesome! But I am wondering if there’s any implantation of voronoi diagram of higher order in C++

    October 1st, 2012
  6. Peter said:

    i’m wondering how to find a nearest neighbor to a random point?

    December 4th, 2012
  7. Damien said:

    Nice stuff !

    Aswers for the comments :

    @Hob
    You might want to try CGAL : http://www.cgal.org/
    http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3_ref/Class_Delaunay_triangulation_3.html
    http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_d_ref/Class_Delaunay_d.html
    As of CGAL 4.1, the lib does not seem to have any API concerning k-dim voronoi diagrams, but it has support for k-dim delaunay triangulations, you may start from there.

    @Peter
    http://en.wikipedia.org/wiki/Nearest_neighbor_search

    January 17th, 2013
  8. Adam Gardner said:

    Like Sean, I’m using your code as the starting-off point for a Ruby implementation of the algorithm (actually, I started from the AS3 code, since it’s more similar to Ruby). Just double-checking, is that Okay, and do you have a problem with me placing an MIT-license on the code?

    Repo is at https://bitbucket.org/philomory/voronoi-pure/

    February 4th, 2013
  9. Ivan Kuckir said:

    Hello,

    it is totally OK, I am offering all my public code under MIT licence.

    February 4th, 2013
  10. Final Year Project // Research | Edward Toy said:

    [...] has been developed so that computers can draw them quickly and efficiently. Ivan Kuckir has a JavaScript implementation that can be played around with in the browser which definitely helped me understand how they [...]

    January 9th, 2014