Algoritmo del punto medio para circunferencias
En computación gráfica, 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.

Funcionamiento 

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

Entonces:

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

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

 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.

Algoritmo 
El algoritmo será el siguiente:

  *Se capturan el radio r y el centro de la circunferencia (xc, yc).
  *Se obtiene el primer punto de la circunferencia centrada en origen (xc, yc) como (0, r).
  *Se calcula el valor inicial del parámetro de decisión como p0=5/4 - r.
  Para k=0 hasta x>=y incrementa k
     Si pk < 0 
        *Siguiente punto de la circunferencia con centro (0,0) es (xk+1, yk).
        *pk+1=pk+2xk+1+1.
     Sino
         *Siguiente punto de la circunferencia con centro (0,0) es (xk+1, yk-1).
        *pk+1=pk+2xk+1+1-2yk+1.
     //Donde 2xk+1=2xk+2  y  2yk+1=2yk-2
  
  *Se determinan los puntos de simetría para los otros siete octantes.
  *Se mueve cada posición del pixel calculada (x,y) a la trayectoria circular centrada en (xc, yc) 
    y trazamos los valores de las coordenadas: x=x+xc y y=y+yc.
  Fin Para

Generalizaciones 

El algoritmo se puede generalizar a otras secciones cónicas, como pueden ser elipses y parábolas. Por ejemplo, para la elipse, que se define como conjunto de puntos en que la suma de las distancias desde dos posiciones fijas sea la misma para todos los puntos, simplemente se tiene que cambiar la definición de la fórmula, 

teniendo en cuenta que la elipse en posición estándar es simétrica entre cuadrantes. Las condiciones de frontera son las mismas que en el caso de la circunferencia y los parámetros de decisión sucesivos se obtienen al utilizar cálculos incrementales. 

De esta manera el algoritmo será el siguiente:

  *Se capturan los radios rx, ry y el centro de la elipse (xc, yc).
  *Se obtiene el primer punto de la elipse centrada en origen (xc, yc) como (0, ry).
  *Se calcula el valor inicial del parámetro de decisión de la región 1 como p10=ry-rxry+ 0.25 rx.
  *En cada posición xk en la región 1 para k=0
     Si p1k<0 
        Punto siguiente = (xk+1, yk)
        p1k+1=p1k+2ryxk+1+ry
  *Se calcula el valor inicial del parámetro de decisión de la región 2 utilizando el último (x0,y0)
 calculado en la región 1 como p20=ry(x0+0.5)+rx(y0-1)-rxry.
  *En cada posición yk en la región 2 para k=0
     Si p2k>0 
        Punto siguiente = (xk, yk-1)
        p2k+1=p2k-2rxyk+1+rx
  *Se determinan los puntos de simetría para los otros tres cuadrantes.
  *Se mueve cada posición del pixel calculada (x,y) a la trayectoria elíptica centrada en (xc, yc) 
   y trazamos los valores de las coordenadas: x=x+xc y x=x+xc.
  *Se repiten los pasos de la región 1 hasta que 2ry2x0 >=2rx2y0

Véase también 
 Analizador Diferencial Digital (algoritmo gráfico) es un algoritmo para el trazado de líneas.
 Algoritmo de Bresenham es un algoritmo para el trazado de líneas.
 Algoritmo de Xiaolin Wu es un algoritmo para antialiasing de líneas.

Referencias 
Algoritmos para dibujar Cónicas del Sitio web de Héctor E. Medellín Anaya
http://galia.fc.uaslp.mx/~medellin/Applets/Circulos/circulos.htm 

Apuntes de Informática Gráfica Uned por Omega.

Publicaciones 
 Alan Watt: 3D Computer Graphics, 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9

Enlaces externos 

Algoritmos de computación gráfica
Algoritmos geométricos
Infografía
En computación gráfica , 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 . Funcionamiento 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 Entonces : si ( x,y ) está dentro de la frontera de la circunferencia . si ( x,y ) está en la frontera de la circunferencia . 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 . Algoritmo El algoritmo será el siguiente : *Se capturan el radio r y el centro de la circunferencia ( xc , yc ) . *Se obtiene el primer punto de la circunferencia centrada en origen ( xc , yc ) como r ) . *Se calcula el valor inicial del parámetro de decisión como p0=5/4 - r . Para k=0 hasta x>=y incrementa k Si pk < *Siguiente punto de la circunferencia con centro0 ) es ( xk+1 , yk ) . *pk+1=pk+2xk+1+1 . Sino *Siguiente punto de la circunferencia con centro0 ) es ( xk+1 , yk-1 ) . *pk+1=pk+2xk+1+1-2yk+1 . //Dondek+1=2xk+2 y k+1=2yk-2 *Se determinan los puntos de simetría para los otros siete octantes . *Se mueve cada posición del pixel calculada ( x,y ) a la trayectoria circular centrada en ( xc , yc ) y trazamos los valores de las coordenadas : x=x+xc y y=y+yc . Fin Para Generalizaciones El algoritmo se puede generalizar a otras secciones cónicas , como pueden ser elipses y parábolas . Por ejemplo , para la elipse , que se define como conjunto de puntos en que la suma de las distancias desde dos posiciones fijas sea la misma para todos los puntos , simplemente se tiene que cambiar la definición de la fórmula , teniendo en cuenta que la elipse en posición estándar es simétrica entre cuadrantes . Las condiciones de frontera son las mismas que en el caso de la circunferencia y los parámetros de decisión sucesivos se obtienen al utilizar cálculos incrementales . De esta manera el algoritmo será el siguiente : *Se capturan los radios rx , ry y el centro de la elipse ( xc , yc ) . *Se obtiene el primer punto de la elipse centrada en origen ( xc , yc ) como ry ) . *Se calcula el valor inicial del parámetro de decisión de la regióncomo p10=ry-rxry+25 rx . *En cada posición xk en la regiónpara k=0 Si p1k<0 Punto siguiente = ( xk+1 , yk ) p1k+1=p1k+2ryxk+1+ry *Se calcula el valor inicial del parámetro de decisión de la regiónutilizando el último ( x0,y0 ) calculado en la regióncomo p20=ry( x0+0.5) +rx( y0-1) -rxry . *En cada posición yk en la regiónpara k=0 Si p2k>0 Punto siguiente = ( xk , yk-1 ) p2k+1=p2k-2rxyk+1+rx *Se determinan los puntos de simetría para los otros tres cuadrantes . *Se mueve cada posición del pixel calculada ( x,y ) a la trayectoria elíptica centrada en ( xc , yc ) y trazamos los valores de las coordenadas : x=x+xc y x=x+xc . *Se repiten los pasos de la regiónhasta quey2x0 >=2rx2y0 Vea se también Analizador Diferencial Digital ( algoritmo gráfico ) es un algoritmo para el trazado de líneas . Algoritmo de Bresenham es un algoritmo para el trazado de líneas . Algoritmo de Xiaolin Wu es un algoritmo para antialiasing de líneas . Referencias Algoritmos para dibujar Cónicas del Sitio web de Héctor E. Medellín Anaya http://galia.fc.uaslp.mx/ ~medellin/Applets/Circulos/circulos.htm Apuntes de Informática Gráfica Uned por Omega . Publicaciones Alan Watt : Computer Graphics,d edition p . 184 ( Rasterizing edges ) . ISBN39855-9 Enlaces externos Algoritmos de computación gráfica Algoritmos geométricos Infografía