El algoritmo de recorte de Vatti [1] se utiliza en gráficos por computadora . Permite recortar 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 de Vatti no restringe los tipos de polígonos que se pueden usar como sujetos o clips. Incluso se pueden procesar polígonos complejos (autointersecantes) y polígonos con agujeros . El algoritmo generalmente solo se aplica en el espacio 2D .
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 : difference , donde los polígonos de recorte eliminan las regiones superpuestas del sujeto; union , donde clipping devuelve las regiones cubiertas por los polígonos de sujeto o de recorte, y; xor , donde clipping devuelve las regiones cubiertas por los polígonos de sujeto o de recorte, excepto cuando están cubiertas por ambos polígonos.
El algoritmo de Vatti implica procesar los bordes de los polígonos de recorte y de los sujetos 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 mediante 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 rayos de exploración , los espacios entre líneas de exploración adyacentes. Estos rayos de exploración se procesan a su vez, comenzando con el rayo de exploración más bajo, y el algoritmo agrega puntos de intersección dentro de estos rayos de exploración en los polígonos de solución.