algoritmo rápido para desenhar círculos preenchidos?

https://stackoverflow.com/questions/1201200

05-07-2019
|

Pergunta

Eu estou usando o Bresenham algoritmo círculo para o desenho rápido círculo. No entanto, eu também quero (a pedido do usuário) desenhar um círculo preenchido.

Existe uma maneira rápida e eficiente de fazer isso? Algo ao longo das mesmas linhas de Bresenham?

A linguagem que estou usando é C.

Solução

Depois de ler a página da Wikipedia sobre Bresenham do (também 'Ponto médio') algoritmo círculo , seria parece que a melhor coisa a fazer seria a de modificar suas ações, de modo que em vez de

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

e similares, cada vez que você em vez fazer

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

Ou seja, para cada par de pontos (com o mesmo y) que Bresenham você teria que você plot , você ao invés conexão com uma linha .

Outras dicas

usar apenas a força bruta. Este método interage sobre alguns muitos pixels, mas só usa inteiro multiplicações e adições. Você evitar completamente a complexidade do Bresenham ea possível gargalo 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);

Aqui está um guia C # (não deve ser tão difícil conseguir a idéia certa para C) -. Esta é a forma "bruta" sem usar Bresenham para eliminar quadrados raízes 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");

Você pode usar este:

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

Eu gosto de resposta de palm3D. Por ser a força bruta, esta é uma solução incrivelmente rápido. Não existam raiz quadrada ou funções trigonométricas para retardá-lo. Sua única fraqueza é o loop aninhado.

Convertendo isso para um único laço faz esta função quase duas vezes mais rápido.

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 solução de espira único rivaliza com a eficiência de uma solução de desenho de linha.

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

Aqui está como eu estou fazendo isso:
Estou usando valores de ponto fixo com precisão dois bits (temos de gerir meia pontos e valores quadrados de meia pontos)
Como mencionada em uma resposta anterior, eu também estou usando valores quadrados em vez de raízes quadradas.
Em primeiro lugar, estou detectando limite de fronteira do meu círculo em um / 8th parte do círculo 1. Estou usando symetric destes pontos para desenhar os 4 "fronteiras" do círculo. Então eu estou desenhando o quadrado dentro do círculo.

Ao contrário do círculo ponto médio algorith , este irá trabalhar com diâmetros até mesmo (e com números diâmetros real também, com algumas pequenas alterações).

Por favor, perdoe-me se as minhas explicações não eram claras, eu sou 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 diâmetro não inteiro, você pode aumentar a precisão de ponto fixo ou usar valores double. Deve ainda ser possível fazer uma espécie de anti-Alias, dependendo da diferença entre dY2 + (raio - x) * (raio - x) e ray2 (dx² + dy² e r²)

Se você quer um algoritmo rápido, considere desenhar um polígono com N faces, maior é N, o mais preciso será o círculo.

algoritmo de força bruta do palm3D eu encontrei para ser um bom ponto de partida. Este método usa a mesma premissa, no entanto, inclui um par de maneiras de pular a verificação maioria dos pixels.

Em primeiro lugar, aqui está o 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 seguir, a explicação.

A primeira coisa a notar é que se você encontrar o mínimo coordenada x que está dentro do círculo para uma determinada linha horizontal, você sabe imediatamente o máximo coordenada x. Isto é devido à simetria do círculo. Se a coordenada X mínima é de 10 pixels à frente da esquerda da caixa delimitadora do círculo, então o máximo de x é de 10 pixels por trás da direita da caixa delimitadora do círculo.

A razão para iterate de altos valores de x para valores baixos x, é que o valor mínimo x será encontrada com menos iterações. Isso ocorre porque o valor mínimo x está mais perto para a esquerda da caixa delimitadora do que o centro coordenada x do círculo para a maioria das linhas, devido ao círculo sendo uma curvatura para fora, como visto em esta imagem A próxima coisa a notar é que, desde o círculo também é simétrica verticalmente, cada linha que você encontrar lhe dá uma segunda linha livre para desenhar, cada vez que você encontrar uma linha na metade superior do círculo, você obter um na metade inferior em o raio-y coordenada y. Portanto, quando qualquer linha for encontrada, dois podem ser desenhadas e apenas a parte superior da metade das necessidades valores y a ser iterada.

A última coisa a notar é que é que se você começar a partir de ay valor que está no centro do círculo e, em seguida, avançar para o topo de y, então o valor mínimo x para cada linha seguinte deve ser mais perto do centro coordenada x do círculo do que a última linha. Isso também se deve ao círculo curva mais perto para o valor central x que você vá até o círculo. Aqui é um visual sobre como esse é o caso.

Em resumo:

Se você encontrar a coordenada X mínima de uma linha, você começa a máxima coordenada x gratuitamente.
Cada linha que você encontrar para desenhar na metade superior do círculo dá-lhe uma linha na metade inferior do círculo de graça.
Cada coordenada X mínima tem de estar mais perto do centro do círculo do que os anteriores x coordenadas para cada linha quando a iteração do centro coordenada y para o topo.

Você também pode armazenar o valor de (radius * radius), e também (y * y) em vez de calculá-los várias vezes.

Gostaria apenas de gerar uma lista de pontos e, em seguida, usar uma função polígono sorteio para a renderização.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow