El algoritmo Greiner-Hormann se utiliza en gráficos por computadora para el recorte de polígonos . [1] Funciona mejor que el algoritmo de recorte de Vatti , pero no puede manejar las degeneraciones . [2] Puede procesar polígonos que se intersectan a sí mismos y no convexos. Se puede generalizar trivialmente para calcular otras operaciones booleanas en polígonos , como unión y diferencia.
El algoritmo se basa en la definición del "interior" de un polígono en función del número de devanado . Considera que las regiones con número de devanado impar están dentro del polígono; esto se conoce como la regla par-impar . Toma dos listas de polígonos como entrada.
En su forma original, el algoritmo se divide en tres fases:
- En la primera fase, se calculan las intersecciones por pares entre los bordes de los polígonos. Se insertan vértices adicionales en ambos polígonos en los puntos de intersección; un vértice de intersección contiene un puntero a su contraparte en el otro polígono.
- En la segunda fase, cada intersección se marca como una intersección de entrada o una intersección de salida . Esto se logra evaluando la regla par-impar en el primer vértice, lo que le permite saber si el primer vértice está dentro o fuera del otro polígono. Luego, siguiendo los límites del polígono, las intersecciones se marcan con banderas alternas (la siguiente intersección después de una intersección de entrada debe ser una intersección de salida).
- En la tercera fase se genera el resultado. El algoritmo comienza en una intersección no procesada y elige la dirección de recorrido según el indicador de entrada/salida: para una intersección de entrada, atraviesa hacia adelante y para una intersección de salida, atraviesa en reversa. Los vértices se añaden al resultado hasta que se encuentra la siguiente intersección; Luego, el algoritmo cambia al vértice de intersección correspondiente en el otro polígono y elige la dirección transversal nuevamente usando la misma regla. Si la siguiente intersección ya ha sido procesada, el algoritmo finaliza el componente actual de la salida y comienza nuevamente desde una intersección no procesada. La salida estará completa cuando no queden más intersecciones sin procesar.
El algoritmo no se limita a polígonos y puede manejar curvas paramétricas arbitrarias como segmentos, siempre que exista un procedimiento de intersección por pares adecuado.
Una deficiencia importante del algoritmo Greiner-Hormann original es el hecho de que no puede manejar degeneraciones, como aristas comunes o intersecciones exactamente en un vértice. El artículo original sugiere perturbar los vértices para eliminarlos.
Ver también
Referencias
- ^ Greiner, Günther; Kai Hormann (1998). "Recorte eficiente de polígonos arbitrarios". Transacciones ACM sobre gráficos . 17 (2): 71–83. doi : 10.1145/274363.274364 .
- ^ Ionel Daniel Stroe. "Recorte eficiente de polígonos arbitrarios" . Consultado el 17 de mayo de 2014 .
enlaces externos
- Recorte geográfico Describe los algoritmos de recorte en D3.js.
- https://github.com/helderco/univ-polyclip Una implementación en Python y Java.
- https://github.com/w8r/GreinerHormann Una implementación en JavaScript
- JTS Topological Suite Una suite topológica con implementación Java
