Algoritmo de Vatti

El algoritmo de Vatti^[1] se utiliza en computación gráfica para recortar cualquier número de polígonos de formas arbitrarias. A diferencia de los algoritmos de Sutherland–Hodgman y Weiler–Atherton de recorte de polígonos, el algoritmo de Vatti no restringe los tipos de polígonos que pueden recortarse. Incluso puede recortar polígonos complejos y que se auto-intersectan así como polígonos con agujeros. El algoritmo es generalmente aplicable sólo en el espacio 2D.

Descripción[editar]

El recorte se define como la interacción entre un polígono sujeto y un polígono de recorte. Generalmente los algoritmos de recorte se ocupan de encontrar las intersecciones (regiones que se sobreponen) entre el sujeto y polígonos de recorte, pero también pueden usarse para calcular operaciones booleanas sobre polígonos.

El algoritmo Vatti implica el tratamiento del polígono sujeto, así como los polígonos de recorte de una manera ordenada, empezando por los bordes inferiores y trabajando hacia la parte superior; Esto es conceptualmente similar al algoritmo Bentley-Ottmann. Este enfoque de barrido de líneas divide el espacio del problema por líneas de exploración horizontales imaginarias que pasan por cada vértice de los polígonos participantes. Estas líneas de exploración delinean zonas de barrido las cuales se procesan, comenzando con la zona más baja, mientras el algoritmo agrega puntos de intersección dentro de estas zonas de barrido en los polígonos de solución.