Bresenham-Algorithmus für Kreise

Question

Ich habe den folgenden Code zum Zeichnen eines Kreises:

#include
#include
#include
#include

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();
}

Der Teil des Codes:

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);

dient hauptsächlich dazu, die Punkte im Bezug auf den Kreis zu zeichnen, und es funktioniert aufgrund der symmetrischen Eigenschaft des Kreises.

Aber ich konnte nicht herausfinden, was genau dieser Teil des Codes macht:

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++;
        }

Kann mir jemand erklären, was es macht? Danke im Voraus.

Answer 1

Die Aktualisierungsformeln sehen ein wenig seltsam aus, und ich werde unten angeben, was ich für die richtigen Schritte halte:

Sie beginnen am obersten Punkt im Kreis und drehen sich im Uhrzeigersinn, bis der Winkel 45 Grad erreicht.

Jetzt erfüllen die Punkte auf dem Kreis ungefähr (x^2 + y^2 = r^2).

Die Idee ist, einen Pixel nach dem anderen zu zeichnen, sich in die positive x-Richtung zu bewegen. Wenn Sie feststellen, dass der nächste Punkt (ohne nach unten zu verschieben) zu weit vom Mittelpunkt des Kreises entfernt ist, sollte dieser Punkt eine Einheit tiefer gezeichnet werden. Wenn Sie beispielsweise pixellierte Kreise betrachten, werden Sie feststellen, dass sie im Wesentlichen aus einer Reihe von horizontalen Linien und Pixeln bestehen. Jedes Ende der horizontalen Linie markiert einen Punkt, an dem eine Verlängerung der Linie zu weit vom Kreis entfernt wäre, und daher sehen Sie einen Abfall.

Beachten Sie, dass hier eine gewisse Ermessensfreiheit besteht, welche Punkte Sie wählen. Es gibt 3 Kreiszeichnungsdisziplinen:

1. Innerer Kreis: Wählen Sie Punkte so, dass kein Punkt außerhalb des Kreises gezeichnet wird (so dass x^2 + y^2 < (r+1)^2 für jeden Punkt r -- beachten Sie, dass hier r+1 steht und nicht r)
2. Äußerer Kreis: Wählen Sie Punkte so, dass kein Punkt innerhalb des Kreises gezeichnet wird (so dass x^2 + y^2 > (r-1)^2 für jeden Punkt r -- beachten Sie, dass hier r-1 steht und nicht r)
3. Mittlerer Kreis: Wählen Sie Punkte, die abs(x^2 + y^2 - r^2) minimieren.

Sie können eine dieser Disziplinen im Algorithmus wählen. Die Methoden sind identisch, abgesehen von diesem Codeblock (und die Änderungen dort sind geringfügig).

In jedem Fall müssen Sie berechnen, wie weit sich jeder Punkt vom Kreis entfernt. Dafür müssen Sie x^2 + (y-1)^2 - r^2 kennen. Nennen wir diese Sequenz p[k]. Wenn x^2 + (y-1)^2 - r^2 <= 0 ist, würde das Verschieben nach unten den Punkt zu nahe am Mittelpunkt des Kreises zeigen, daher sollte der nächste Punkt (x+1, y) sein. In diesem Fall wird die nächste Abweichung sein:

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

Wenn x^2 + y^2 - r^2 > 0 ist, sollte der nächste Punkt (x+1, y-1) sein, sodass

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)

Diese Formeln ändern sich je nachdem, ob Sie den äußeren Kreis (Pixel sind nie zu nah), inneren Kreis (Pixel sind nie zu weit) oder Mittelkreis (ungefähr in Linie) finden möchten, aber dies ist die grundlegende Idee.

Answer 2

Der Abschnitt des Programms, über den Sie fragen, ist der Kern des Kreiszeichnungsalgorithmus, und er berechnet die x-, y-Koordinaten für ein Oktant des Kreises (die acht putpixel () Aufrufe spiegeln dieses Oktanten in die anderen sieben, um den Kreis zu vervollständigen). Der Algorithmus wird ausführlich in diesem Artikel erklärt in diesem Artikel.