algorithm - topografia - poligonal arquitectura

Unión poligonal sin agujeros. (3)

Estoy buscando algo bastante fácil (sé que la unión de polígonos NO es una operación fácil, pero tal vez alguien podría apuntarme en la dirección correcta con un algoritmo relativamente sencillo) al fusionar dos polígonos que se cruzan. Los polígonos podrían ser cóncavos sin agujeros y también el polígono de salida no debería tener agujeros. Los polígonos se representan en sentido contrario a las agujas del reloj. Lo que quiero decir se presenta en una imagen. Como puede ver, incluso si hay un agujero en la unión de polígonos, no lo necesito en la salida. Los polígonos de entrada son seguros sin agujeros. Creo que sin agujeros debería ser más fácil de hacer pero aún no tengo una idea.

Elimine todos los vértices de los polígonos que se encuentran dentro del otro polígono: http://paulbourke.net/geometry/insidepoly/
Elija un punto de inicio que esté garantizado para estar en el polígono de unión (uno de los extremos funcionaría)
Traza a través de los bordes del polígono en sentido contrario a las agujas del reloj. Estos son puntos en su sindicato. Trace hasta que llegue a una intersección (tenga en cuenta que un borde puede cruzarse con más de un borde del otro polígono).
Encuentra la primera intersección (si hay más de una). Este es un punto en tu unión.
Vuelve al paso 3 con el otro polígono. El siguiente punto debe ser el punto que forma el mayor ángulo con el borde anterior.

No tengo una respuesta completa, pero estoy a punto de embarcarme en un problema similar. Creo que hay dos pasos que son bastante importantes. Primero sería encontrar un punto en un polígono que se encuentra en el borde exterior. Lo segundo sería hacer una lista de cuadros delimitadores para todos los vértices y ver cuáles de estos se superponen. Esto significa que cuando recorres los vértices, no tienes que hacer pruebas para todos ellos, solo aquellos que sabes que tienen la posibilidad de cruzar (los problemas del cuadro delimitador son ligeros).

Como ahora tiene un punto exterior, ahora puede recorrer los puntos conectados hasta que detecte una intersección. Si sabe qué lado está dentro y qué lado está fuera (es posible que necesite hacer un poco de trabajo en el primer vértice para saberlo), sabe qué camino tomar en la intersección. Entonces es simplemente una cuestión de cambiar polígonos.

Esto se vuelve un poco más interesante si desea mantener ese agujero (que yo hago), en cuyo caso, probablemente me aseguraría de haber agotado todos mis cuadros de límite de intersección. Tampoco especificaste qué debería pasar si tus polígonos no se intersecan en absoluto. Pero eso será dejarlos solos (lo que podría ser un problema si está esperando un polígono) o devolver un error.

Puede proceder de la siguiente manera:

Primero agregue a su conjunto de puntos todos los puntos de intersección de sus polígonos.

luego procedería como el algoritmo de escaneo Graham pero con una restricción más.

En lugar de seleccionar el punto que forma el ángulo más alto con la línea anterior (observe el escaneo Graham para ver qué quiero decir (*)), elija el que tenga el ángulo más alto que formaba parte de uno de los polígonos anteriores.

obtendrá una envellope (no convexa) que describirá su forma.

Nota:

Es similar a encontrar el casco convexo de tus puntos.

Por ejemplo, el algoritmo de escaneo Graham lo ayudará a encontrar el casco convexo del conjunto de puntos en O (N * ln (N)) donde N es el número de puntos.

busca los algoritmos de casco convexo, y puedes encontrar algunas ideas.

Espero eso ayude.

remarques

(*) de wikipedia:

El primer paso en este algoritmo es encontrar el punto con la coordenada y más baja. Si la coordenada y más baja existe en más de un punto en el conjunto, se debe elegir el punto con la coordenada x más baja fuera de los candidatos. Llame a este punto P. Este paso toma O (n), donde n es el número de puntos en cuestión.
A continuación, el conjunto de puntos debe ordenarse en orden creciente del ángulo que ellos y el punto P hacen con el eje x. Cualquier algoritmo de clasificación de propósito general es apropiado para esto, por ejemplo, heapsort (que es O (n log n)). Para acelerar los cálculos, no es necesario calcular el ángulo real que hacen estos puntos con el eje x; en cambio, basta con calcular el coseno de este ángulo: es una función que disminuye monótonamente en el dominio en cuestión (que es de 0 a 180 grados, debido al primer paso) y se puede calcular con aritmética simple.

En el algoritmo de casco convexo, eligió el punto del ángulo que forma el ángulo más grande con el lado anterior.

Para "mantenerte" con tu polígono anterior, solo agrega la restricción de que debes seleccionar un lado que existía anteriormente.

y se quita la restricción de tener un ángulo inferior a 180 °

espero que quede claro