veloce algoritmo per disegnare cerchi pieni?

Question

Sto usando Bresenham's circle algorithm per il disegno circolare veloce. Tuttavia, voglio anche (su richiesta dell'utente) disegnare un cerchio pieno.

Esiste un modo rapido ed efficiente di fare questo? Qualcosa sulla stessa linea di Bresenham?

Il linguaggio che sto usando è C.

Answer 1

Letta the Wikipedia page on Bresenham's (also 'Midpoint') circle algorithm, sembrerebbe che la cosa più semplice da fare sarebbe quella di modificare le sue azioni, in modo tale che invece di

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

e simili, ogni volta che invece di fare

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

Cioè, per ogni coppia di punti (con lo stesso) che Bresenham vorresti avere il tuo trama, tu invece connetterti con una linea.

Answer 2

Ecco una C# guida approssimativa (non dovrebbe essere così difficile da ottenere l'idea giusta per C) - questa è la forma "grezza" senza utilizzare Bresenham per eliminare ripetuto radici quadrate.

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

Answer 3

Vorrei solo generare un elenco di punti e quindi utilizzare una funzione di disegno poligono per il rendering.

Answer 4

Basta usare la forza bruta. Questo metodo esegue iterazioni su alcuni troppi pixel, ma utilizza solo moltiplicazioni e aggiunte integer. Eviti completamente la complessità di Bresenham e il possibile collo di bottiglia di 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); 

Answer 5

Se si desidera un algoritmo veloce, considerano disegnare un poligono con N lati, più alto è N, il più preciso sarà il cerchio.

Answer 6

Ecco come lo sto facendo:
sto usando i valori a virgola fissa con due bit di precisione (dobbiamo gestire punti e mezzo e valori quadrati di punti e mezzo)
Come citato in una risposta precedente, I' m usando anche valori quadrati invece di radici quadrate.
Per prima cosa, sto rilevando il limite di confine del mio cerchio in una 1/8 della circonferenza. Sto usando simmetrico di questi punti per disegnare i 4 "bordi" del cerchio. Poi sto disegnando il quadrato all'interno del cerchio.

A differenza del cerchio punto medio algoritmo, questo funzionerà anche con diametri (e con numeri reali diametri anche, con alcune piccole modifiche).

prego di perdonarmi se le mie spiegazioni non erano chiari, io sono francese;)

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

Per utilizzare diametro non intero, è possibile aumentare la precisione del punto fisso o utilizzare i valori doppi. Dovrebbe essere possibile creare una sorta di anti-alias a seconda della differenza tra dY2 + (ray-x) * (ray-x) e ray2 (dx² + dy² e r²)

Answer 7

È possibile utilizzare questo:

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

Answer 8

Mi piace la risposta di palm3D. Per essere la forza bruta, questa è una soluzione incredibilmente veloce. Non ci sono funzioni radice quadrata o trigonometrica per rallentarlo. La sua unica debolezza è il ciclo annidato.

La conversione di questo in un loop singolo rende questa funzione quasi due volte più veloce.

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

Questa soluzione a ciclo singolo rivaleggia con l'efficienza di una soluzione di disegno a tratteggio.

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