Le he pedido a esta pregunta ASÍ, pero la única respuesta que he obtenido es el de una no-respuesta como lo que puedo decir, así que me gustaría probar mi suerte aquí.
Básicamente, estoy en busca de un mejor de lo ingenuo algoritmo para la construcción de polígonos de la unión de muchos polígonos, cada uno con una lista de Vértices $V$. El ingenuo algoritmo para encontrar la unión de polígonos(s) va como esto:
En primer lugar tomar dos polígonos, de la unión de ellos, y tomar otro polígono, unión con la unión de los dos polígonos, y repetir este proceso hasta que cada de una sola pieza. A continuación, voy a correr a través de la unión de polígonos de la lista y compruebe si hay todavía algunos los polígonos pueden ser combinados, y voy a repita este paso hasta que un resultado satisfactorio se consigue.
Hay un algoritmo inteligente?
Para este propósito, se puede imaginar cada polígono como un rompecabezas pieza, cuando termine de ellos obtendrá una buena imagen. Pero la cuestión es que una pequeña porción ( es decir <5%) del rompecabezas que falta, y aún así se requiere para formar una imagen tan completa como sea posible; que el polígono ( o polígonos)-- tal vez con orificios que quiero formar.
Nota: estoy no preguntar acerca de cómo la unión de dos polígonos, pero estoy preguntando acerca de--dado que yo conozca cómo la unión de dos polígonos--cómo de la unión de $n$ número de (donde $n>>2$) polígonos de una manera eficiente.
También,todos los polígonos pueden compartir los bordes, y algunos polígono del borde puede ser compartido por uno o muchos otros polígono del borde. Los polígonos no puede superponen entre sí.
