Midpoint circle Algorithmus für gefüllte Kreise
Den Midpoint circle Algorithmus verwendet werden können, Rastern Sie die Grenze des Kreises. Allerdings möchte ich, dass der Kreis gefüllt werden, ohne die Pixel mehrfach (das ist sehr wichtig).
Diese Antwort stellt eine Modifikation des Algorithmus, ergibt sich ein gefüllter Kreis, aber einige Pixel werden mehrere Male besucht:
schneller Algorithmus für das zeichnen von gefüllten Kreisen?
Q: Wie kann ich die Option "Rastern", ein Kreis ohne Zeichnung Pixel mehrfach? Beachten Sie, dass RAM ist sehr begrenzt!
Update:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CircleTest
{
class Program
{
static void Main(string[] args)
{
byte[,] buffer = new byte[50, 50];
circle(buffer, 25, 25, 20);
for (int y = 0; y < 50; ++y)
{
for (int x = 0; x < 50; ++x)
Console.Write(buffer[y, x].ToString());
Console.WriteLine();
}
}
//'cx' and 'cy' denote the offset of the circle center from the origin.
static void circle(byte[,] buffer, int cx, int cy, int radius)
{
int error = -radius;
int x = radius;
int y = 0;
//The following while loop may altered to 'while (x > y)' for a
//performance benefit, as long as a call to 'plot4points' follows
//the body of the loop. This allows for the elimination of the
//'(x != y)' test in 'plot8points', providing a further benefit.
//
//For the sake of clarity, this is not shown here.
while (x >= y)
{
plot8points(buffer, cx, cy, x, y);
error += y;
++y;
error += y;
//The following test may be implemented in assembly language in
//most machines by testing the carry flag after adding 'y' to
//the value of 'error' in the previous step, since 'error'
//nominally has a negative value.
if (error >= 0)
{
error -= x;
--x;
error -= x;
}
}
}
static void plot8points(byte[,] buffer, int cx, int cy, int x, int y)
{
plot4points(buffer, cx, cy, x, y);
if (x != y) plot4points(buffer, cx, cy, y, x);
}
//The '(x != 0 && y != 0)' test in the last line of this function
//may be omitted for a performance benefit if the radius of the
//circle is known to be non-zero.
static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
{
#if false //Outlined circle are indeed plotted correctly!
setPixel(buffer, cx + x, cy + y);
if (x != 0) setPixel(buffer, cx - x, cy + y);
if (y != 0) setPixel(buffer, cx + x, cy - y);
if (x != 0 && y != 0) setPixel(buffer, cx - x, cy - y);
#else //But the filled version plots some pixels multiple times...
horizontalLine(buffer, cx - x, cy + y, cx + x);
//if (x != 0) setPixel(buffer, cx - x, cy + y);
//if (y != 0) setPixel(buffer, cx + x, cy - y);
//if (x != 0 && y != 0) setPixel(buffer, cx - x, cy - y);
#endif
}
static void setPixel(byte[,] buffer, int x, int y)
{
buffer[y, x]++;
}
static void horizontalLine(byte[,] buffer, int x0, int y0, int x1)
{
for (int x = x0; x <= x1; ++x)
setPixel(buffer, x, y0);
}
}
}
Hier ist das relevante Ergebnis:
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000011111111111111111111111111111111111111100000
00000011111111111111111111111111111111111111100000
00000011111111111111111111111111111111111111100000
00000001111111111111111111111111111111111111000000
00000001111111111111111111111111111111111111000000
00000000111111111111111111111111111111111110000000
00000000111111111111111111111111111111111110000000
00000000011111111111111111111111111111111100000000
00000000001111111111111111111111111111111000000000
00000000000111111111111111111111111111110000000000
00000000000011111111111111111111111111100000000000
00000000000001111111111111111111111111000000000000
00000000000000122222222222222222222210000000000000
00000000000000001222222222222222221000000000000000
00000000000000000012333333333332100000000000000000
00000000000000000000012345432100000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
Den unteren Pixeln gezeichnet werden, zu viele Male. Was vermisse ich hier?
Update #2: Diese Lösung funktioniert:
static void circle(byte[,] buffer, int cx, int cy, int radius)
{
int error = -radius;
int x = radius;
int y = 0;
while (x >= y)
{
int lastY = y;
error += y;
++y;
error += y;
plot4points(buffer, cx, cy, x, lastY);
if (error >= 0)
{
if (x != lastY)
plot4points(buffer, cx, cy, lastY, x);
error -= x;
--x;
error -= x;
}
}
}
static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
{
horizontalLine(buffer, cx - x, cy + y, cx + x);
if (y != 0)
horizontalLine(buffer, cx - x, cy - y, cx + x);
}
Meine Implementierung hält der multi-zeichnen am oberen/unteren Rand des Kreises. Vielleicht bin ich einfach nicht verstehen, die Antwort?
Warum nicht zeigen Sie uns einige code?
Bitte siehe mein update!
InformationsquelleAutor l33t | 2012-06-04
Du musst angemeldet sein, um einen Kommentar abzugeben.
Die Antwort auf die andere Frage ist völlig in Ordnung. Aber da ist es Verwirrung zu Stiften, werde ich es erklären, ein wenig.
Den Algorithmus, den Sie in der Wikipedia sehen im Grunde findet
x
undy
von 1/8 eines Kreises (Winkel 0 bispi/4
) und zieht dann 8 Punkte was sind seine Spiegel. Zum Beispiel:Was die andere Lösung schlägt vor, die macht es durchaus Sinn, wenn Sie genau hinsehen, um dieses Bild, ist stattdessen der Zeichnung 8 Punkte, Unentschieden 4 horizontale Linien:
Nun, wenn Sie berechnen
(x,y)
für die Winkel in[0, pi/4]
und ziehen diese 4 Zeilen für jeden berechneten Punkt, Sie müssen gezeichnet, viele horizontale Linien, die füllen einen Kreis ohne Linie überschneidet sich mit der anderen.Update
Der Grund, warum Sie bekommen überlappende Linien im unteren Teil des Kreises ist, dass die
(x,y)
Koordinaten sind gerundet, so dass an diesen Standorten die(x,y)
bewegen horizontal sich.Wenn man einen Blick auf wikipedia Bild:
Werden Sie bemerken, dass auf der Spitze des Kreises, einige Pixel werden horizontal ausgerichtet. Zeichnen von horizontalen Linien mit Ursprung aus diesen Punkten überschneiden.
Wenn Sie nicht wollen, dass dies die Lösung ist ganz einfach. Sie haben, um die vorherigen
x
Sie haben mit gezogen (da die oberen und unteren sind Spiegel der original(x,y)
, sollte man die vorherigen x repräsentiert die y-Linien) und nur zeichnen Sie die horizontale Linien, wenn dieser Wert sich ändert. Wenn es nicht funktioniert, es bedeutet, dass Sie auf der gleichen Linie.Angesichts der Tatsache, dass Sie wird die erste Begegnung der innersten Punkte, zeichnen Sie Linien für die vorherigen Punkt, nur der neue Punkt hat verschiedene
x
(natürlich die Letzte Linie gezeichnet wird immer). Alternativ können Sie starten, zeichnen von Winkel PI/4 nach unten auf 0, anstatt von 0 bis PI/4 und Sie wird die erste Begegnung der äußeren Punkte, daher Sie Linien zeichnen, jedes mal, wenn Sie sehen, eine neuex
.siehe mein update
Hm. Also brauche ich zwei "Vorherige Zeile" Variablen? Für 'y' und für 'x' (gespiegelt)?
Naja, so einfach ist es nicht. Um eine Linie zu zeichnen benötigen Sie das außen pixel. Und der Algorithmus nicht garantieren, dass die äußeren pixel wird zuerst besucht. Also, wenn ich die Strecke besucht Linien, einige Pixel werden vermisst.
Sie benötigen nur 1, das ist für
x
. Wir betrachten das gleiche Bild aus Wikipedia. Sie beginnen bei Winkel 0, so haben Sie(x,0)
und Sie beginnen zu gehen. Wie Sie gehen, für ein paar Pixelx
bleibt die gleiche und diey
änderungen. 2 die horizontalen Linien gezeichnet werden sowieso und die anderen beiden (gespiegelten über die Linie y = x) muss überprüft werden, ob Sie die Einführung einer horizontalen Linie. Wenn Sie das tun, werden Sie Sie zu zeichnen.InformationsquelleAutor Shahbaz
Ich brauchte, um dies zu tun, hier ist der code, den ich kam mit es. Das Bild hier zeigt die Pixel gezeichnet, wobei die Nummer die Reihenfolge, in der die Pixel, die durchquert werden, und die grünen zahlen stellen Pixel, die gezeichnet sind mit der Reflexion den Abschluss einer Spalte mithilfe von Symmetrie, wie im code gezeigt.
InformationsquelleAutor colinday
Ich kam mit einem Algorithmus, zieht der Kreis bereits gefüllt.
Er iteriert über die Pixel, die der Kreis gezeichnet werden soll und auf nichts anderes.
Ab hier ist alles über die Geschwindigkeit, mit der draw-pixel-Funktion.
Hier ein *.gif, das zeigt, was der Algorithmus tut !
Als für den Algorithmus hier ist der code :
Hoffe, das hilft ... einige neue Benutzer ... sorry für den necro-posting.
~Shmiggy
Auf x86-procs Multiplikation, division und Wurzel werden alle einzelnen Anweisungen.
Eine einzelne Instruktion, bedeutet nicht unbedingt hohe performance. Es gibt Taktzyklen zu berücksichtigen, die Präzision, die Themen -, Plattform-Unterschiede... Es macht keinen Sinn, mathematisch komplexen algorithmen (z.B. Quadratwurzel-Näherung), wenn es nicht sein muß.
InformationsquelleAutor Shmiggy
Ich wollte einen Kommentar zu Ihrem Update #2: Diese Lösung funktioniert: (aber ich denke, ich brauche mehr Ruf erst...), dass es einen kleinen Fehler in der Lösung zufällig beim zeichnen kleine Kreise. Wenn Sie den radius auf 1 setzen Sie bekommen
Um dies zu beheben alles, was Sie tun müssen, ist, ändern Sie die bedingte check-in plot4points von
zu
Ich habe getestet dieses auf kleine und große Kreise um sicherzustellen, dass jeder pixel ist immer noch nur einmal vergeben. Scheint sehr gut zu funktionieren. Mich denkt, das x != 0 wurde nicht gebraucht. Speichern Sie ein klein wenig Leistung zu.
InformationsquelleAutor Steven Ackerman
Update #2
zu
Kreis Und FillCircle version:
InformationsquelleAutor user4906579