Ir al contenido

Algoritmo del punto medio para circunferencias

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 01:29 31 jul 2013 por CEM-bot (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.

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 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 simetrica entre octantes.

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

pk = fcircunferencia(x,y)=

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.

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 inicial 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

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
Obtenido de «https://es.wikipedia.org/w/index.php?title=Algoritmo_del_punto_medio_para_circunferencias&oldid=68725008»