Voronoi diagram in AS3

In today's article I will introduce you my own small library for generating Voroni diagram in ActionScript 3. I used Fortune's algorithm, which is probably the fastest algorithm for solving Voronoi diagram.

Voronoi library

I put the whole code in a small package "net.ivank.voronoi". I just couldn't find any working implementation of Priority Queue or Heap in AS3, so I used a simple array. That's why the final complexity is $O(n^2 * log(n))$, but it is still usable for small diagrams. You can download my whole code HERE.

Example

import net.ivank.voronoi.*;       // importing libraries
import flash.geom.Point;

var i:int;
var edges:Vector.< VEdge >;       // vector for edges
var v:Voronoi = new Voronoi();    // this instance will compute the diagram
// vector for sites, for which we compute a diagram
var vertices:Vector.< Point> = new Vector.< Point >();

// let's add some random sites
for(i = 0; i< 20; i++)
{
   var p = new Point(Math.random() * 1000 , Math.random() * 800)
   vertices.push(p);
}
// call a method which computes a diagram, width and height limit
edges = v.GetEdges(vertices, 1000, 800);

// drawing a Delaunay triangulation
graphics.lineStyle(3, 0x888888);
for(i = 0; i< edges.length; i++)
{
   graphics.moveTo(edges[i].left .x, edges[i].left .y);
   graphics.lineTo(edges[i].right.x, edges[i].right.y);
}

// drawing a Voronoi diagram
graphics.lineStyle(5, 0x000000);
for(i = 0; i< edges.length; i++)
{
   graphics.moveTo(edges[i].start.x, edges[i].start.y);
   graphics.lineTo(edges[i].end  .x, edges[i].end  .y);
}

Performance test

We can use an array or a heap to represent an event queue. Let's take a look at the speed of these two options. (diagram for 200 places, recounting on mouse move).

Array - add event: to the end of an array; remove event: remove + move the rest one field backwards; get maximum: sort + remove the last item.

Heap - adding an event, removing maximum: see definition of the heap.

Old comments (closed because of spam)

5 Comments

  1. joe kukish said:

    Hi, is it possible to get the code for the demos as well?

    Thanks!

    April 6th, 2011
  2. Ivan Kuckir said:

    No, you can only download my library and use the code above. You can create mostly anything you want.

    April 6th, 2011
  3. Simon said:

    Hey, nice work. I’ll definitely use this code.

    I found a bug though, a vertical line pops up somewhere on the map when you move a point to the very lower edge of the screen. Can you fix that?

    Keep up the good work,

    Simon

    June 23rd, 2011
  4. Brian said:

    Very nice.

    Can you tell me how to best find all the vertices of a given polygon using your code? I’d like to be able to fill them with color.

    August 11th, 2011
  5. Ivan Kuckir said:

    Thank you. It’s a very good question. When programming it, I realised, that it would be a very nice feature, but I didn’t implement it :(
    Now it will be the best to create a class Cell with the list of points, which define the polygon. Create a list of Cells under the list of Vertices. Now loop through the list of edges, check it’s left and right vertex and add their begin and end vertex to the cells, which are at the left and right.
    But then you will have to create a convex hull for each cell.
    This process will have complexity $n*log(n)$ (again). Better way is to edit current code.

    August 11th, 2011