schneller Algorithmus für gefüllte Kreise zu zeichnen?

https://stackoverflow.com/questions/1201200

05-07-2019
|

Frage

Ich bin mit Bresenhamschen Kreis Algorithmus für schnelle Kreiszeichnung. Allerdings mag ich auch (auf Wunsch des Benutzers) einen gefüllten Kreis zeichnen.

Gibt es eine schnelle und effiziente Art und Weise, dies zu tun? Etwas auf der gleichen Linie von Bresenham?

Die Sprache verwende ich C.

Lösung

der Wikipedia-Seite über Bresenhamschen (auch ‚Midpoint‘) Kreis Algorithmus gelesen haben, wäre es scheint, dass die einfachste Sache zu tun wäre, seine Aktionen zu modifizieren, so dass anstelle von

setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);

und ähnliche, jedes Mal, wenn Sie stattdessen tun

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);

Das heißt, für jedes Paar von Punkten (mit dem gleichen y), die Bresenham würden Sie haben Sie Handlung , Sie stattdessen Verbindung mit einer Zeile .

Andere Tipps

Just Brute-Force verwenden. Dieses Verfahren wiederholt sich über ein paar zu viele Pixel, aber es nutzt nur ganzzahlige Multiplikationen und Additionen. Sie vermeiden vollständig die Komplexität des Bresenham und den möglichen Engpass von sqrt.

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

Hier ist eine C # grobe Orientierung (sollte nicht so schwer sein, die richtige Idee für C zu erhalten.) - das ist die „rohe“ Form ohne Bresenham unter Verwendung von Quadratwurzeln zu beseitigen

Bitmap bmp = new Bitmap(200, 200);

int r = 50; // radius
int ox = 100, oy = 100; // origin

for (int x = -r; x < r ; x++)
{
    int height = (int)Math.Sqrt(r * r - x * x);

    for (int y = -height; y < height; y++)
        bmp.SetPixel(x + ox, y + oy, Color.Red);
}

bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");

Sie können diese verwenden:

void DrawFilledCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int xChange = 1 - (radius << 1);
    int yChange = 0;
    int radiusError = 0;

    while (x >= y)
    {
        for (int i = x0 - x; i <= x0 + x; i++)
        {
            SetPixel(i, y0 + y);
            SetPixel(i, y0 - y);
        }
        for (int i = x0 - y; i <= x0 + y; i++)
        {
            SetPixel(i, y0 + x);
            SetPixel(i, y0 - x);
        }

        y++;
        radiusError += yChange;
        yChange += 2;
        if (((radiusError << 1) + xChange) > 0)
        {
            x--;
            radiusError += xChange;
            xChange += 2;
        }
    }
}

Ich mag palm3D Antwort. Für rohe Gewalt zu sein, ist dies eine erstaunlich schnelle Lösung. Es gibt keine Quadratwurzel oder trigonometrische Funktionen, die es zu verlangsamen. Seine einzige Schwäche ist die verschachtelte Schleife.

Konvertieren dieser zu einer einzigen Schleife macht diese Funktion fast doppelt so schnell.

int r2 = r * r;
int area = r2 << 2;
int rr = r << 1;

for (int i = 0; i < area; i++)
{
    int tx = (i % rr) - r;
    int ty = (i / rr) - r;

    if (tx * tx + ty * ty <= r2)
        SetPixel(x + tx, y + ty, c);
}

Diese einzige Schleife Lösung Rivalen die Effizienz einer Linienzeichnung Lösung.

            int r2 = r * r;
            for (int cy = -r; cy <= r; cy++)
            {
                int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5);
                int cyy = cy + y;

                lineDDA(x - cx, cyy, x + cx, cyy, c);
            }

Hier ist, wie ich es so mache:
Ich bin mit festen Punktwerten mit zwei Bits Präzision (wir haben auf der Hälfte Punkte und Quadratwerte von Halb Punkten verwalten)
Wie in einer vorherigen Antwort erwähnt, verwende ich auch Quadratwerte anstelle von Quadratwurzeln.
Erstens, ich bin Erkennung Grenze Grenze meines Kreises in einem 1/8-Teil des Kreises. Ich verwende symetric dieser Punkte die 4 „Grenzen“ des Kreises zu zeichnen. Dann bin ich auf den Platz innerhalb des Kreises zeichnen.

Im Gegensatz zu dem Mittelpunkt Kreis algorith , wird dieser mit sogar Durchmessern arbeiten (und mit reellen Zahlen Durchmesser auch mit einigen kleinen Änderungen).

Bitte verzeihen Sie mir, wenn meine Erklärungen nicht klar waren, ich bin französisch;)

void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY)
{
    const int FULL = (1 << 2);
    const int HALF = (FULL >> 1);

    int size = (circleDiameter << 2);// fixed point value for size
    int ray = (size >> 1);
    int dY2;
    int ray2 = ray * ray;
    int posmin,posmax;
    int Y,X;
    int x = ((circleDiameter&1)==1) ? ray : ray - HALF;
    int y = HALF;
    circlePosX -= (circleDiameter>>1);
    circlePosY -= (circleDiameter>>1);

    for (;; y+=FULL)
    {
        dY2 = (ray - y) * (ray - y);

        for (;; x-=FULL)
        {
            if (dY2 + (ray - x) * (ray - x) <= ray2) continue;

            if (x < y)
            {
                Y = (y >> 2);
                posmin = Y;
                posmax = circleDiameter - Y;

                // Draw inside square and leave
                while (Y < posmax)
                {
                    for (X = posmin; X < posmax; X++)
                        setPixel(circlePosX+X, circlePosY+Y);
                    Y++;
                }
                // Just for a better understanding, the while loop does the same thing as:
                // DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y);
                return;
            }

            // Draw the 4 borders
            X = (x >> 2) + 1;
            Y = y >> 2;
            posmax = circleDiameter - X;
            int mirrorY = circleDiameter - Y - 1;

            while (X < posmax)
            {
                setPixel(circlePosX+X, circlePosY+Y);
                setPixel(circlePosX+X, circlePosY+mirrorY);
                setPixel(circlePosX+Y, circlePosY+X);
                setPixel(circlePosX+mirrorY, circlePosY+X);
                X++;
            }
            // Just for a better understanding, the while loop does the same thing as:
            // int lineSize = circleDiameter - X*2;
            // Upper border:
            // DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize);
            // Lower border:
            // DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize);
            // Left border:
            // DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize);
            // Right border:
            // DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize);

            break;
        }
    }
}

void DrawSquare(int x, int y, int size)
{
    for( int i=0 ; i<size ; i++ )
        DrawHorizontalLine(x, y+i, size);
}

void DrawHorizontalLine(int x, int y, int width)
{
    for(int i=0 ; i<width ; i++ )
        SetPixel(x+i, y);
}

void DrawVerticalLine(int x, int y, int height)
{
    for(int i=0 ; i<height ; i++ )
        SetPixel(x, y+i);
}

Nicht-Integer-Durchmesser zu verwenden, können Sie Präzision von festen Punkt erhöhen oder doppelte Werte verwenden. Es sollte auch möglich sein, eine Art von Anti-Aliasing zu machen abhängig von der Differenz zwischen dY2 + (ray - x) * (ray - x) und ray2 (dx² + dy² und r²)

Wenn Sie einen schnellen Algorithmus wollen, sollten Sie einen Polygon mit N-Seiten zeichnen, desto höher ist N, desto genauer wird der Kreis sein.

palm3D der Brute-Force-Algorithmus fand ich ein guter Ausgangspunkt sein. Diese Methode nutzt die gleiche Prämisse, aber es ein paar Möglichkeiten, sind die meisten der Pixel überspringen zu überprüfen.

Als erstes ist hier ist der Code:

int largestX = circle.radius;
for (int y = 0; y <= radius; ++y) {
    for (int x = largestX; x >= 0; --x) {
        if ((x * x) + (y * y) <= (circle.radius * circle.radius)) {
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y + y);
            drawLine(circle.center.x - x, circle.center.x + x, circle.center.y - y);
            largestX = x;
            break; // go to next y coordinate
        }
    }
}

Als nächstes wird die Erklärung.

Das erste, was ist zu beachten, dass, wenn Sie die minimale x-Koordinate feststellen, dass innerhalb des Kreises ist für eine gegebene horizontale Linie, erhalten Sie sofort wissen, dass die maximale x-Koordinate. Dies ist aufgrund der Symmetrie des Kreises. Wenn das x-Koordinate mindestens 10 Pixel vor der linken Seite der Box des Kreises Begrenzungs ist, dann ist die maximale x 10 Pixel hinter dem rechten Seite des Begrenzungsrahmen des Kreises.

Der Grund von hohen x-Werten zu niedrig x Werten zu durchlaufen ist, dass der minimale x-Wert wird mit weniger Iterationen zu finden. Dies ist, weil der minimale x-Wert näher an der linken Seite der Bounding-Box als die Mitte Koordinate x des Kreises für die meisten Linien aufgrund des Kreises nach außen gekrümmt ist, wie auf dieses Bild Das nächste, was zu beachten ist, dass, da der Kreis auch vertikal symmetrisch ist, jede Zeile, die Sie finden gibt Ihnen eine kostenlose zweite Linie zu zeichnen, jedes Mal, wenn Sie eine Zeile in der oberen Hälfte des Kreises zu finden, können Sie einen auf der unteren Hälfte bekommen der Radius y-y-Koordinate. Daher wird, wenn jede Zeile gefunden wird, zwei gezogen und muss nur die obere Hälfte der y-Werte werden kann iteriert werden.

Das letzte, was zu beachten ist, dass das ist, wenn Sie von einem y-Wert starten, der in der Mitte des Kreises und dann nach oben bewegen, um y, dann ist der minimale x-Wert für jede nächste Zeile muss das Zentrum näher x-Koordinate des Kreises als die letzte Zeile. Dies ist auch auf den Kreis geschwungenen näher in Richtung der Mitte x-Wert, wie Sie den Kreis nach oben. Hier ist eine visuelle, wie das der Fall ist.

Zusammenfassung:

Wenn Sie die Mindest x-Koordinate einer Linie finden, erhalten Sie die maximalen x kostenlos koordinieren.
Jede Zeile, die Sie finden auf der oberen Hälfte des Kreises zu zeichnen gibt Ihnen eine Linie auf der unteren Hälfte des Kreises kostenlos.
Jeder minimal x hat, um näher an die Mitte des Kreises als die vorherigen Koordinaten x Koordinate für jede Zeile, wenn sie von der Mitte nach oben y-Koordinate Iterieren.

Sie können auch den Wert von (radius * radius) speichern und auch (y * y), anstatt sie für die Berechnung mehrmals.

Ich würde nur eine Liste von Punkten erzeugen und dann eine Polygonzeichnungsfunktion für die Wiedergabe verwendet werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow