Algoritmo del Punto Medio para Elipses

Plantilla:Acerca de

Introducción

Una elipse se define como el conjunto de puntos en que la suma de las distancias desde dos posiciones fijas sea la misma para todos los puntos. Una elipse en posición estandar es simetrica entre cuadrantes.

Para aplicar el método del punto medio, definimos una función de elipse como: p_k = f_elipse(x,y)= r_y²x²+r_x²y²-r_x²r_y²

f_elipse(x,y)<0 si (x,y) está dentro de la frontera de la elipse.

f_elipse(x,y)=0 si (x,y) está en la frontera de la elipse.

f_elipse(x,y)>0 si (x,y) está fuera de la frontera de la elipse.

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

Algoritmo

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 incial del parametro de decisión de la región 1 como p10=ry2-rx2ry+ 0.25 rx2.
 *En cada posicion xk en la region 1 para k=0
    Si p1k<0 
       Punto siguiente = (xk+1, yk)
       p1k+1=p1k+2ry2xk+1+ry2
 *Se calcula el valor incial del parametro de decisión de la región 2 utilizando el último (x0,y0)
calculado en la región 1 como p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2.
 *En cada posicion yk en la region 2 para k=0
    Si p2k>0 
       Punto siguiente = (xk, yk-1)
       p2k+1=p2k-2rx2yk+1+rx2
 *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 region 1 hasta que 2ry2x0 >=2rx2y0

Rendimiento

Código Ejemplo Java

Ejemplo:

public void Elipse(Graphics g, int xc, int yc, int rx, int ry){
 int x, y, p, px, py;
 int rx2, ry2, tworx2, twory2;
 ry2 = ry*ry;
 rx2 = rx*rx;
 twory2 = 2 * ry2;
 tworx2 = 2 * rx2;
/* región 1 */
 x = 0;
 y = ry;
 PlotPoint(x,y);
 p = (int)Math.round(ry2 - rx2*ry + 0.25*rx2);
 px = 0;
 py = tworx2*y;
 while (px < py) { /* se cicla hasta trazar la región 1 */
   x = x + 1;
   px = px + twory2;
   if (p < 0)
     p = p + ry2 + px;
   else {
     y = y - 1;
     py = py - tworx2;
     p = p + ry2 + px - py;
   }
   PlotPoint(x,y);
 }
/* región 2 */
 p = (int)Math.round(ry2*(x+0.5)*(x+0.5) + rx2*(y-1)*(y-1) - rx2*ry2);
 px = 0;
 py = tworx2*y;
 while (y > 0) { /* se cicla hasta trazar la región 2 */
   y = y - 1;
   py = py - tworx2;
   if (p > 0)
     p = p + rx2 - py;
   else {
     x = x + 1;
     px = px + twory2;
     p = p + rx2 + py + px;
   }
   PlotPoint(x,y);
 }
}

Código Ejemplo en C

Ejemplo en código C:

#include<stdio.h>
#include<graphics.h>
#include<math.h>
#include<conio.h>
void main()
 {
   float x,y,rx2,ry2,p1,p2;
   int xc,yc,gm,gd=DETECT,rx,ry;
   printf("ENTER RX AND RY:");
   scanf("%d %d",&rx,&ry);
   printf("ENTER THE CO-ORDINATES OF THE CENTER:");
   scanf("%d %d",&xc,&yc);
   initgraph(&gd,&gm," ");
   putpixel(xc,yc,15);
   x=0;
   y=ry;
   rx2=pow(rx,2);
   ry2=pow(ry,2);
   p1=ry2-(rx2*ry)+(0.25*rx2);
   while((ry2*x)<(rx2*y))
      {
      if(p1<0)
         { x++;
           p1=p1+(2*ry2*x)+ry2;
         }
      else
         {
           x++; y--;
           p1=p1+(2*ry2*x)-(2*rx2*y)+ry2;
         }
      putpixel(xc+x,yc+y,15);
      putpixel(xc-x,yc+y,15);
      putpixel(xc+x,yc-y,15);
      putpixel(xc-x,yc-y,15);
      }
   p2=(ry2)*pow((x+0.5),2)+(rx2)*pow((y-1),2)-(rx2*ry2);
   while(y>0)
      {
         if (p2>0)
         {
           y--;
           p2=p2-(2*rx2*y) +rx2;
         }
         else
         {
           x++; y--;
           p2=p2+ (2*ry2*x)-(2*rx2*y)+rx2;
         }
         putpixel(xc+x,yc+y,15);
         putpixel(xc-x,yc+y,15);
         putpixel(xc+x,yc-y,15);
         putpixel(xc-x,yc-y,15);
      }
   getch();
   closegraph();
}

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