Rasterizace kružnice Bresenhamovým algoritmem – applet

J. E. Bresenham publikoval algoritmus pro rasterizaci kružnice, který je stejně efektivní jako jeho řešení rasterizace úsečky. V literatuře je algoritmus nazván „midpoint algorithm“.

Either scripts and active content are not permitted to run or Adobe Flash Player version 11.1.0 or greater is not installed.

Get Adobe Flash Player

Teorie

Pro body na kružnici platí rovnice x2 + y2r2 = 0, kterou lze zapsat v podobě implicitní funkce

rovnice 1

Hodnota funkce F je pro body uvnitř kružnice záporná, zatímco pro body vně je hodnota kladná.

Předpokládejme situaci, kdy se nacházíme na pozici [xi, yi] a vykreslujeme v prvním oktantu. Dalším bodem, který připadá do úvahy, je buď bod [xi + 1, yi] nebo [xi + 1, yi + 1]. Určíme si bod, ležící na středu úsečky mezi těmito dvěma body. Dosadíme-li jeho souřadnice [xi + 1, yi − 1/2] do předchozí funkce, rozhodneme na základě znaménka výsledku o tom, zda tento bod leží uvnitř či vně kružnice. Výsledek tedy můžeme označit jako rozhodovací činitel

rovnice 2

Je-li znaménko záporné, bude vybrán bod se stejnou souřadnicí yi, tedy ten horní. Naopak při kladné hodnotě rozhodovacího členu pi bude vybrán pro vykreslení bod yi + 1, tedy spodní. Hodnotu pi budeme pro každý krok algoritmu přepočítávat podle předchozí hodnoty takto

rovnice 3

Ovládání appletu

Applet se skládá z vykreslovací plochy a ovládacího panelu dole. Kružnici na vykreslovací ploše zadáme kliknutím kamkoli na plochu, tím označíme střed kružnice a druhým klikem (jinde než první klik) zadáme její poloměr.

Spojnice mezi bodem středu a bodem vytyčujícím její poloměr má modrou barvu. Skutečný průměr, dle kterého algoritmus počítá pixely, které se mají vykreslit, je naznačena barvou červenou. Teoretická kružnice, tedy kružnice, kterou bychom dostali při nekonečně malých pixelech, je vykreslena rovněž červeně. V úvahu se bere vždy střed pixelu, proto pohybem středového bodu či bodu určujícího poloměr kružnice v rámci jednoho pixelu se kružnice nezmění (nepřekreslí).

Posuvník a tlačítka + a − zvětšují velikost pixelu pro větší názornost. Tlačítko reset uvede applet do startovní pozice při načtení, takže je možné kreslit znovu. Rovněž je však možné pohybem stávajících bodů měnit jejich polohu a za běhu vidět změnu ve vykreslení pixelů.


(c) 2012, Jakub Malina, Pavel Rajmic, Ústav telekomunikací, FEKT, VUT v Brně