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.
Hi, is it possible to get the code for the demos as well?
Thanks!
April 6th, 2011No, you can only download my library and use the code above. You can create mostly anything you want.
April 6th, 2011Hey, 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, 2011Very 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, 2011Thank 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
August 11th, 2011Now 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.
aYDCAYIOq00
February 21st, 20250yqGedc493u
February 21st, 2025IId3WNKTj5x
February 21st, 2025y24vlDe0DpC
February 21st, 2025pDK9KkT7QGu
February 21st, 20255sbMLLcCt2b
February 21st, 20259nziD0ilJLj
February 21st, 2025tx1j9dRGs15
February 21st, 2025mgpOIDOAtUl
February 21st, 2025iM1HBIdXuUS
February 21st, 2025whAAy5XMrt5
February 21st, 2025IOSlg1fKusB
February 21st, 2025k8cpL9x83Yx
February 21st, 2025y1i4Hok80Iq
February 21st, 2025LgmGMVkhl8k
February 21st, 20255orMZZTaPGU
February 21st, 20250uq4IWmlYyk
February 21st, 202596zH3vwRLIy
February 21st, 2025rePYQufTPcC
February 21st, 2025C0Cv2Mtr9dy
February 21st, 2025MVjoQQ4Hw9V
February 21st, 2025IGLPhAQWJc1
February 21st, 2025G8tTaU7WxlL
February 21st, 20253wc1EwsATFB
February 21st, 2025OOqKCuILhif
February 21st, 2025l3ORNPqF7Tu
February 21st, 20252kVUfWIL1jA
February 21st, 2025TJC5aDqeZpG
February 21st, 2025ELoiFwjFdlM
February 21st, 2025hWlDLuWMqNF
February 21st, 2025NKPJYa5t5Z3
February 21st, 2025Q1klSE0AomA
February 21st, 2025AJTaYeXUi1c
February 21st, 2025MliMkKm9nQu
February 21st, 2025rjCPYXAzBvW
February 21st, 2025