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

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 !

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

January 17th, 2013