Hispanopedia WikiEl algoritmo de recorte de Vatti [ 1 ] se utiliza en gráficos por computadora . Fue propuesto por Bala R Vatti , quien trabajó en Calcomp y Hewlett-Packard [ 2 ] en la década de 1990 y propuso el algoritmo en Communications of the ACM Journal en 1992. [ 1 ]
El algoritmo permite recortar cualquier número de polígonos de sujeto 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 recortes. Incluso se pueden procesar polígonos complejos (autointersecantes) y polígonos con agujeros . El algoritmo generalmente solo es aplicable en el espacio 2D .
Descripción
El recorte se define como la interacción entre el sujeto y los polígonos de recorte. Si bien el recorte generalmente implica encontrar las intersecciones (regiones de superposición) de los polígonos del 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; unión , donde el recorte devuelve las regiones cubiertas por los polígonos del sujeto o de recorte; y xor , donde el recorte devuelve las regiones cubiertas por los polígonos del sujeto o de recorte, excepto cuando están cubiertas por ambos.
El algoritmo de Vatti implica el procesamiento ordenado de los bordes de los polígonos de origen y destino, comenzando por los bordes inferiores y avanzando hacia los superiores; conceptualmente, es similar al algoritmo de Bentley-Ottmann . Este método 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 delimitan haces de exploración , es decir, los espacios entre líneas de exploración adyacentes. Estos haces de exploración se procesan sucesivamente, comenzando por el haz de exploración inferior, y el algoritmo añade los puntos de intersección dentro de estos haces de exploración a los polígonos de la solución.
Véase también
Referencias
- 1 2 Bala R. Vatti. "Una solución genérica para el recorte de polígonos" , Communications of the ACM, Vol. 35, número 7 (julio de 1992), págs. 56-63.
- ↑ Vatti, Bala R. «Experiencia laboral de Bala R Vatti» . LinkedIn . Consultado el 16 de agosto de 2025 .
Enlaces externos
- Clipper2, una implementación gratuita de código abierto del algoritmo de Vatti.
- Algoritmos de recorte de polígonos
- Esbozos de gráficos por computadora
