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.