Geometría

Algoritmos geométricos

El algoritmo de Xiaolin Wu es una mejora del algoritmo de Bresenham que permite dibujar rectas en dispositivos de gráficos rasterizados reduciendo el aliasing. El algoritmo se basa en dibujar parejas de pixeles a lo largo del trazado de la recta con diferentes intensidades en función de la cercanía a la recta real.

El algoritmo segmento Xiaolin Wu rastreo es un algoritmo para dibujar curvas no dentadas que fue presentado en el artículo de una técnica eficaz Antialiasing de julio de 1991 de Computer Graphics y en el artículo Fast Antialiasing julio edición 1992 del Diario del Dr. Dobb.

El algoritmo Bresenham dibuja líneas muy rápidamente, pero no está diseñado para antialiasing. Además, no puede manejar el caso en que los puntos finales de línea no se encuentran exactamente en la cuadrícula de píxeles. El enfoque ingenuo para dibujar líneas sin aliasing es mucho tiempo, pero el algoritmo de Wu es bastante rápido. La base del algoritmo es para dibujar los pares de píxeles línea superpuestos, de color según su proximidad. Línea después de los píxeles son tratados por separado.

Una extensión del algoritmo para círculos fue presentado por Wu en el Graphics Gems II. Como Wu algoritmo de rastreo segmento es un reemplazo del algoritmo de la línea del Bresenham, el camino círculo Wu es un reemplazo del algoritmo de dibujo círculo Bresenham.

Implementación en pseudo-código

A continuación, el pseudo código del algoritmo en el caso donde la línea es casi horizontal. Para extenderlo a todas las líneas, invertir la coordenadas xey en cuando. Esta aplicación sólo es válida para x ≥ 0 ey ≥ 0.

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)= 

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.

 *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

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: pk = felipse(x,y)= ry+rx-rxry

felipse(x,y)<0 b=""> si (x,y) está dentro de la frontera de la elipse.

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

felipse(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.



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="(x<sub" style="line-height: 1em;">k+1

, y_k) p_1k+1=p_1k+2r_yx_k+1+r_y *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(x₀+0.5)+r_x(y₀-1)-r_xr_y. *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_xy_k+1+r_x *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₀

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);




Ejemplo en código C:
#include
#include
#include