ブレゼンハムの円描画アルゴリズム
私たちのコンピュータ画面はマトリックス状に組織されたピクセルで構成されているため、コンピュータ画面上に連続した滑らかな円弧を表示するのは簡単ではありません。したがって、コンピュータ画面上に円を描くには、円弧を形成できるように、印刷されたピクセルから最も近いピクセルを常に選択する必要があります。これを行うには 2 つのアルゴリズムがあります。
- 中点円描画アルゴリズム
- ブレゼンハムの円描画アルゴリズム
についてはすでに議論しました 中点円描画アルゴリズム この投稿では、ブレゼンハムの円描画アルゴリズムについて説明します。
これらのアルゴリズムは両方とも、対称性が高いという円の重要な特徴を使用します。したがって、360 度の円全体を 45 度の八分円ごとに 8 つの部分に分割します。これを行うために、ブレゼンハムの円アルゴリズムを使用して、45 度の最初の八分円内のピクセルの位置を計算します。円は原点の中心にあると仮定します。したがって、計算されるすべてのピクセル (x y) について、以下に示すように、円の 8 つの八分円のそれぞれにピクセルを描画します。
ピクセル (xy) の場合、8 八分円内のすべての可能なピクセル
次に、既知のピクセル位置 (x y) から次のピクセル位置を計算する方法を見ていきます。 Bresenham のアルゴリズムでは、任意の点 (x y) において、東側 (x+1 y) の次のピクセルを選択するか、南東 (x+1 y-1) の次のピクセルを選択するかの 2 つのオプションがあります。
そして、これは決定パラメータ d を次のように使用して決定できます。
- d > 0 の場合、(x+1 y-1) が円弧に近づくため、次のピクセルとして選択されます。
- それ以外の場合は (x+1 y) が次のピクセルとして選択されます。
ここで、指定された半径 'r' と中心 (xc yc) の円を描画します。(0 r) から開始して、x=y (つまり 45 度) まで第 1 象限内を移動します。リストされた初期条件から開始する必要があります。
d = 3 - (2 * r)
x = 0
y = rここで、ピクセルごとに次の操作を実行します。
- (xc yc)、(x y)の初期値を設定します。
- 決定パラメータ d を d = 3 – (2 * r) に設定します。
- drawCircle(int xc int yc int x int y) 関数を呼び出します。
- x になるまで次の手順を繰り返します。 <= y:
- もしd < 0 set d = d + (4 * x) + 6.
- それ以外の場合は、 d = d + 4 * (x – y) + 10 を設定し、y を 1 減分します。
- xの値をインクリメントします。
- drawCircle(int xc int yc int x int y) 関数を呼び出します。
drawCircle()関数:
CPP以下は、上記のアプローチの C 実装です。
CPP#include #include // Function to put pixels // at subsequence points void drawCircle ( int xc int yc int x int y ){ putpixel ( xc + x yc + y RED ); putpixel ( xc - x yc + y RED ); putpixel ( xc + x yc - y RED ); putpixel ( xc - x yc - y RED ); putpixel ( xc + y yc + x RED ); putpixel ( xc - y yc + x RED ); putpixel ( xc + y yc - x RED ); putpixel ( xc - y yc - x RED ); } // Function for circle-generation // using Bresenham's algorithm void circleBres ( int xc int yc int r ){ int x = 0 y = r ; int d = 3 - 2 * r ; drawCircle ( xc yc x y ); while ( y >= x ){ // check for decision parameter // and correspondingly // update d y if ( d > 0 ) { y -- ; d = d + 4 * ( x - y ) + 10 ; } else d = d + 4 * x + 6 ; // Increment x after updating decision parameter x ++ ; // Draw the circle using the new coordinates drawCircle ( xc yc x y ); delay ( 50 ); } } int main () { int xc = 50 yc = 50 r = 30 ; int gd = DETECT gm ; initgraph ( & gd & gm '' ); // initialize graph circleBres ( xc yc r ); // function call return 0 ; } 出力：
利点
- シンプルなアルゴリズムです。
- 簡単に実装できます
- それは完全に円の方程式、つまり x に基づいています。 2 +y 2 =r 2
短所
- ポイントを生成する際の精度に問題があります。
- このアルゴリズムは、複雑で高グラフィックな画像には適していません。
