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/