Algoritmo para calcular el polígono restante después de la resta

Question

Tengo un gran polígono (Pa). En el interior del polígono hay una gran cantidad de pequeños "agujeros", como se muestra:

Estas son algunas condiciones de los agujeros:

1. Los agujeros no pueden superponerse entre sí
2. El los agujeros no pueden salir del polígono exterior
3. Sin embargo, los agujeros pueden tocar el borde del polígono exterior

¿Cómo obtener el polígono restante (o la lista de polígonos) de manera eficiente? La forma más fácil (modo de fuerza bruta) es tomar el Pa y calcular gradualmente el polígono restante restando los agujeros. Aunque esta idea es factible, sospecho que hay un algoritmo más eficiente.

Editar: ¡No estoy preguntando cómo realizar el algoritmo de recorte de polígono (o sustracción)! De hecho, eso es algo que haría con la fuerza bruta. Estoy pidiendo además del método de recorte de polígono (tomar el polígono principal y luego recortar gradualmente los agujeros), ¿hay alguna otra manera más eficiente?

Answer 1

Esto es muy difícil de hacer de manera general. Puede encontrar el código fuente de una solución aquí:

General Polygon Clipper (GPC)

Answer 2

Usted puede hacer así.

1. Dibuje el polígono principal con un color en un mapa de bits.
2. Dibuja los agujeros con otro color en el mismo mapa de bits.
3. A continuación, extraiga el polígono ejecutando el algoritmo de marcha de cuadrados con el color de los polígonos principales como umbral.
4. La salida contendrá todos los puntos que pertenecen a ese polígono.
5. Puede ordenar los puntos si lo desea como un polígono continuo cerrado.

Answer 3

Bueno, si utiliza la representación correcta para su polígono, no tendría que hacer nada. Simplemente agregue la lista de bordes de los agujeros a la lista de bordes de Pa.

La única consideración que debe tener es que si algún vértice o borde del orificio puede tocar Pa edge, deberá realizar alguna simplificación allí.

¡Un problema diferente es convertir ese polígono en un mapa de bits!

Answer 4

Estoy de acuerdo con salva, pero mi publicación abordará la parte del dibujo. Básicamente, puede sumar todas las líneas de los polígonos principal y de agujero juntos y así obtener un único polígono complejo.

El algoritmo en sí no está muy complicado y se explica muy bien en el Polygon Fill Teaching Tool.