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.

4 komentářů:

  1. Anonymní ... (22. března 2011 5:36)

    Ahoj, vidim ze sa celkom dost zaoberas grafmi. Ja take. Ako by si principialne riesil toto [http://lab.php5.cz/jak-na-planarny-graf.png]. Mam graf nakresleny rucne/mysou ale ten moze obsahovat vela priesecnikov. Chem ho zjednodusit a to tak ze premiestnim (najlepsie minimalny pocet) vrcholy aby tych priesecnikov bolo co najmenej, idealne ziadny - teda dostavam planarny graf. To samozrejme nemusi ist vzdy. Vdaka.

  2. Ivan ... (24. března 2011 16:44)

    Ahoj, tady jsem něco vygooglil ohledně tohoto tématu
    T A D Y
    je tu i implementace v C++
    T A D Y

  3. Anonymní ... (25. března 2011 9:43)

    Diky aj za C++, pozriem. I kde knih s teoriou mam viac, aj zostudovane.

  4. Anonymní ... (28. března 2011 7:24)

    Tak som sa do toho pustil, vyzera to nadejne. Diky este raz.

Okomentovat