Kreslení hezkých grafů v AS3
V tomto článku se podíváme na způsoby kreslení hezkých grafů do roviny. Použijeme fyzikální, tzv. "pružinový" algoritmus, v průběhu kterého si budeme graf vykreslovat.
Grafy a jejich nakreslení
Grafy
Klasický graf je definován množinou vrcholů (např. ${a, b, c, d}$) a množinou hran, což jsou dvojice vrcholů ($\{ \{ a,b\}, \{b,c\}, \{c,d\}, \{d,a\}\}$). Většina lidí by tento graf nakreslila jako "čtvereček", ovšem způsobů, jak ho nakreslit, je mnoho, některé se nám esteticky líbí více, některé méně.Co je to hezké nakreslení
Zkusme hezké nakreslení nějak definovat. Určitě budeme chtít, aby vrcholy nebyly příliš blízko u sebe, už vůbec ne jeden na druhém. Budeme asi také chtít, aby hrany byly rozumně dlouhé a nekřížily se příliš často. Můžeme si vymyslet i spoustu dalších kritérií.Pružinový model
V tomto modelu přiřadíme každému vrcholu "antigravitaci", odpudivou sílu. Díky tomu vrcholy nebudou příliš blízko u sebe. Mezi dvojice vrcholů, kde vede hrana, přidáme přitažlivou sílu (pružinu). Postupem času se působení sil ustálí a graf bude "hezký".Třída Vertex
package
{
import flash.display.Sprite;
import flash.geom.Point;
public class Vertex extends Sprite
{
// rychlost vrcholu
public var velocity:Point = new Point();
// síla vůči aktuálnímu modelu
public var net_force:Point = new Point();
public var isDragged:Boolean = false; // zda ho táhnu myší
public function Vertex():void
{
// doprostřed nakreslím kroužek
with(graphics)
{
beginFill(0xFF005E);
drawEllipse(-12, -12, 24, 24);
endFill();
}
}
}
}
Vytvoření grafu
// množina vrcholů
vertices = new Vector.< Vertex >(n, true);
// hrany v grafu incidence
edges = new Vector. < Vector.< Boolean >>(n, true);
for(i=0; i < n; i++) edges[i] = new Vector.< Boolean >(n, true);
while(e > 0) // přidám hrany
{
var a:int = Math.floor(Math.random()*n);
var b:int = Math.floor(Math.random()*n);
if(a==b || edges[a][b])continue;
edges[a][b] = true;
edges[b][a] = true;
e--;
}
// přidám vrcholy
for(i=0; i < n; i++)
{
var v:Vertex = new Vertex();
v.x = 200+Math.random()*300;
v.y = 100+Math.random()*200;
vertices[i] = v;
addChild(v);
v.addEventListener(MouseEvent.MOUSE_DOWN, drag);
v.addEventListener(MouseEvent.MOUSE_UP, sdrag);
}
Vykreslování modelu
Už máme vrcholy na náhodných pozicích. Teď provádíme iterace, v každé z nich přepočítáme polohu každého vrcholů podle ostatních vrcholů a podle jeho hran. Iterace provádíme, než "rozklepanost" (kinetická energie) systému neklesne pod nějaké minimum. V příkladu níže provádím iterace při každém snímku, model se nikdy úplně nezastaví.
function onEF(e:Event):void
{
for(i=0; i < n; i++) // projdu vrcholy
{
var v:Vertex = vertices[i];
var u:Vertex;
v.net_force.x = v.net_force.y = 0;
for(j=0; j < n; j++) // spočítám odpudivou sílu vůči ostatním
{
if(i==j)continue;
u = vertices[j];
var rsq:Number = ((v.x-u.x)*(v.x-u.x)+(v.y-u.y)*(v.y-u.y))/200;
v.net_force.x += (v.x-u.x) /rsq;
v.net_force.y += (v.y-u.y) /rsq;
}
for(j=0; j < n; j++) // spočítám přitažlivou sílu pro hrany
{
if(!edges[i][j])continue;
u = vertices[j];
v.net_force.x += 0.06*(u.x - v.x);
v.net_force.y += 0.06*(u.y - v.y);
}
v.velocity.x = (v.velocity.x + v.net_force.x)*0.85;
v.velocity.y = (v.velocity.y + v.net_force.y)*0.85;
}
for(i=0; i < n; i++) // nastavím vrcholům nové pozice
{
v = vertices[i];
if(v.isDragged){ v.x = mouseX; v.y = mouseY; }
else { v.x += v.velocity.x; v.y += v.velocity.y; }
}
// nakreslím hrany
graphics.clear();
graphics.lineStyle(3, 0x333333);
for(i=0; i < n; i++)
{
for(j=0; j < n; j++)
{
if(!edges[i][j]) continue;
graphics.moveTo(vertices[i].x, vertices[i].y);
graphics.lineTo(vertices[j].x, vertices[j].y);
}
}
}
Vynikajuce. Vdaka.
Zadejte si 12/60 a preji prijemnou zabavu pro dlouhy vecer...
Doporucuji pridat tlumeni.
Navic vypocet nikdy nedokonverguje k nule, takze graf neustale ujizdi, byt traba pomalounku...
Chtelo by to zastavovaci test: Kdyz zmena pozice je mensi nez 0.25 pixelu na vsech uzlech, zaokrouhi a prestan pocitat.
...zajimavy by mohl byt ukazatel celkove energie systemu, neco jako "kineticka + potencialni = celkova", aby se dalo sledovat, jak se po vychyleni ona celkova postupne snizuje.
PS: na 14/85 se mi graf vubec nezastavil. A jeho teziste mi postupne ujizdelo mimo obraz... jakmile ujede z okraj, uz ho nedohledam! A to same se stane, kdyz pri kontrukci grafu nejaky uzel nedostane zadnou hranu: 3/1 treba. To se mi pak obe skupiny rozleti na obe strany a nevidim, nic. detekce (a treba hlaseni?) a nesouvislem grafu? Anebo vypnuti vzajemneho ovlivnovani dvou nesouvisejicih garafu?
Mozna byse oboji dalo vylepsit ani tak zvetsenim tlumeni, jako spis:
a) vetsi "vzorkovaci frekvenci" - pocitat pri mensi zmene polohy, aby byl pohyb hladsi,
b) ujizdeni je mozna zpusobene nedokonalosti typu "spatne zaokrouhlovani" - vlastne se nepouziva opravdove zokrouhlovani, ale cislo jen se orizne, tedy je vzdy posunuto jen jednim smerem? ...ujizdi to hlavne doleva.
PS: 11/85 jeste stale generuje chaos... :)
"nestabilita vypoctu" - neiterovat pres stale stejny prirustek casu, ale urcovat si ho odhadem velikosti zmeny polohy (maximum nad vsemi uzly).
...odhad uz klidne lienarizaci: treba pouzit 20x mensi prirustek casu nez minule, pokud by zmena mela byt 20px: kriterium pouzit treba 0.5px, ovsem klidne v reozmezi 0.4-0.6px, tedy +- 20% ...to je OK.
Ovsem kazdou odhadnutou zmenu zase overit - to kvuli te "nestabilite vypoctu": pokud by zmena v prostoru byla vetsi nez povolenych 20% od 0.5px, nove polohy zahodit, upravit cas odhadem (klidne linearne) na cilenych 0.5px.
A pokud by byl prirustek mensi nez 20% od 0.5px, hodnoty poloh uzlu pouzit (jsme jeste presnejsi, nez je nutne), jen ten cas trosku zase zvetsit - linearizaci urcit o kolik.
Princip: dokud jsou zmeny poloh prilis velke, nove polohy nebrat, zahodit je, a prepocitat casovy prirustek.
Tim by se mela vyresit jak "hladkost" zobrazovani, tak snad i to zaokrouhlovani: Nabizi se takto totiz kriterium pro zastaveni.
Naopak, pokud by se pouze zvetsila "vzorkovaci frekvence" nic by se nevyresilo: Stacilo by do systemu kopnout vice a zase uz by uzly pri zobrazovani neplynule "skakaly"... Proto takt adaptabilne.
Realtime: Protoze "plynulost casu" je u realtime aplikace asi pozadavek, ale pritom, aby to zustalo stale "hladke" a vnitrne adaptabilni a presne, asi se to bude resit pomoci vlaken: Jedno na zobrazovani v danych casovych momentech (vlakno se vzorkovanim/taktovanim/prekreslovanim podle casu), naopak druhe jako generator casovych "fotek" systemu.
Dusledkem by bylo, ze pri pomalych pohybech by se obe vlakna flakala, ovsem pri velkych rychlostech a slabem HW by uz poctaci vlakno nemuselo stihat... Zobrazovaci by pak asi muselo vynechavat: Pocitaci vynechavat nesmi, prisli bychom o presnost.
Lze to resit uspavanim zobrazovaciho vlakna: probouzet ho
a) systemem rekneme na 20Hz (pro animaci staci)
b) prekreslovat screen pouze je-li nastaven priznak, ze je vubec uz spocitana nejaka hodnota.
Tim se resi jak zbytecne zatezovani rychleho systemu (nevykresluje se neustale, ale jen omezene casto, coz asi osetrene je, neb procesor mi to ted vytezuje jen malounko), tak i pretezovani uz tak zahlceneho slabeho systemu: Kresli se, jen kdyz se ma a navic jen kdyz je co. Kdyz neni co kreslit, spise dalsi periodu, ackoli treba mezi tim projdou vypocty 9ti dalsich bodu: Vykresli je jen ten posledni.
Rozdil proti dosavadnimu "skakani" je v tom, ze
a) uz by se nezobrazoval kazdy spocitany bod, (nenarocnost)
b) nezobrazovane body by se opravdu pocitaly. (presnost)
...tim graf:
1) prestane ujizdet (zastaveni vypoctu pri casovem prirustku vetsim nez 1s, kdy max zmena ma stale byt mensinez 0.5 px),
2) bude hladsi v pohybech
3) bude presnejsi a tedy i konecne opravdu dokonverguje (permutace 14/80 a vice).
Tlumeni pak samozrejme nebude 0.85 na jeden krok: Lze ho delat opet dynamicky-adaptivne, jako v prirode: s kvadratem rychlosti.
...pekny by byl take vstup nebo aspon ovlivneni pravdepodobnosti, jak generovat pocatecni graf: Treba abych mohl videt krychli (8/12), coz se mi "samo" za mnoho pokusu nenagenerovalo.
S tim souvisi i mechanismus generovani hran nad znamymi vrcholy: ted se zkousi nastrel, ale dala by se nejdrive nagenerovat mnozina vsech moznych dvojic, a z ni vybirat!
...tak by se take dal predem osetrit chybny vstup: Treba 4 hrany na trech vrcholech postavit nelze. A ted na tom animacka selhava. :-/ Skoda.