El Weiler-Atherton es una polygon- recorte algoritmo . Se utiliza en áreas como gráficos por computadora y desarrollo de juegos donde se necesita el recorte de polígonos. Permite el recorte de un polígono sujeto o candidato mediante un polígono / área / región de recorte de forma arbitraria .
Generalmente es aplicable solo en 2D . Sin embargo, se puede utilizar en 3D a través de la determinación de la superficie visible y con la mejora de la eficiencia a través de Z-pedido . [1]
Condiciones previas
Antes de aplicarse a un polígono, el algoritmo requiere que se cumplan varias condiciones previas:
- Los polígonos candidatos deben orientarse en el sentido de las agujas del reloj.
- Los polígonos candidatos no deben ser auto-intersectantes (es decir, reentrantes).
- El algoritmo puede admitir huecos (como polígonos en sentido contrario a las agujas del reloj completamente dentro de su poligoritmo principal.
Algoritmo
Dado que el polígono A es la región de recorte y el polígono B es el polígono sujeto a recortar, el algoritmo consta de los siguientes pasos:
- Enumere los vértices del polígono A de la región de recorte y los del polígono sujeto B.
- Etiquete los vértices enumerados del polígono sujeto B como dentro o fuera de la región de recorte A.
- Encuentre todas las intersecciones de polígonos e insértelas en ambas listas, uniendo las listas en las intersecciones.
- Genere una lista de intersecciones "entrantes": las intersecciones donde el vector desde la intersección hasta el vértice posterior del polígono sujeto B comienza dentro de la región de recorte.
- Siga cada intersección en el sentido de las agujas del reloj alrededor de las listas vinculadas hasta encontrar la posición inicial.
Si no hay intersecciones, entonces debe cumplirse una de las tres condiciones:
- A está dentro de B: devuelve A para recortar, B para fusionar.
- B está dentro de A: devuelve B para recortar, A para fusionar.
- A y B no se superponen: devuelve None para recortar o A & B para fusionar.
Conclusión
Uno o más polígonos cóncavos pueden producir más de un polígono que se cruza. Los polígonos convexos solo tendrán un polígono de intersección.
El mismo algoritmo se puede utilizar para fusionar dos polígonos comenzando en las intersecciones salientes en lugar de las entrantes. Sin embargo, esto puede producir agujeros en sentido antihorario.
Algunas combinaciones de polígonos pueden ser difíciles de resolver, especialmente cuando se permiten huecos.
Los puntos muy cercanos al borde del otro polígono pueden considerarse tanto de entrada como de salida hasta que se pueda confirmar su estado después de que se hayan encontrado y verificado todas las intersecciones; sin embargo, esto aumenta la complejidad.
Se pueden utilizar varias estrategias para mejorar la velocidad de este etiquetado y evitar la necesidad de seguir adelante. Se necesitará cuidado donde los polígonos comparten un borde.
Ver también
Referencias
- ^ Foley, James, Andries van Dam, Steven Feiner y John Hughes. "Infografía: principio y práctica". Compañía editorial de Addison-Wesley. Reading, Massachusetts: 1987. páginas 689-693
- Weiler, Kevin y Atherton, Peter. "Eliminación de superficies ocultas mediante la clasificación de áreas poligonales" , Computer Graphics, 11 (2): 214-222, 1977.