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.
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, 2011Hey 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, 2011I’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, 2012Hello, 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, 2012Wow that’s awesome! But I am wondering if there’s any implantation of voronoi diagram of higher order in C++
October 1st, 2012i’m wondering how to find a nearest neighbor to a random point?
December 4th, 2012Nice 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
January 17th, 2013http://en.wikipedia.org/wiki/Nearest_neighbor_search
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, 2013Hello,
it is totally OK, I am offering all my public code under MIT licence.
February 4th, 2013