El algoritmo de recorte de Vatti [1] se utiliza en gráficos por computadora . Permite el recorte de cualquier número de polígonos sujetos de forma arbitraria mediante cualquier número de polígonos de recorte de forma arbitraria . A diferencia de los algoritmos de recorte de polígonos de Sutherland-Hodgman y Weiler-Atherton , el algoritmo Vatti no restringe los tipos de polígonos que se pueden usar como sujetos o clips. Incluso se pueden procesar polígonos complejos (auto-intersectantes) y polígonos con agujeros. El algoritmo es generalmente aplicable solo en el espacio 2D .
Descripción
El recorte se define como la interacción de los polígonos de sujeto y de recorte. Si bien el recorte generalmente implica encontrar las intersecciones (regiones de superposición) de los polígonos de sujeto y de recorte, los algoritmos de recorte también se pueden aplicar con otras operaciones de recorte booleanas : diferencia , donde los polígonos de recorte eliminan las regiones superpuestas del sujeto; union , donde el recorte devuelve las regiones cubiertas por polígonos de sujeto o de recorte, y; xor , donde el recorte devuelve las regiones cubiertas por polígonos de sujeto o de recorte, excepto cuando están cubiertas por polígonos de sujeto y de recorte.
El algoritmo Vatti implica procesar tanto el sujeto como los bordes del polígono de recorte de manera ordenada, comenzando con los bordes más bajos y avanzando hacia la parte superior; esto es conceptualmente similar al algoritmo de Bentley-Ottmann . Este enfoque de línea de barrido divide el espacio del problema por líneas de exploración , líneas horizontales imaginarias que pasan por cada vértice de los polígonos participantes. Estas líneas de exploración delinean los haces de exploración , los espacios entre las líneas de exploración adyacentes. Estos haces de escaneo se procesan a su vez, comenzando con el haz de escaneo más bajo, y el algoritmo agrega puntos de intersección dentro de estos haces de escaneo en los polígonos de solución.
Ver también
Referencias
- ^ Bala R. Vatti. "Una solución genérica para el recorte de polígonos" , Comunicaciones del ACM, Vol 35, Número 7 (julio de 1992) págs. 56–63.