# Algoritmo de Cohen-Sutherland

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.

## Introducción

Este algoritmo resuelve el recorte de líneas que quedan fuera de un rectángulo alineado con los ejes. Para ello divide el espacio 2D en una matriz de 9 regiones, de las cuales la única visible es la parte central (el viewport). El viewport, es la pantalla o plano de proyección.
Dicho de otro modo, las líneas que delimitan el viewport son prolongadas en ambos extremos de sus 4 líneas formando así 9 planos perfectamente separados, donde sus puntos de intersección quedan perfectamente delimitados y son iguales a las coordenadas que describen el viewport.

## Funcionamiento

Cada punto tiene asignados unos códigos de frontera que indican la posición de ese punto respecto al viewport. Cada código de frontera se compone de 4 bits.
El algoritmo incluye, excluye, o incluye parcialmente, la línea (segmento) basado en dónde están sus puntos extremos:
* Ambos puntos están en el viewport (la operación bitwise OR de sus puntos extremos es igual a cero): aceptación trivial.
* Ambos puntos están en la misma región no visible (la operación bitwise AND de sus puntos extremos no es igual a cero): rechazo trivial.
* Ambos puntos están en regiones distintas: En caso de esta situación no trivial el algoritmo encuentra uno de los 2 puntos que está fuera del viewport (hay al menos un punto fuera). La intersección del punto exterior con la frontera extendida es entonces calculada (es decir, con la ecuación paramétrica de la línea) y este nuevo punto reemplaza al punto exterior. El algoritmo se repite hasta que ocurre un éxito o rechazo trivial.
Puede verse en el dibujo un ejemplo para cada caso. Nótese como solo las porciones de las líneas dentro del área verde (coloreadas de azul) necesitan ser dibujadas.

### Códigos de frontera

Los números en la figura inferior se llaman códigos de frontera. Un código de frontera es calculado para cada uno de los dos puntos extremos de la línea (tanto para el punto inicial como el punto final de la línea). El primer bit es asignado a 1 si el punto esta por encima del viewport. Los bits del código de frontera representan: Arriba, Abajo, Derecha, Izquierda. Por ejemplo el código de frontera 1010 representa un punto que está arriba y a la derecha del viewport. Note que los puntos de frontera tienen que ser recalculados en cada iteración después de que el corte ocurre.
| 1001 | 1000 | 1010 |
| 0001 | 0000 | 0010 |
| 0101 | 0100 | 0110 |
Analizando los valores y pasándolos a decimal (que resulta más comprensible a cualquier audiencia), puede analizarse que horizontalmente, hay una separación de 1 unidad entre el valor central y el de su izquierda y entre este y el valor de la derecha (8,9,10 - 0,1,2 - 4,5,6). Y de modo equivalente hay una separación verticalmente de 4 unidades entre un valor de la fila central y el de la fila inferior y entre este y el de la fila superior (1,5,9 - 0,4,8 - 2,6,10.
| 09 | 08 | 10 |
| 01 | 00 | 02 |
| 05 | 04 | 06 |

## Algoritmo de Cohen-Sutherland

Aquí está el algoritmo de Cohen-Sutherland