Algoritmo de Wyler-Atherton
Los polígonos cortados y cortados pueden ser no convexos.
Los polígonos de entrada deben tener una dirección transversal de límite fija (digamos en el sentido de las agujas del reloj) y no deben tener autointersecciones . El algoritmo puede manejar polígonos con agujeros (los agujeros se especifican como polígonos con la dirección de recorrido opuesta), pero requiere algoritmos adicionales para determinar cuáles de los polígonos son agujeros.
El algoritmo se puede modificar para fusionar dos polígonos.
Algoritmo
- A partir de las coordenadas de los vértices de los polígonos A y B se compilan dos listas.
- Los vértices de cada una de las listas se etiquetan según estén o no dentro del otro polígono.
- Los puntos de intersección de polígonos se agregan a ambas listas; Se establecen enlaces bidireccionales entre puntos coincidentes en diferentes listas.
- Si no se encuentra ninguna intersección, ocurre una de las siguientes situaciones:
- A dentro de B: devuelve A cuando se trunca, B cuando se combina.
- B dentro de A: devuelve B cuando se trunca, A cuando se combina.
- A y B no se cruzan: devuelve un conjunto vacío cuando se trunca, A y B cuando se combinan.
- Se compila una lista de puntos de intersección en los que el límite del polígono A, cuando se atraviesa, entra en el polígono B. Siguiendo desde cada punto en el sentido de las agujas del reloj a lo largo de los límites de los polígonos A y B, se puede encontrar un conjunto de áreas de intersección. En el caso de que A y B sean convexos, solo hay un polígono de intersección. De la misma manera, puedes encontrar la unión de polígonos, en este caso, el recorrido debe comenzar con los puntos de salida.
Véase también
Enlaces