| このアルゴリズムは最初に始点と終点との間の距離をＸ、Ｙ方向それぞれに求めて、 その大きい方の値をベース値として、カウンタの値とベース値を比較しながら点を打っていきます。 例えばＸの距離のほうが大きい場合は、Ｘ方向にまず点を打っていき、カウンタ値がベース値を越えたときに Ｙ座標を更新して、またＸ方向に打っていきます。その繰り返し。 このアルゴリズム、何がスゴイかというと加算と減算しか行ってないんです。 これはコンピュータにとって、乗算や除算を使う場合より圧倒的に早いです。 まぁ、一本線を引くぐらいじゃぁ、速さの違いはわかりませんが…。 ↓実行画面 ↑マウスでクリックすると、始点が変化。
/************************************
* ブレゼンハムのアルゴリズム
***********************************/
public void line(int x1,int y1,int x2,int y2){
int px; //現在、点を打っている座標
int py;
int counter = 0; //カウンタ
int dstX; //始点から終点までの距離
int dstY;
int addX; //増加分
int addY;
//始点から終点までの、x,yそれぞれの距離を求める
dstX = x2 - x1;
if(dstX ＜ 0){
dstX *= -1; //0以下なら符号反転
addX = -1;
}
else{
addX = 1;
}
dstY = y2 - y1;
if(dstY ＜ 0){
dstY *= -1; //0以下なら符号反転
addY = -1;
}
else{
addY = 1;
}
px = x1; //(x1,y1)の位置から始める
py = y1;
//距離を比較
if(dstX > dstY){
// X方向に点を打っていく
for(int i=0;i＜dstX;i++){
if(px>0 && px＜DISP_WIDTH && py>0 && py＜DISP_HEIGHT){
backbuf[py*DISP_WIDTH + px] = 0xFFffffff;
counter += dstY;
if(counter > dstX){
counter -= dstX;
py += addY;
}
}
px += addX;
}
}
else{
// Y方向に点を打っていく
for(int i=0;i＜dstY;i++){
if(px>0 && px＜DISP_WIDTH && py>0 && py＜DISP_HEIGHT){
backbuf[py*DISP_WIDTH + px] = 0xFFffffff;
counter += dstX;
if(counter > dstY){
counter -= dstY;
px += addX;
}
}
py += addY;
}
}
}
|