Algoritmo de dibujo de círculos de Bresenham

No es fácil mostrar un arco suave continuo en la pantalla de la computadora, ya que la pantalla de nuestra computadora está hecha de píxeles organizados en forma de array. Entonces, para dibujar un círculo en la pantalla de una computadora, siempre debemos elegir los píxeles más cercanos de un píxel impreso para que puedan formar un arco. Hay dos algoritmos para hacer esto:

1. Algoritmo de dibujo de círculo de punto medio
2. Algoritmo de dibujo de círculos de Bresenham

Ya hemos discutido el algoritmo de dibujo circular de punto medio en nuestra publicación anterior. En esta publicación discutiremos sobre el algoritmo de dibujo circular de Bresenham. 

Ambos algoritmos utilizan la característica clave del círculo de que es altamente simétrico. Entonces, para los 360 grados del círculo, lo dividiremos en 8 partes cada octante de 45 grados. Para ello, utilizaremos el algoritmo circular de Bresenham para el cálculo de las ubicaciones de los píxeles en el primer octante de 45 grados. Asume que el círculo está centrado en el origen. Entonces, por cada píxel (x, y) que calcula, dibujamos un píxel en cada uno de los 8 octantes del círculo, como se muestra a continuación: 
 

Ahora, veremos cómo calcular la siguiente ubicación de píxel a partir de una ubicación de píxel previamente conocida (x, y). En el algoritmo de Bresenham en cualquier punto (x, y) tenemos dos opciones para elegir el siguiente píxel en el este, es decir (x+1, y) o en el sureste, es decir (x+1, y-1).
 

Y esto se puede decidir usando el parámetro de decisión d como: 
 

• Si d > 0, entonces (x+1, y-1) se elegirá como el siguiente píxel, ya que estará más cerca del arco.
• de lo contrario (x+1, y) se elegirá como el siguiente píxel.

Ahora, para dibujar el círculo para un radio dado ‘r’ y centro (xc, yc) Comenzaremos desde (0, r) y nos moveremos en el primer cuadrante hasta x=y (es decir, 45 grados). Debemos comenzar desde la condición inicial enumerada: 
 

d = 3 - (2 * r)
x = 0
y = r

Ahora para cada píxel, haremos las siguientes operaciones:  

1. Establecer valores iniciales de (xc, yc) y (x, y)
2. Establezca el parámetro de decisión d en d = 3 – (2 * r). 
    
3. llame a la función drawCircle(int xc, int yc, int x, int y).
4. Repita los pasos 5 a 8 hasta que x < = y
5. Incremento del valor de x.
6. Si d < 0, establezca d = d + (4*x) + 6
7. De lo contrario, establezca d = d + 4 * (x – y) + 10 y disminuya y en 1.
8. llama a la función dibujarCirculo(int xc, int yc, int x, int y)

función dibujarCírculo(): 

// function to draw all other 7 pixels
// present at symmetric position
drawCircle(int xc, int yc, int x, int y)
{
    putpixel(xc+x, yc+y, RED);
    putpixel(xc-x, yc+y, RED);
    putpixel(xc+x, yc-y, RED);
    putpixel(xc-x, yc-y, RED);
    putpixel(xc+y, yc+x, RED);
    putpixel(xc-y, yc+x, RED);
    putpixel(xc+y, yc-x, RED);
    putpixel(xc-y, yc-x, RED);
}

A continuación se muestra la implementación en C del enfoque anterior. 

// C-program for circle drawing
// using Bresenham’s Algorithm
// in computer-graphics
#include <stdio.h>
#include <dos.h>
#include <graphics.h>
 
// Function to put pixels
// at subsequence points
void drawCircle(int xc, int yc, int x, int y)
{
    putpixel(xc+x, yc+y, RED);
    putpixel(xc-x, yc+y, RED);
    putpixel(xc+x, yc-y, RED);
    putpixel(xc-x, yc-y, RED);
    putpixel(xc+y, yc+x, RED);
    putpixel(xc-y, yc+x, RED);
    putpixel(xc+y, yc-x, RED);
    putpixel(xc-y, yc-x, RED);
}
 
// Function for circle-generation
// using Bresenham's algorithm
void circleBres(int xc, int yc, int r)
{
    int x = 0, y = r;
    int d = 3 - 2 * r;
    drawCircle(xc, yc, x, y);
    while (y >= x)
    {
        // for each pixel we will
        // draw all eight pixels
         
        x++;
 
        // check for decision parameter
        // and correspondingly
        // update d, x, y
        if (d > 0)
        {
            y--;
            d = d + 4 * (x - y) + 10;
        }
        else
            d = d + 4 * x + 6;
        drawCircle(xc, yc, x, y);
        delay(50);
    }
}
 
 
// Driver code
int main()
{
    int xc = 50, yc = 50, r = 30;
    int gd = DETECT, gm;
    initgraph(&gd, &gm, "");  // initialize graph
    circleBres(xc, yc, r);    // function call
    return 0;
}

Producción: 
 

ventajas 

• Es un algoritmo simple.
• Se puede implementar fácilmente
• Se basa totalmente en la ecuación del círculo, es decir, x ² +y ² =r ²

Desventajas 

• Hay un problema de precisión al generar puntos.
• Este algoritmo no es adecuado para imágenes gráficas complejas y altas.

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.