不曉得有誰對 Bresenham's circle algorithm 了解的?
我這裏目前只找到相關 code，沒有說明
想請懂的人解說一下或是 post 相關站台
void Draw_Circle(int x1, int y1, int rad, char colour)
{
// Based on Bresenham's circle algorithm - very fast
int x, y, d;
x = 0;
y = rad;
d = 3 - (2 * rad);
while (x < y)
{
Draw_Pixel(x1 + x, y1 + y, colour);
Draw_Pixel(x1 + x, y1 - y, colour);
Draw_Pixel(x1 - x, y1 + y, colour);
Draw_Pixel(x1 - x, y1 - y, colour);
Draw_Pixel(x1 + y, y1 + x, colour);
Draw_Pixel(x1 + y, y1 - x, colour);
Draw_Pixel(x1 - y, y1 + x, colour);
Draw_Pixel(x1 - y, y1 - x, colour);
if (d < 0)
d = d + (4 * x) + 6;
else
{
d = d + 4 * (x - y) + 10;
y = y - 1;
}
x++;
}
if (x == y)
{
Draw_Pixel(x1 + x, y1 + y, colour);
Draw_Pixel(x1 + x, y1 - y, colour);
Draw_Pixel(x1 - x, y1 + y, colour);
Draw_Pixel(x1 - x, y1 - y, colour);
Draw_Pixel(x1 + y, y1 + x, colour);
Draw_Pixel(x1 + y, y1 - x, colour);
Draw_Pixel(x1 - y, y1 + x, colour);
Draw_Pixel(x1 - y, y1 - x, colour);
}
}
龍龍
--
你是一位聰明人嗎?如果是，你該記住，你的聰明是跟那些人學來的，
然後在適當的地點，適當的時間，輕輕的對那人說：這是你教我的。
聲音要輕，而且只告訴他一個人。
摘錄自"牧羊少年奇幻之旅"
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: DickG.m5.ntu.ed
> -------------------------------------------------------------------------- <
作者: hotball (哲哲魚) 看板: C_and_CPP
標題: Re: about "Bresenham's circle algorithm"
時間: Mon Jan 4 01:49:41 1999
※ 引述《DickG (龍龍)》之銘言：
: 不曉得有誰對 Bresenham's circle algorithm 了解的?
: 我這裏目前只找到相關 code，沒有說明
: 想請懂的人解說一下或是 post 相關站台
這個方法是算出圓形的 1/8 然後畫八次就畫出整個圓形，所以有八個 Draw_Pixel，
畫到 x == y 時就結束。其中 d 是誤差項，決定每次 x+1 時 y 是否要 -1。
誤差項的算法有點複雜，有空再把它詳細寫出來。
> -------------------------------------------------------------------------- <
作者: hotball (哲哲魚) 看板: C_and_CPP
標題: Re: about "Bresenham's circle algorithm"
時間: Mon Jan 4 02:47:47 1999
基本上這個演算法的精神和畫線的方法是很類似的，都是用一誤差項（即 d）
來決定 y 是否要加 1。誤差項的算法是這樣的：
考慮圓形的函數 f(x, y) = x^2 + y^2 - R^2，f == 0 即表示在圓形上。
f > 0 則在圓外，f < 0 在圓內。
所以，當 x + 1 時，則考慮
f(x+1, y - 1/2) = (x+1)^2+(y-1/2)^2-R^2 = p
當 p > 0 時，則 y 已經太大，所以在下一次要將 y - 1，而 p < 0 則
保留 y 的值。也就是說，當 p > 0 時，則向右下方移動：
q = f(x+2, y-3/2) = (x+2)^2+(y-3/2)^2-R^2
q - p = 2x - 2y + 5
而 p <= 0 時，則向右方移動：
q = f(x+2, y-1/2) = (x+2)^2+(y-1/2)^2-R^2
q - p = 2x + 3
p 的初值是 f(1, R-1/2) = 1 + (R-1/2)^2 - R^2 = 5/4 - R
把它們全都 x 4 就可以用整數表示：
(右下方) q - p = 8(x-y) + 20
(右方) q - p = 8x + 12
(初值) p0 = 5 - 4R
在 Bresenhams 的演算法中，把初值改成 p0 = 3/2 - R 所以只乘上 2，
其餘則完全相同，不過我不知道為什麼要把初值設成 3/2 - R。
要加快 Bresenhams 演算法的速度，可以改寫成：
delta_right = 12;
delta_right_down = 20 - 8*r;
p = 5 - 4*r;
x = 0;
y = r;
while(x < y) {
...
if(p < 0) {
p += delta_right;
delta_right_down += 8;
}
else {
y--;
p += delta_right_down;
}
delta_right += 8;
x++;
...
}
這樣可以減少在迴圈內進行 *4 或 *8 的動作。
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: kimicat.m1.ntu.
> -------------------------------------------------------------------------- <
作者: hotball (哲哲魚) 看板: C_and_CPP
標題: Re: about "Bresenham's circle algorithm"
時間: Mon Jan 4 21:07:21 1999
※ 引述《DickG (龍龍)》之銘言：
: ※ 引述《DickG (龍龍)》之銘言：
: : 剛剛試了一下
: : circle(x, y, r=0 to r1, color)
: : (原本想利用此法來畫實心圓)
: : 發現到用此演算法所畫出的圓如果其半徑遞增的話
: : 會於所畫出的實心圓中出現沒有畫到的點…
: : 看來要畫實心畫是不能用此法的
: : 不曉得有其它的方法嗎?
: 突然想到，如果利用 Bresenham circle algorithm
: 求得一圓上對稱於 x 軸或是 y 軸所得到的兩個對稱點
: 再利用畫直線(可考慮特殊情況，即為水平線或是垂直線)來一一畫出
: 這樣就能達到畫實心圓的方法了
: 不過還沒有試過，不曉得效率如何
: 龍龍
畫實心圓不可以用半徑遞增的方法……那太慢了，而且「一定」會缺一些點……
用畫水平線的方式畫會比較快……畫水平線比垂直線快喔……
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: kimicat.m1.ntu.