畫圓形(Bresenham算法)

下面先簡要介紹常用的畫圓算法（Bresenham算法），然後再具體闡述筆者對該算法的改進。

    一個圓，如果畫出了圓上的某一點，那麼可以利用對稱性計算餘下的七段圓弧：Plot(x，y)，Plot(y，x)，Plot(y，-x)，Plot(x，-y)，Plot(-x，-y)，Plot(-y，-x)，Plot(-y，x)，Plot(-x，y)。

    1、Bresenham 畫圓算法。Bresenham算法的主要思想是：以坐标原點（0，0）為圓心的圓可以通過0度到45°的弧計算得到，即x從0增加到半徑，然後利用對稱性計算餘下的七段圓弧。當x從0增加到時，y從R遞減到。

    設圓的半徑為R，則圓的方程為：

    f(x，y)＝(x+1)2+y2-R2＝0                                   (1)

    假設目前列（x=xi列）中最接近圓弧的像素已經取為P(xi，yi)，根據第二卦限1/8圓的走向，下一列（x=xi+1列）中最接近圓弧的像素隻能在P的正右方點H(xi+1，yi)或右下方點L(xi+1，yi-1)中選擇，如圖1所示。Bresenham畫圓算法采用點T(x，y)到圓心的距離平方與半徑平方之差D(T)作為選擇标準，即

    D(T)=(x+1)2+y2-R2                                         (2)

    通過比較H、L兩點各自對實圓弧上點的距離大小，即根據誤差大小來選取，具有最小誤差的點為繪制點。根據公式(2)得：

    對H(xi+1，yi)點有：D(H)=(xi+1)2+yi2-R2；

    對L(xi+1，yi-1)點有：D(L)=(xi+1)2+(yi-1)2-R2；

    根據Bresenham畫圓算法，則選擇的标準是：

    如果|D(H)|<|D(L)|，那麼下一點選取H(xi+1，yi)；

    如果|D(H)|>|D(L)|，那麼下一點選取L(xi+1，yi-1)；

    如果|D(H)|=|D(L)|，那麼下一點可以取L(xi+1，yi-1)，也可以選取H(xi+1，yi)，我們約定選取H(xi+1，yi)。

    圖1  Bresenham畫圓算法點的選取

    綜合上述情況，得：

    當|D(H)|>|D(L)|時，選取L點(xi+1，yi-1)為繪制點坐标；

    當|D(H)|<|D(L)|時，選取H點(xi+1，yi)為繪制點坐标。

    然後将選取的點坐标作為目前坐标，重複上述過程直至xi=或者yi=為止，(xi，yi)的初始值為（0，R）。

    以上便是Bresenham算法的主要思想，但是上述算法是在一個假設下：以坐标原點（0，0）為圓心。該假設實際上隻是為了友善算法的研究。但在實際嵌入式LCD顯示裝置中，往往圓心坐标不是（0，0）點，而是以左上角為（0，0）點，這樣就使得在實際運用中，需要對這個算法做很大的改進。

    另外，如果完全按照Bresenham畫圓算法，那麼就會涉及到浮點運算，這使得嵌入式程式設計十分煩瑣，因為本系統中所有資料都是整型的，是以在這方面也要作一定的改進。下面根據本系統中嵌入式硬體特點和資料結構得特點，對這個算法進行改進。

    2、改進的Bresenham畫圓算法。先假設起始點為（R，0），令Pi=(xi，yi)為目前的一點，那麼我們就需要在Ti=(xi，yi+1)和Si=(xi-1，yi+1)中選取一點，如圖2所示。

    圖2 嵌入式LCD畫圓時點的選取

    設(xi-1/2+e，yi+1)為S和T之間圓上的點，e是S、T中點到圓上點的誤差，帶入圓的方程(1)得：

    f(xi-1/2+e，yi+1)=(xi-1/2+e)2+(yi+1)2-R2=f(xi-1/2，yi+1)+2(xi-1/2)e+e2=0   (3)

    在式(3)中，令

    di="f"(xi-1/2，yi+1)=-2(xi-1/2)e-e2                                    (4)

    如果e<0，那麼di>0，是以選擇S=(xi-1，yi+1)，根據(3)與(4)得：

    di+1=f(xi-1-1/2，yi+1+1)=di-2(xi-1)+2(yi+1)+1=di+2(yi+1-xi+1)+1         (5)

    如果e30，那麼di￡0，是以選擇T=(xi，yi+1)，根據(3)與(4)得：

    di+1=f(xi-1/2，yi+1+1)=di+2yi+1+1                                  (6)

    起始點是（R，0）的時候，根據(4)得di的初始值d0就是：

    d0=f(R-1/2，0+1)=(R-1/2)2+1-R2=5/4-R=1-R（由于程式設計中所用資料類型均為整型，故取1-R）。

    當選取S=(xi-1，yi+1)時，那麼di+1＝di+2(yi+1-xi+1)+1；

    當選取T=(xi，yi+1)時，那麼di+1=di+2yi+1+1；

    然後将選取的點坐标作為目前坐标，重複上述過程直至x=y，而不是xi=或者yi=，這樣就可以不用作浮點數計算了。

    本項目中的LCD像素為640×480點陣，并且資料是八位的，當橫坐标和縱坐标超過255時，那麼資料就不能一次傳送成功，是以需要通過位元組操作來設定高位元組，然後再傳送低位元組。是以，每次畫圓上的點時要傳送的參數至少是六個，圓心坐标是四個（因為要考慮圓心坐标可能大于255，是以要對其圓心坐标設定高、低位元組），另外兩個是圓上的點相對于圓心的坐标，但是最後要畫一個點，需要四個參數，即改進的畫圓算法為六個參數輸入，四個參數輸出。

#include <graphics.h>

#include <math.h>

void MidPointCircle(int r, int color);     /*中點bresenham算法*/

void CirclePoints(int x,int y,int color);

void BresenhamCircle(int xc,int yc,int r,int color);

void plot_cicle_point(int xc,int yc,int x,int y,int color);

main()

{

   int gdriver=DETECT,gmode;

   initgraph(&gdriver,&gmode," ");

   cleardevice();

   setbkcolor(2);

   MidPointCircle(100,4);

   getch();

   BresenhamCircle(100,100,50,5);

   closegraph();

}

void MidPointCircle(int r,int color)

  int x,y;

  float d;

  x=0;y=r;

  d=1.25-r;

  CirclePoints(x,y,color);

  while(x<=y)

  {

    if(d<0)

       d+=2*x+3;

    else

    {

       d+=2*(x-y)+5;

       y--;

    }

    x++;

    CirclePoints(x,y,color);

  }

void CirclePoints(int x,int y,int color)

   putpixel(x,y,color);

   putpixel(y,x,color);

   putpixel(-x,y,color);

   putpixel(y,-x,color);

   putpixel(x,-y,color);

   putpixel(-y,x,color);

   putpixel(-x,-y,color);

   putpixel(-y,-x,color);

void plot_circle_point(int xc,int yc,int x,int y,int color)

    putpixel(xc+x,yc+y,color);

    putpixel(xc-x,yc+y,color);

    putpixel(xc+x,yc-y,color);

    putpixel(xc-x,yc-y,color);

    putpixel(xc+y,yc+x,color);

    putpixel(xc-y,yc+x,color);

    putpixel(xc+y,yc-x,color);

    putpixel(xc-y,yc-x,color);

void BresenhamCircle(int xc,int yc,int r,int color)

  int x,y,d;

  d=3-2*r;

  while(x<y)

     plot_circle_point(xc,yc,x,y,color);

     if(d<0)

 d=d+4*x+6;

     else

     {

 d=d+4*(x-y)+10;

 y--;

     }

     x++;

  if(x==y)

    plot_circle_point(xc,yc,x,y,color);

PASCAL程式

program circlebre;

uses crt,graph;

var

  gd,gm:integer;

  xasp,yasp:word;

  ratio:real;

  procedure bresenham_circle(x0,y0,r:integer);

  var

    x,y,D:integer;

  begin

    x:=0;

    y:=r;

    d:=3-r-r;

    while x<=y do

    begin

      putpixel(x0+x,round((y0+y)*ratio),white);

      putpixel(x0-x,round((y0+y)*ratio),white);

      putpixel(x0+x,round((y0-y)*ratio),white);

      putpixel(x0-x,round((y0-y)*ratio),white);

      putpixel(x0+y,round((y0+x)*ratio),white);

      putpixel(x0-y,round((y0+x)*ratio),white);

      putpixel(x0+y,round((y0-x)*ratio),white);

      putpixel(x0-y,round((y0-x)*ratio),white);

      if d<0 then

        inc(d,4*x+6)

      else

      begin

        inc(d,4*(x-y)+10);

        dec(y);

      end;

      inc(x);

    end;

  end;

begin

  gd:=detect;

  initgraph(gd,gm,'D:\tp\bgi');

  getaspectratio(xasp,yasp);

  ratio :=xasp/yasp;

  bresenham_circle(300,100,50);

  Repeat until Keypressed;

  closegraph;

end.