¿Algoritmo rápido para dibujar círculos rellenos?

StackOverflow https://stackoverflow.com/questions/1201200

Pregunta

Estoy usando algoritmo de círculo de Bresenham para dibujar círculos rápidamente. Sin embargo, también quiero (a petición del usuario) dibujar un círculo relleno.

¿Hay una manera rápida y eficiente de hacer esto? ¿Algo parecido a Bresenham?

El lenguaje que estoy usando es C.

¿Fue útil?

Solución

Habiendo leído la página de Wikipedia en el algoritmo de círculo de Bresenham (también 'Punto Medio') , sería Parece que lo más fácil sería modificar sus acciones, de forma que en lugar de 

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

y similares, cada vez que hagas 

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

Es decir, para cada par de puntos (con el mismo y ) que Bresenham le haría a usted parcela , en cambio se conectará con una línea .

Otros consejos

Solo usa la fuerza bruta. Este método se repite en demasiados píxeles, pero solo utiliza multiplicaciones de enteros y adiciones. Evita por completo la complejidad de Bresenham y el posible cuello de botella de 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);

Aquí hay una guía aproximada de C # (no debería ser tan difícil obtener la idea correcta para C): esta es la " raw " formar sin usar Bresenham para eliminar las raíces cuadradas repetidas. 

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

Puedes usar esto: 

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

Me gusta la respuesta de palm3D. Por ser una fuerza bruta, esta es una solución sorprendentemente rápida. No hay raíz cuadrada o funciones trigonométricas para frenarla. Su única debilidad es el bucle anidado.

Convertir esto en un solo bucle hace que esta función sea casi el doble de rápida. 

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

Esta solución de bucle único compite con la eficiencia de una solución de dibujo de líneas. 

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

Así es como lo estoy haciendo:
Estoy usando valores de punto fijo con dos bits de precisión (tenemos que administrar valores de medio punto y valores cuadrados de medio punto)
Como se mencionó en una respuesta anterior, también estoy usando valores cuadrados en lugar de raíces cuadradas.
Primero, estoy detectando el límite de borde de mi círculo en una porción de 1/8 del círculo. Estoy usando la simetría de estos puntos para dibujar los 4 " bordes " del circulo. Luego estoy dibujando el cuadrado dentro del círculo.

A diferencia del algoritmo de círculo de punto medio , este funcionará con diámetros pares (y también con diámetros de números reales, con algunos pequeños cambios).

Por favor, perdóneme si mis explicaciones no fueron claras, soy francés;) 

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

Para usar un diámetro no entero, puede aumentar la precisión del punto fijo o usar valores dobles. Incluso debería ser posible hacer un tipo de anti-alias dependiendo de la diferencia entre dY2 + (ray - x) * (ray - x) y ray2 (dx² + dy² y r²)

Si quieres un algoritmo rápido, considera dibujar un polígono con N lados, cuanto más alto sea N, más preciso será el círculo.

El algoritmo de fuerza bruta de

palm3D me pareció un buen punto de partida. Este método utiliza la misma premisa, sin embargo, incluye un par de formas para omitir la comprobación de la mayoría de los píxeles.

Primero, aquí está el código: 

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

A continuación, la explicación.

Lo primero que debes tener en cuenta es que si encuentras la coordenada x mínima que está dentro del círculo para una línea horizontal dada, inmediatamente conocerás la coordenada x máxima. Esto se debe a la simetría del círculo. Si la coordenada x mínima es 10 píxeles delante de la izquierda del cuadro delimitador del círculo, entonces la máxima x es 10 píxeles detrás de la derecha del cuadro delimitador del círculo.

La razón para iterar desde valores altos de x a valores bajos de x, es que el valor mínimo de x se encontrará con menos iteraciones. Esto se debe a que el valor mínimo de x está más cerca de la izquierda del cuadro delimitador que la coordenada central del círculo para la mayoría de las líneas, debido a que el círculo está curvado hacia afuera, como se ve en esta imagen Lo siguiente que debe tener en cuenta es que, como el círculo también es simétrico verticalmente, cada línea que encuentre le brinda una segunda línea libre para dibujar, cada vez que encuentre una línea en la mitad superior del círculo, obtendrá una en la mitad inferior. la coordenada de radio y y. Por lo tanto, cuando se encuentra una línea, se pueden dibujar dos y solo la mitad superior de los valores y debe repetirse.

Lo último que se debe tener en cuenta es que si empiezas desde un valor ay que está en el centro del círculo y luego te mueves hacia la parte superior para y, entonces el valor mínimo de x para cada línea siguiente debe estar más cerca del centro Coordenada x del círculo que la última línea. Esto también se debe a que el círculo se curva más hacia el centro x el valor a medida que sube el círculo. Aquí se muestra una descripción de cómo es ese el caso.

En resumen:

  1. Si encuentra la coordenada x mínima de una línea, obtendrá la coordenada x máxima de forma gratuita.
  2. Cada línea que encuentres para dibujar en la mitad superior del círculo te da una línea gratuita en la mitad inferior del círculo.
  3. Cada coordenada x mínima tiene que estar más cerca del centro del círculo que la coordenada x anterior para cada línea cuando se itera desde la coordenada y hacia el centro.

También puede almacenar el valor de (radio * radio) y también (y * y) en lugar de calcularlos  varias veces.

Simplemente generaría una lista de puntos y luego usaría una función de dibujo de polígono para la representación.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top