Voroného diagram v AS3

Jak jste možná vytušili z předchozího článku, nyní si implementujeme Fortunův algoritmus pro hledání Voroného diagramu ve flashi.

Knihovna Voronoi

Celý kód jsem zabalil do jedné knihovny, aby byla snadno přístupná. Knihovnu si stáhnete kliknutím ZDE.

Příklad použití

 
import net.ivank.voronoi.*;       // import knihoven
import flash.geom.Point;

var i:int;
var edges:Vector.< VEdge >;       // vektor, kam se uloží hrany
var v:Voronoi = new Voronoi();    // tato instance vše spočítá
// vektor bodů, pro které počítáme diagram
var vertices:Vector.< Point> = new Vector.< Point >();

// přidáme náhodné body (pouze kladné pozice)
for(i = 0; i< vnum; i++)
{
   var p = new Point(Math.random() * 1000 , Math.random() * 800)
   vertices.push(p);
}
// necháme si spočítat hrany, uvedeme rozměr diagramu
edges = v.GetEdges(vertices, 1000, 800);

// takto si nakreslíme Delaunayho triangulaci
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);
}

// takto si nakreslíme Voroného 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);
}

Test výkonu

Pro reprezentaci fronty událostí lze použít pole nebo haldu. Podívjeme se na rychlost jednotlivých možnosti (diagram pro 200 bodů, přepočítává se při pohybu myši).

Pole - přidání události: na konec pole; mazání události: vymazání + posun zbytku o políčko dozadu; výběr maxima: sort + odebrání posledního.

Halda - přidání událost, výběr maxima: dle definice haldy.