布氏圈算法

Question

我有畫一個圓圈下面的代碼：

#include<stdio.h> 
#include<conio.h> 
#include<graphics.h> 
#include<math.h> 

void main() 
{ 
    int xc, yc, x, y, p[100], r, k; 
    int gdriver=DETECT, gmode, errorcode; 
    printf("\nEnter the center point(xc,yc): "); 
    scanf("%d%d", &xc, &yc); 
    printf("\nEnter the radius: "); 
    scanf("%d", &r); 
    printf("\nPlotting...\n"); 
    sleep(5); 
    clrscr(); 

    initgraph(&gdriver, &gmode, ""); 
    p[0]=1-r; 
    x=0; 
    y=r; 
    for(k=0;k<=y;k++) 
    { 
     putpixel(xc+x, yc+y, 9); 
     putpixel(xc-x, yc-y, 9); 
     putpixel(xc+x, yc-y, 9); 
     putpixel(xc-x, yc+y, 9); 
     putpixel(xc+y, yc+x, 9); 
     putpixel(xc-y, yc-x, 9); 
     putpixel(xc+y, yc-x, 9); 
     putpixel(xc-y, yc+x, 9); 

     if(p[k]>0) 
     { 
      p[k+1]= p[k]+ 2*(x+1)+1-2*(y+1); 
      x++; 
      y--; 
     } 
     else 
     { 
      p[k+1]=p[k]+2*(x+1)+1; 
      x++; 
     } 
    } 
     getch(); 
} 

這部分代碼：

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

主要是對相對於圓形繪製點，它的工作原理因爲圓的對稱性。

但我無法弄清楚這部分代碼正在做什麼;

if(p[k]>0) 
     { 
      p[k+1]= p[k]+ 2*(x+1)+1-2*(y+1); 
      x++; 
      y--; 
     } 
     else 
     { 
      p[k+1]=p[k]+2*(x+1)+1; 
      x++; 
     } 

任何人都可以解釋我做了什麼嗎？ 在此先感謝。

Answer 1

更新公式看起來有點怪異，我會給我覺得什麼都低於正確的步驟：

您在圈子中的最高點開始，直到角度達到45度順時針旋轉。

現在，圓上的點大致滿足（x^2 + y^2 = r^2）。

這個想法是一次繪製一個像素，向正方向移動。如果你發現下一個點（沒有向下移動）距離圓心太遠，那麼這個點應該被拉低一個單位。例如，如果你看像素化的圓圈，你會發現它們可以被分解成一系列的水平線和像素。水平線的每一端都標出了延長線距離圓遠的點，因此您會看到一個下降點。

請注意，這裏有一些關於您選擇哪些點的自由裁量因素。有3個圓形繪圖學科：

1. 內圈：選擇點，使得沒有點繪製圓的外（這樣x^2 + y^2 < (r+1)^2 for each point r - 請注意，在這裏，而不是r其r+1）
2. 外圓：選擇點，以便在圓內沒有繪製點（所以x^2 + y^2 > (r-1)^2 for each point r - 注意其r-1此處而不是r）
3. 中圈：選擇最小化點數abs(x^2 + y^2 - r^2)。

您可以在算法中選擇任何這些規則。除了該代碼塊以外，這些方法是相同的（並且其中的更改較小）。

在每種情況下，您必須計算每個點偏離圓的距離。這需要知道x^2 + (y-1)^2 - r^2。我們稱之爲p[k]。如果x^2 + (y-1)^2 - r^2 <= 0，則向下移動會顯示該點太靠近圓的中心，因此下一點應該是(x+1, y)。在這種情況下，那麼接下來的偏差將是：

p[k+1] = (x+1)^2 + (y-1)^2 - r^2 = x^2 + (y-1)^2 - r^2 + 2x + 1 = p[k] + 2*(x + 1) - 1 

如果x^2 + y^2 - r^2 > 0，再下點應該是(x+1,y-1)，使

p[k+1] = (x+1)^2 + (y-2)^2 - r^2 = x^2 + (y-1)^2 - r^2 + 2x + 1 - 2y + 3 = q[k] + 2*(x + 1) - 2*(y - 1) = p[k] + 2*(x+1) - 2 * (y + 1) 

這些公式更改基於您是否有興趣在尋找外圈（像素永遠不會太靠近），內圈（像素永遠不會太遠）或中心圓（大致一致），但這是基本的想法。

Answer 2

您詢問的程序部分是圓形繪圖算法的核心部分，它計算圓的一個八分圓的x，y座標（八個putpixel（）調用將該八分圓鏡反射到另一個八分圓七個完成該圈）。該算法詳細解釋in this article。