Geometría

Algoritmos geométricos

El algoritmo de Cohen-Sutherland es un algoritmo de recorte de líneas usado en gráficos por computadora. Fue desarrollado por Danny Cohen e Ivan Sutherland en 1967.- .............................:http://es.wikipedia.org/w/index.php?title=Especial:Libro&bookcmd=download&collection_id=d36ba913eeff9f59e6dbb683e2f47a9cd60fcc4d&writer=rdf2latex&return_to=Algoritmo+de+Cohen-Sutherland

Algoritmo de Cohen-Sutherland

^

Este algoritmo realiza varias comprobaciones iniciales para descubrir si se puede evitar cálculos de las intersecciones. El primer paso es comprobar si los puntos extremos del segmento son aceptados por sus posiciones. Si esto no es posible, entonces realizamos varias comprobaciones por regiones exteriores al rectángulo de recorte, formadas por las líneas rectas al extender sus aristas. Asimismo, podemos rechazar un segmento inmediatamente si sus extremos yacen en regiones a la izquierda de x_izq, por encima de y_sup, a la derecha de x_der, y por debajo de y_inf.

Si el segmento no se puede aceptar ni rechazar inmediatamente, entonces es partido en dos segmentos por un arista del rectángulo de recorte, para que uno de ellos sea rechazado de inmediato. Esto implica que implementamos un método iterativo de recorte para el segmento hasta que éste sea aceptado o rechazado. Este algoritmo es eficiente especialmente en el caso de tener un rectángulo de recorte muy grande que comprende a todos o una gran mayoría de los segmentos a visualizar. Asimismo, podemos tener el caso de un rectángulo de recorte muy pequeño que fuerza a todos o casi todos los segmentos a ser rechazados.

Se le asigna un código de cuatro bits, b₃b₂b₁b₀, a cada región de las nueve creadas. Este código binario es creado estratégicamente para representar rápida y fácilmente cada región. El valor de 1 indicará que un extremo yace en tal región mientras que un 0 indicará lo contrario. Aquí tenemos la estrategia a usar:

Bit	Condición	Descripción
b3	y > ysup	por encima de la arista superior
b2	y < yinf	por debajo de la arista inferior
b1	x > xder	a la derecha de la arista derecha
b0	x < xizq	a la izquierda de la arista izquierda

Figura 9 - Las regiones con los Códigos

Usaremos ciertas operaciones a nivel de bit para asginar el código regional a cada extremo en el que yace y también para determinar tal región cuando necesitemos discriminarlos. Una forma eficiente de asignar un valor a un bit particular es tomando el primer bit que indica el signo positivo o negativo de la resta entre las dos coordenadas de la condición. Esto es, b₃ es asignado el bit del signo de(y_sup-y), b₂ es asignado el bit de (y - y_inf), b₁ es asignado el bit de (x_sup-x), y b₀ es asignado el bit de (x - x_inf).

La figura 9 muestra las regiones con sus correspondientes códigos.

Con estos códigos podemos determinar si los extremos, y por tanto el segmento que representan, pueden ser aceptados o rechazados inmediatamente. Obviamente, si ambos códigos son 0, entonces ambos extremos existen dentro del rectángulo de recorte, y por consiguiente el segmento es aceptado de inmediato. Para combinar estos dos códigos, simplemente aplicamos una operación OR y comprobamos si el resultado es 0. Si el código no es 0, entonces aplicamos la operación AND a ambos códigos. Si el resultado no es cero, entonces rechazamos el segmento de inmediato.

Si no podemos aceptar ni rechazar inmediatamente el segmento, entonces iremos dividiendo el segmento y comprobando sus nuevos códigos, para determinar su aceptación o rechazo. Dividimos el segmento calculando la intersección con las líneas creadas al extender las aristas del rectángulo de recorte. Si no podemos discriminar el nuevo segmento, entonces debemos continuar dividiéndolo hasta que al final lo aceptamos o lo rechazamos. Una propiedad notable es que modificamos el segmento mudando el extremo, cuyo código no es cero. Dicho de otra manera, el algoritmo elige un extremo exterior que será mudado a la intersección con la arista o con la línea que separa y define las regiones. Asignamos el código regional del punto de intersección al extremo mudado.

La desventaja de este algoritmo es que puede realizar varias intersecciones antes de alcanzar la intersección final y válida. Una mejora es calcular la pendiente para determinar el punto de intersección una sola vez y conservarla para posteriores iteraciones. Aun con esta mejora, este algoritmo no es tan eficiente. Por otro lado, la ventaja de este algoritmo es su simplicidad y además se puede extender fácilmente al caso de un volumen de recorte en 3D.

Ejemplo

Descripción Figura 10 - Ejemplo Queremos mostrar varios segmentos, pero únicamente dentro de nuestra vista representada por un rectángulo vertical descrito con las siguientes esquinas: superior izquierda (-1,3) e inferior derecha (3,-3). Tenemos los siguientes segmentos definidos por parejas de puntos que forman sus extremos: A = (-2, 1) y B = ( 2, 2), C = ( 1, 4) y D = ( 0,-4), E = ( 4, 3) y F = ( 3, 0), G = (-3,-1) y H = (-2,-4).

Solución Figura 11 - Solución Calculamos los códigos regionales para cada punto: A: 0001 B: 0000 C: 1000 D: 0100 E: 0010 F: 0000 G: 0001 H: 0101

Figura 12 - Aplicando Criterios Aplicamos nuestros criterios a los resultados de las operaciones a nivel de bit de los códigos regionales de cada punto dando lugar a: AB: 0001 OR 0000 = 0001 ⇒ 0001 AND 0000 = 0000 ⇒ Hay que recortar CD: 1000 OR 0100 = 1100 ⇒ 1000 AND 0100 = 0000 ⇒ Hay que recortar EF: 0010 OR 0000 = 0010 ⇒ 0010 AND 0000 = 0000 ⇒ Hay que recortar GH: 0001 OR 0101 = 0101 ⇒ 0001 AND 0101 = 0001 ⇒ Inmediatamente lo rechazamos

Figura 13 - Recortando Hacemos la primera tanda de recortes de los puntos con sus primeras aristas del algoritmo, obteniendo: \{ A'x = -1 \{ A'y = 1 + 1 * 1 / 4 = 1,25 \{ C'x = 1 - 1 * 1 / (-8) = 1,125 \{ C'y = 3 \{ E'x = 3 \{ E'y = 3 - 3 * (-1) / (-1) = 0 Recalculamos los códigos de cada punto: A′B: 0000 OR 0000 = 0000 ⇒ Aceptamos el segmento C′D: 0000 OR 0100 = 0100 ⇒ 0000 AND 0100 = 0000 ⇒ Hay que recortar E′F: 0000 OR 0000 = 0000 ⇒ Aceptamos el segmento

Figura 14 - Recortando Nos falta recortar una segunda vez para el segmento C′D. El algoritmo elige el punto D para recortar, obteniendo: \{ D'x = 0 + 1,125 * 1 / 7 = 0,1607 \{ D'y = -3 Recalculamos los códigos de cada punto: C′D′: 0000 OR 0000 = 0000 ⇒ Aceptamos el segmento

Figura 15 - Final Al final, obtenemos la siguiente imagen con los segmentos recortados e interiores al rectángulo de recorte.

Algoritmo

La función principal es Recortar(), la cual aceptará tres parámetros: dos puntos extremos, P y Q, donde cada uno contiene las coordenadas (x,y) que representan el segmento a recortar, y un rectángulo, R, que contiene los elementos \ representando las coordenadas de las dos esquinas izquierda superior y derecha inferior. También debemos definir los códigos binarios para: SUPERIOR=8, INFERIOR=4, DERECHA=2, e IZQUIERDA=1.

Para Recortar(), el algoritmo es:

booleano Recortar( ref Punto P, ref Punto Q, Rectángulo R )

aceptar ← falso
terminar ← falso
códigoP ← Calcular_Código(P,R)
códigoQ ← Calcular_Código(Q,R)
Repetir:


Si (códigoP OR códigoQ) = 0, entonces


aceptar ← verdadero
terminar ← verdadero

Si no, compruebe que  (códigoP AND códigoQ) ≠ 0,


terminar ← verdadero

Si no, entonces


Si códigoP = 0, entonces


código ← códigoQ

Si no, entonces


código ← códigoP

Si código es SUPERIOR, entonces


Δy ← Q.y-P.y
Si Δy = 0, entonces  // segmento vertical


x ← P.x

Si no, entonces


x ← P.x + (Q.x-P.x)*(R.ysup-P.y) / Δy

y ← ysup

Si no, compruebe que código es INFERIOR


Δy ← Q.y-P.y
Si Δy = 0, entonces  // segmento vertical


x ← P.x

Si no, entonces


x ← P.x + (Q.x-P.x)*(R.yinf-P.y) / Δy

y ← yinf

Si no, compruebe que código es DERECHA


x ← xder
y ← P.y + (Q.y-P.y)*(R.xder-P.x) / (Q.x-P.x)

Si no, entonces  // código = IZQUIERDA


x ← xizq
y ← P.y + (Q.y-P.y)*(R.xizq-P.x) / (Q.x-P.x)

Si código = códigoP, entonces


P.x ← x
P.y ← y
códigoP ← Calcular_Código(P,R)

Si no, entonces


Q.x ← x
Q.y ← y
códigoQ ← Calcular_Código(Q,R)



Mientras que terminar = falso
Terminar( aceptar )

Si el segmento es aceptado, entonces el algoritmo terminará con el valor booleano verdadero. Además, los extremos, P y Q, contendrán los valores recortados por este mismo algoritmo. Si el segmento es rechazado, entonces uno debería hacer caso omiso de los parámetros, P y Q. En cualquier caso, se pasan estos dos parámetros por referencia, para así poder modificarlos.

A continuación presentamos el algoritmo para Calcular_Código(), el cual requiere un punto, P, y el rectángulo de recorte, R:

entero Calcular_Código( Punto P, Rectángulo R )

código ← 0
Si P.y > R.ysup, entonces


código ← código OR SUPERIOR

Si no, compruebe que P.y < R.yinf


código ← código OR INFERIOR

Si P.x > R.xder, entonces


código ← código OR DERECHA

Si no, compruebe que P.x < R.xizq


código ← código OR IZQUIERDA

Terminar( código )

No todos los lenguajes de programación aceptan realizar operaciones a nivel de bit con números que no sean enteros. Tampoco todos los lenguajes establecen exactamente la cantidad de bits para representar internamente un número real. Por estas razones, no hemos presentado el algoritmo mejorado para Calcular_Código() que previamente hablamos en este apartado.

Suponiendo que un número real se representase con 32 bits y el 32º bit contiene su signo positivo, como 0, o negativo, como 1, aquí presentamos otra versión del algoritmo Calcular_Código():

entero Calcular_Código( Punto P, Rectángulo R )

código ← (((P.y - R.ysup) SHR 31) SHL 3) OR
         (((R.yinf - P.y) SHR 31) SHL 2) OR
         (((P.x - R.xder) SHR 31) SHL 1) OR
         ((R.xizq - P.x)  SHR 31)
Terminar( código )

El operador SHL se refiere a la operación común de desplazamiento de bits a la izquierda y el operador SHR se refiere a la del desplazamiento de bits a la derecha.

algoritmo cohen sutherland .- ..................:https://docs.google.com/presentation/d/1pd4ZawZVXFsYqfqyjGVOPxtE44GwHiNgNi6qpDd0MVY/present?slide=id.i0

algoritmo cohen sutherland .- ...................:http://serdis.dis.ulpgc.es/~ii-fgc/Tema%203%20-%20Transformaciones%202D.pdf