Algoritmos geométricos

Algoritmo del punto medio para circunferencias

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:

p_k = f_{circunferencia}(x,y)= $x^{2}+y^{2}-r^{2}$

f_{circunferencia}(x,y)<0 b=""> 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 (x_c, y_c).
 *Se obtiene el primer punto de la circunferencia centrada en origen (x_c, y_c) como (0, r).
 *Se calcula el valor inicial del parámetro de decisión como p₀=5/4 - r.
 Para k=0 hasta x>=y incrementa k
    Si p_k < 0 
       *Siguiente punto de la circunferencia con centro (0,0) es (x_k+1, y_k).
       *p_k+1=p_k+2x_k+1+1.
    Sino
        *Siguiente punto de la circunferencia con centro (0,0) es (x_k+1, y_k-1).
       *p_k+1=p_k+2x_k+1+1-2y_k+1.
    //Donde 2x_k+1=2x_k+2  y  2y_k+1=2y_k-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 (x_c, y_c) 
   y trazamos los valores de las coordenadas: x=x+x_c y y=y+y_c.
 Fin Para


Algoritmo del punto medio para elipses




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 estándar es simétrica 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 $^{2}x^{2}$ +r_x $^{2}y^{2}$ -r_x $^{2}$ r_y $^{2}$ 

f_elipse(x,y)<0 b=""> 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 r_x, r_y y el centro de la elipse (x_c, y_c).
 *Se obtiene el primer punto de la elipse centrada en origen (x_c, y_c) como (0, r_y).
 *Se calcula el valor inicial del parámetro de decisión de la región 1 como p₁₀=r_y $^{2}$ -r_x $^{2}$ r_y+ 0.25 r_x $^{2}$ .
 *En cada posición x_k en la región 1 para k=0
    Si p_1k<0 punto="" siguiente="(x<sub" style="line-height: 1em;">k+1

, y_k) p_1k+1=p_1k+2r_y

^{2}

x_k+1+r_y

^{2}

*Se calcula el valor inicial del parámetro de decisión de la región 2 utilizando el último (x₀,y₀) calculado en la región 1 como p₂₀=r_y $^{2}$ (x₀+0.5) $^{2}$ +r_x $^{2}$ (y₀-1) $^{2}$ -r_x $^{2}$ r_y $^{2}$ . *En cada posición y_k en la región 2 para k=0 Si p_2k>0 Punto siguiente = (x_k, y_k-1) p_2k+1=p_2k-2r_x

^{2}

y_k+1+r_x

^{2}

*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 (x_c, y_c) y trazamos los valores de las coordenadas: x=x+x_c y x=x+x_c. *Se repiten los pasos de la región 1 hasta que 2r_y2x₀ >=2r_x2y₀

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
#include
#include $#include 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 else="" p1="p1+(2*ry2*x)-(2*rx2*y)+ry2;" p2="(ry2)*pow((x+0.5),2)+(rx2)*pow((y-1),2)-(rx2*ry2);" putpixel="" while="" x="" xc-x="" xc="" y--="" y="" yc-y="" yc="">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();$


Algoritmo del Punto Medio



      El Algoritmo del Punto Medio fue ideado por Breshenhan en 1965. Su principal ventaja con respecto a otros métodos utilizados para el dibujo de líneas es su rapidez a la hora de calcular los pixels que debemos pintar cuando estamos dibujando una línea.

     Esta rapidez de la que hablamos se debe a que es un algoritmo incremental en el que además solo trabajamos con enteros por lo que no tenemos que hacer ningún tipo de redondeo.

     Lo que hace este algoritmo es utilizar una variable de decisión que le indicará cual es el siguiente pixel que tiene que pintar. Esta variable la llamaremos "d" y cada vez que pintemos un pixel se verá incrementada en un valor fijo que denominaremos incremento. Veamos esto con un pequeño ejemplo. Supongamos la siguiente situación:



      En la figura que tenemos arriba estamos intentando pintar la línea L y el último pixel que hemos pintado es P0. A la hora de elegir el siguiente pixel a pintar tenemos 2 posibilidades: P1 y P2. Pues bien, según elijamos P1 o P2, a la variable de decisión "d" le sumaremos un valor u otro. Pero, ¿de dónde sale ese valor que le tenemos que sumar a "d"? y ¿cómo utilizamos la variable de decisión "d" a la hora de elegir entre P1 y P2?. Eso es lo que vamos a ver ahora.

      Usaremos la ecuación implícita de la recta F(x, y) = ax + by +c, teniendo en cuenta lo siguiente:

            -	Si F(x, y) = 0, entonces el punto (x, y) pertenece a la recta.

            -	Si F(x, y) < 0, entonces el punto (x, y) está por encima de la recta.

            -	Si F(x, y) > 0, entonces el punto (x, y) está por debajo de la recta.

     ¿Cuál será nuestra variable de decisión?

        Nuestra variable de decisión "d" será F(M), siendo M el punto medio entre P1 y P2.



     ¿Cómo utilizamos la variable de decisión "d" para elegir entre P1 y P2?

           -	Si d > 0, entonces M está por debajo de la recta L. Esto implica que el punto P1 está más cerca de la recta que P2, lo que nos lleva a elegirlo como próximo punto a pintar.

           -	Si d < 0, estaremos en el caso contrario al anterior, lo que nos lleva a elegir P2 como siguiente punto a pintar.

           -	Si d = 0, da igual el punto que elijamos, si bien debemos mantener la elección cada vez que se nos plantee el mismo caso.

     En este ejemplo hemos considerado el octante E - NE, con lo cual P1 se refiere al píxel que esta al NE y P2 al que se encuentra al E.

     El cálculo de los incrementos y las d iniciales se muestran en:

Incremento E - NE

Incremento N - NE

Incremento S - SE

Incremento E - SE









Algoritmo de Punto Medio - Bresenham






El planteamiento que utilizamos aquí es similar a aquel que empleamos en el despliegue de una circunferencia de rastreo. Dados los parámetros r_x, r_y y (x_c, y_c), determinamos los puntos (x, y) para una elipse en posición estándar centrada en el origen y luego alteramos los puntos, de modo que la elipse esté centrada en (x_c, y_c).

El método de punto medio para elipse se aplica a lo largo del primer cuadrante en dos partes.

Definimos la ecuación de una elipse con (x_c, y_c) = (0,0) como

f_elipse(x, y) = r²_yx²+ r²_xy²- r2_xr²_y

que tiene las propiedades siguientes:

f_elipse(x, y) < 0 si (x , y) está adentro 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á afuera de la frontera de la elipse

Así, la función de la elipse f_elipse(x, y) sirve como un parámetro de decisión en el algoritmo de punto medio. En cada posición del muestreo, seleccionamos el pixel siguiente a lo largo de la trayectoria de la elipse de acuerdo con el signo de la función de la elipse evaluada en el punto medio entre los dos pixel candidatos.

En los pasos siguientes se presenta el algoritmo de la elipse de punto medio:

1.Se capturan r_x , r_y y el centro de la elipse (x_c , y_c ) y se obtiene el prime punto de una elipse centrada en el origen como (x₀ , y₀ )= (0 , r_y)

2.Se calcula el valor inicial del parámetro de decisión en la región 1 como p1₀ = r²_y  - r²_x r_y+ (1 r²x)/4

3.En cada posición x_k en la región 1, al iniciar en k=0 , se realiza la prueba siguiente. Si p1_k <0 em="" nbsp="">el punto siguiente a lo largo de la elipse centrada en (0 ,0) es (x_k+1 , y_k) y p1_k+1 = p1_k  +2 r²_y x_k+1+  r²_y

De otro modo, el punto siguiente a lo largo del círculo es (x_k +1 , y_k - 1) y  p1_k+1 = p1_k  +2 r²_y x_k+1- 2 r²_xy_k+1+r²_y con 2 r²_y x_k+1= 2 r²_y x_k+ 2 r²_y  ,  2 r²_x y_k+1= 2 r²_x y_k-  2 r²_x    

4.Se calcula el valor inicial del parámetro de decisión en la región 2 utilizando el último punto (x₀ , y₀) calculado en la región 1 como  p2₀ = r²_y  (x₀ + 1/2)²+ r²_x(y₀ - 1)² -  r ²_xr²_y

5.En cada y_k posición en la región 2, al iniciar en k = 0, se realiza la prueba siguiente. Si p2_k >0, el punto siguiente a lo largo de la elipse centrada en (0 ,0) es (x_k , y_k- 1) y p2_k+1 = p2_k  - 2r²_x y_k+1+  r²_x

De otro modo, el punto siguiente a lo largo del círculo es (x_k +1 , y_k - 1) y  p2_k+1 = p2_k  +2 r²_y x_k+1- 2 r²_xy_k+1+r²_x utilizando los mismos cálculos incrementales para x y y  que en la región 1.

6.Se determinan puntos de simetría en los otros tres cuadrantes.
7.Se mueve cada posición de pixel calculada (x , y) a la trayectoria elíptica centrada en (x_c , y_c)y se trazan los valores de las coordenadas:


   x = x + x_cy = y + y_c

 8.Se repiten los pasos para la región 1 hasta que 2 r²_y x>= 2 r²_x y.