Algoritmo de punto medio para elipses (circunferencias)

El algoritmo del punto medio para circunferencias es un algoritmo usado para determinar los puntos necesarios para rasterizar una circunferencia. El algoritmo se puede generalizar a curvas cónicas. Este algoritmo de punto medio se utiliza para calcular todos los puntos perimetrales de un círculo en el primer octante y luego imprimirlos junto con sus puntos de espejo en los otros octantes. Esto funciona porque un círculo es simétrico sobre su centro. De este algoritmo se deriva el algoritmo de  Bresenham.

Este algoritmo nos ayuda a medir los puntos perimetrales completos de un círculo para el primer octante. Con la ayuda de los primeros puntos octantes, podemos localizar y medir fácilmente los puntos de otros octantes. Los restantes puntos octantes son una imagen especular de los primeros puntos octantes.

En computación gráfica, este algoritmo se utiliza para definir las coordenadas necesarias para rasterizar el círculo. La generalización de las secciones cónicas se simplifica con el algoritmo de dibujo de círculos de punto medio. El algoritmo de dibujo de círculos de punto medio también se utiliza para derivar el algoritmo de dibujo de círculos de Bresenham.

Explicación breve del algoritmo de punto medio

Este algoritmo dibuja los ocho octantes simultáneamente, a partir de cada dirección cardinal (0°, 90°, 180°, 270°) y se extiende en ambos sentidos para llegar al múltiplo más cercano de 45° (45°, 135°, 225°, 315°). Puede determinar dónde parar porque cuando y = x, ha alcanzado 45°. La razón para usar estos ángulos se muestra en la imagen de arriba: A medida que y aumenta, no salta ni repite ningún valor y hasta alcanzar 45°. Así que durante el bucle while, y aumenta por 1 cada iteración, y x decrementos por 1 en ocasiones, nunca superando 1 en una iteración. Esto cambia a 45° porque ese es el punto donde la tangente es rise=run. Mientras que rise>run antes y rise<run después.

Proceso Matemático

Una circunferencia se define como un conjunto de puntos que se encuentran, en su totalidad, a una distancia determinada r de una posición central.

Es posible reducir el cálculo al considerar la simetría de las circunferencias, la forma de la circunferencia es similar entre cuadrantes y simétrica entre octantes.

Para aplicar el método del punto medio, definimos una función de circunferencia como:

pk = fcircunferencia(x,y)= x2 + y2 − r2

fcircunferencia(x,y)<0 si (x,y) está dentro de la frontera de la circunferencia.

fcircunferencia(x,y)=0 si (x,y) está en la frontera de la circunferencia.

fcircunferencia(x,y)>0 si (x,y) está fuera de la frontera de la circunferencia.

Los parámetros de decisión sucesivos se obtienen al utilizar cálculos incrementales.

¿Cómo funciona el algoritmo de punto medio? 

El algoritmo de punto medio se encarga de determinar los pixels que habría que encender en el segundo octante utilizando para ello solo aritmética entera. Para cualquier tipo de algoritmo de generación de círculos, la simetría del círculo se puede utilizar para reducir la cantidad de cálculos. El círculo con centro en el origen tiene cuatro ejes de simetría, que son: 

x = 0, y= 0, y = x,  y = – x

Si se conoce algún punto P (x, y) en la circunferencia, entonces se conocerán los otros siete. Los puntos de simetría en la circunferencia se pueden obtener mediante cuatro ejes de simetría, que son (y, x), (-x,y), (x, -y), (y, -x), (-y, x), (-x, -y), (-y, -x), esta propiedad se llama simetría octante del círculo.

x comienza entonces con el valor de 0,  y con el valor de R, se procede entonces incrementando x de uno en uno, en ese octante, y tiene solo dos posibilidades, se decrementa o mantiene su valor.

Ventajas

• Consume pocos recursos en los ordenadores.
• Es el algoritmo más simple de implementar.
• No requiere de muchos conocimientos.
• Es un método rápido para calcular la posición de un pixel.

Desventajas

• La complejidad de las fórmulas, en grandes funciones, reducen la velocidad de visualización.
• No es capaz de procesar algunas características de imagen (líneas cruzadas).

Autor: Juan Sebastián Martínez Martínez, Natalia Ramírez, Juan Pablo Quiroz, Carlos Alberto Sarmiento, Carlos Ivan Sanchez

Editor: Carlos Iván Pinzón

Código: UCCG-9

Universidad: Universidad Central

Información tomada de:

Midpoint circle algorithm. (4 de Febrero de 2021). En Wikipedia

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Admin. (2020). Midpoint Circle Drawing Algorithm in Computer Graphics. Tutorial and example

https://www.tutorialandexample.com/midpoint-circle-drawing-algorithm/

Psiĥedelisto. (2018). Concentric circles drawn with Bresenham’s circle algorithm (all black) [Imagen]. En Wikipedia

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Psiĥedelisto. (2018). Concentric circles drawn with Bresenham’s circle algorithm [Imagen]. En Wikipedia

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Geeks for Geeks. (2020). Mid-Point Circle Drawing Algorithm. GeeksforGeeks

https://www.geeksforgeeks.org/mid-point-circle-drawing-algorithm/