Algoritmo del Punto Medio para Circunferencias

Plantilla:Acerca de

Introducción

Una circunferencia se define como un conjunto de puntos que se encuentran, en su totalidad, a una distancia determinada r de una posicion 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 simetrica entre octantes.

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

p_k = f_{circunferencia}(x,y)= x² + y² − r²

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

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

f_{circunferencia}(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.

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 cacula el valor incial del parametro 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

Rendimiento

Código Ejemplo Java

Ejemplo:

void CircleMidPoint(Graphics g, int xc, int yc, int r){
  int x, y, p;
  x = 0;
  y = r;
  p = 1 - r;
  PlotPoint(g,xc,yc,x,y);
  /* se cicla hasta trazar todo un octante */
  while (x < y){
    x = x + 1;
    if (p < 0)
      p = p + 2*x + 1;
    else {
      y = y - 1;
      p = p + 2*(x - y) + 1;
    }
    PlotPoint(g,xc,yc,x,y);
  }}

Véase también

• Analizador Diferencial Digital (algoritmo gráfico) es un algoritmo para el trazado de lineas.
• Algoritmo de Bresenham es un algoritmo para el trazado de lineas.
• Algoritmo de Xiaolin Wu es un algoritmo para antialiasing de lineas.
• Algoritmo del Punto Medio para Elipses es un algoritmo para el trazado de cónicas.
• Algoritmo del Punto Medio para Parábolas es un algoritmo para el trazado de cónicas.
• Algoritmo del Punto Medio para Hipérbolas es un algoritmo para el trazado de cónicas.

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