Ik gebruik Bresenham’s cirkelalgoritmevoor het tekenen van snelle cirkels. Ik wil echter ook (op verzoek van de gebruiker) een gevulde cirkel tekenen.
Is er een snelle en efficiënte manier om dit te doen? Iets in de trant van Bresenham?
De taal die ik gebruik is C.
Antwoord 1, autoriteit 100%
Na het lezen van de Wikipedia-pagina over Bresenham’s (ook ‘Midpoint’) cirkelalgoritme, zou het lijkt het gemakkelijkst om zijn acties aan te passen, zodat in plaats van
setPixel(x0 + x, y0 + y);
setPixel(x0 - x, y0 + y);
en soortgelijk, elke keer dat je in plaats daarvan doet
lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);
Dat wil zeggen, voor elk paar punten (met dezelfde y) die Bresenham u wilt hebben plot, u verbindt met een lijnsterk>.
Antwoord 2, autoriteit 76%
Gebruik gewoon brute kracht. Deze methode herhaalt een paar pixels te veel, maar gebruikt alleen vermenigvuldigingen en optellingen met gehele getallen. Je vermijdt volledig de complexiteit van Bresenham en de mogelijke bottleneck van 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);
Antwoord 3, autoriteit 30%
Hier is een ruwe handleiding voor C# (het zou niet zo moeilijk moeten zijn om het juiste idee voor C te krijgen) – dit is de “onbewerkte” vorm zonder Bresenham te gebruiken om herhaalde vierkantswortels te elimineren.
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");
Antwoord 4, autoriteit 15%
U kunt dit gebruiken:
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;
}
}
}
Antwoord 5, autoriteit 12%
Ik vind het antwoord van palm3D goed. Omdat het brute kracht is, is dit een verbazingwekkend snelle oplossing. Er zijn geen vierkantswortel of trigonometrische functies om het te vertragen. Zijn enige zwakte is de geneste lus.
Door dit te converteren naar een enkele lus, wordt deze functie bijna twee keer zo snel.
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);
}
Deze oplossing met één lus evenaart de efficiëntie van een lijntekeningoplossing.
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);
}
Antwoord 6, autoriteit 10%
Groot-ideeën hier!
Sinds ik ben op een project dat vele duizenden kringen te trekken vereist, heb ik alle suggesties hier geëvalueerd (en een paar verbeterd door precomputing het kwadraat van de straal):
http://quick-bench.com/mwTOodNOI81k1ddaTCGH_Cmn_Ag
The Rev varianten gewoon x en y verwisseld omdat opeenvolgende toegang langs de y-as sneller met de manier waarop mijn rooster / canvas structuur werken zijn.
De duidelijke winnaar is Earwicker methode Daniel’s (DrawCircleBruteforcePrecalc) de Y-waarde onnodig straal controles worden voorkomen precomputes. Enigszins verrassend dat ontkent de aanvullende berekening wordt veroorzaakt door de wortel gesprek.
Sommigen stellen voor de kmillen’s variant (DrawCircleSingleLoop) die werkt met een enkele lus zeer snel moeten zijn, maar het is de langzaamste hier. Ik neem aan dat is omdat van alle divisies. Maar misschien heb ik aangepast het verkeerd om de globale variabelen in die code. Zou geweldig zijn als iemand een kijkje neemt.
EDIT: Na het kijken voor het eerst sinds college jaar op een bepaald assembler code, slaagde ik erin vinden dat de laatste toevoegingen van de oorsprong van de cirkel zijn een boosdoener.
Precomputing die ik verbeterde de snelste methode met een factor van een ander 3,7-3,9 volgens de bank!
http://quick-bench.com/7ZYitwJIUgF_OkDUgnyMJY4lGlA
Geweldig.
Dit was mijn code:
for (int x = -radius; x < radius ; x++)
{
int hh = (int)std::sqrt(radius_sqr - x * x);
int rx = center_x + x;
int ph = center_y + hh;
for (int y = center_y-hh; y < ph; y++)
canvas[rx][y] = 1;
}
Antwoord 7, Autoriteit 6%
palm3D’s brute-force algoritme vond ik een goed uitgangspunt zijn. Deze werkwijze maakt gebruik van dezelfde veronderstelling, maar het bevat een aantal manieren om controle overslaan meeste pixels.
Ten eerste, hier is de 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
}
}
}
Vervolgens wordt de toelichting.
Het eerste wat opvalt, is dat als je de minimale x-coördinaat die binnen de cirkel voor een gegeven horizontale lijn, weet je meteen de maximale x-coördinaat.
Dit komt door de symmetrie van de cirkel. Als de minimale x-coördinaat 10 pixels vóór het verlaten van het begrenzingskader van de cirkel, dan is de maximale x 10 pixels achter rechts van het begrenzingskader van de cirkel.
De reden itereren van hoog x waarden lage waarden x, is dat de minimale waarde x wordt gevonden met minder iteraties. Dit komt omdat de minimale waarde x dichter bij de linkerzijde van het kader dan het midden x-coördinaat van de cirkel voor de meeste lijnen, als gevolg van de cirkel naar buiten worden gebogen, zoals te zien op dit beeld
Het volgende wat op te merken is dat sinds de cirkel is ook verticaal symmetrisch, elke lijn vind je geeft je een gratis tweede lijn te trekken, elke keer dat u een lijn in de bovenste helft van de cirkel te vinden, krijg je er een op de onderste helft op de radius-y y-coördinaat. Daarom, wanneer een lijn wordt gevonden, twee kunnen worden getrokken en alleen de bovenste helft van de y-waarden moet worden herhaald op.
Het laatste om op te merken is dat als je begint met een y-waarde in het midden van de cirkel en dan naar de top gaat voor y, de minimale x-waarde voor elke volgende regel dichter bij het midden moet liggen x-coördinaat van de cirkel dan de laatste regel. Dit is ook te wijten aan het feit dat de cirkel dichter naar de middelste x-waarde buigt als je de cirkel opgaat. Hier is een visuele weergave van hoe dat het geval is.
Samengevat:
- Als je de minimale x-coördinaat van een lijn vindt, krijg je de maximale x-coördinaat gratis.
- Elke lijn die je vindt om op de bovenste helft van de cirkel te tekenen, geeft je gratis een lijn op de onderste helft van de cirkel.
- Elke minimale x-coördinaat moet dichter bij het middelpunt van de cirkel liggen dan de vorige x-coördinaat voor elke lijn bij het doorlopen van de middelste y-coördinaat naar de top.
Je kunt ook de waarde van (radius * radius)opslaan, en ook (y * y)in plaats van ze te berekenen
meerdere keren.
Antwoord 8, autoriteit 4%
Zo doe ik het:
Ik gebruik vaste-puntwaarden met een precisie van twee bits (we moeten halve punten en kwadraten van halve punten beheren)
Zoals vermeld in een eerder antwoord, gebruik ik ook vierkantswaarden in plaats van vierkantswortels.
Ten eerste detecteer ik de grens van mijn cirkel in een 1/8e deel van de cirkel. Ik gebruik symmetrische van deze punten om de 4 “randen” van de cirkel te tekenen. Dan teken ik het vierkant binnen de cirkel.
In tegenstelling tot het middelpuntcirkelalgoritme, werkt deze met even diameters (en ook met reële getallendiameters, met enkele kleine veranderingen).
Vergeef me als mijn uitleg niet duidelijk was, ik ben Frans 😉
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);
}
Om de diameter niet-gehele getal te gebruiken, kunt u de precisie van het vaste punt verhogen of dubbele waarden gebruiken.
Het zou zelfs mogelijk moeten zijn om een soort anti-alias te maken, afhankelijk van het verschil tussen DY2 + (Ray – X) * (Ray – X) en Ray2 (DX² + DY² en R²)
Antwoord 9, Autoriteit 2%
Als u een snel algoritme wilt, overweeg dan een polygoon met N-zijden te trekken, hoe hoger is, hoe nauwkeuriger de cirkel is.
Antwoord 10
Ik zou gewoon een lijst met punten genereren en vervolgens een Polygon Draw-functie gebruiken voor het weergeven.
Antwoord 11
Het is misschien niet het algoritme dat u op zoek bent naar en niet de meest performante,
Maar ik doe altijd zoiets:
void fillCircle(int x, int y, int radius){
// fill a circle
for(int rad = radius; rad >= 0; rad--){
// stroke a circle
for(double i = 0; i <= PI * 2; i+=0.01){
int pX = x + rad * cos(i);
int pY = y + rad * sin(i);
drawPoint(pX, pY);
}
}
}
Antwoord 12
De volgende twee methoden vermijden de herhaalde vierkante wortelberekening door meerdere delen van de cirkel tegelijk te tekenen en moet daarom vrij snel zijn:
void circleFill(const size_t centerX, const size_t centerY, const size_t radius, color fill) {
if (centerX < radius || centerY < radius || centerX + radius > width || centerY + radius > height)
return;
const size_t signedRadius = radius * radius;
for (size_t y = 0; y < radius; y++) {
const size_t up = (centerY - y) * width;
const size_t down = (centerY + y) * width;
const size_t halfWidth = roundf(sqrtf(signedRadius - y * y));
for (size_t x = 0; x < halfWidth; x++) {
const size_t left = centerX - x;
const size_t right = centerX + x;
pixels[left + up] = fill;
pixels[right + up] = fill;
pixels[left + down] = fill;
pixels[right + down] = fill;
}
}
}
void circleContour(const size_t centerX, const size_t centerY, const size_t radius, color stroke) {
if (centerX < radius || centerY < radius || centerX + radius > width || centerY + radius > height)
return;
const size_t signedRadius = radius * radius;
const size_t maxSlopePoint = ceilf(radius * 0.707106781f); //ceilf(radius * cosf(TWO_PI/8));
for (size_t i = 0; i < maxSlopePoint; i++) {
const size_t depth = roundf(sqrtf(signedRadius - i * i));
size_t left = centerX - depth;
size_t right = centerX + depth;
size_t up = (centerY - i) * width;
size_t down = (centerY + i) * width;
pixels[left + up] = stroke;
pixels[right + up] = stroke;
pixels[left + down] = stroke;
pixels[right + down] = stroke;
left = centerX - i;
right = centerX + i;
up = (centerY - depth) * width;
down = (centerY + depth) * width;
pixels[left + up] = stroke;
pixels[right + up] = stroke;
pixels[left + down] = stroke;
pixels[right + down] = stroke;
}
}