math - los - perimetro y area de poligonos regulares e irregulares

¿Cómo combino polígonos complejos? (8)

¡Buena pregunta! Nunca he intentado esto antes, pero voy a intentarlo ahora.

Primero: necesita saber dónde se superponen estas dos formas. Para hacer esto, podría mirar cada borde en el Polígono A y ver dónde se cruza y borde en el Polígono B. En este ejemplo, debe haber dos puntos de intersección.

Entonces: Haz la forma de unión. Puede tomar todos los vértices en A y B, y también los puntos de intersección, y luego excluir los vértices que contiene la forma final. Para encontrar estos puntos, parece que podrías encontrar cualquier vértice de A que esté dentro de B, y cualquier vértice de B que esté dentro de A.

Dado dos polígonos:

POLYGON((1 0, 1 8, 6 4, 1 0)) POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

¿Cómo puedo calcular la unión (polígono combinado)?

El ejemplo de Dave usa SQL Server para producir la unión, pero necesito lograr lo mismo en el código. Estoy buscando una fórmula matemática o un ejemplo de código en cualquier idioma que expone las matemáticas reales. Intento producir mapas que combinen países dinámicamente en regiones. Hice una pregunta relacionada aquí: agrupando formas geográficas

Al agrupar países, espero que no exista una superposición; podría tomar un algoritmo bastante ingenuo que busque vértices compartidos; una vista simple sería recorrer los puntos en un polígono, ver si está en cualquiera de sus otros polígonos. y comparte el mismo punto anterior o siguiente para ver si hay una coincidencia. Entonces simplemente elimine el vértice compartido para crear su unión

Debes determinar qué puntos se encuentran adentro . Después de eliminar estos puntos, puede insertar un conjunto de puntos "externos" en el otro. Sus puntos de inserción (por ejemplo, donde tiene la flecha en la imagen de la derecha) es donde tuvo que quitar los puntos de los conjuntos de entrada.

Esta es una muy buena pregunta. Implementé el mismo algoritmo en c # hace algún tiempo. El algoritmo construye un contorno común de dos polígonos (es decir, construye una unión sin agujeros). Aquí está.

Paso 1. Crea un gráfico que describa los polígonos.

Entrada: primer polígono (n puntos), segundo polígono (m puntos). Salida: gráfico. Vértice - Punto poligonal del punto de intersección.

Deberíamos encontrar intersecciones. Itera a través de todos los lados del polígono en ambos polígonos [O (n * m)] y encuentra cualquier intersección.

Si no se encuentra una intersección, simplemente agregue vértices y conéctelos al borde.
Si se encuentran intersecciones, ordénelas por longitud hasta su punto de inicio, agregue todos los vértices (inicio, final e intersecciones) y conéctelos (ya en orden ordenado) al borde.

Paso 2. Verifica el gráfico construido

Si no encontramos ningún punto de intersección cuando se construyó el gráfico, tenemos una de las siguientes condiciones:

Polygon1 contiene polygon2 - return polygon1
Polygon2 contiene polygon1 - return polygon2
Polygon1 y polygon2 no se cruzan. Devuelve polygon1 Y polygon2.

Paso 3. Encuentra el vértice inferior izquierdo.

Encuentra las coordenadas mínimas xey (minx, miny). Luego, encuentre la distancia mínima entre (minx, miny) y los puntos del polígono. Este punto será el punto inferior izquierdo.

Paso 4. Construye un contorno común.

Comenzamos a recorrer el gráfico desde el punto inferior izquierdo y continuamos hasta que volvemos a él. Al principio marcamos todos los bordes como no visitados. En cada iteración debe seleccionar el siguiente punto y marcarlo como visitado.

Para elegir el siguiente punto, elija un borde con un ángulo interno máximo en sentido antihorario.

Calculo dos vectores: vector1 para el borde actual y vector2 para cada próximo borde no visitado (como se presenta en la imagen).

Para los vectores que calculo:

Producto escalar (producto escalar). Devuelve un valor relacionado con un ángulo entre vectores.
Producto vectorial (producto cruzado). Devuelve un nuevo vector. Si la coordenada z de este vector es positiva, el producto escalar me da un ángulo recto en sentido contrario a las agujas del reloj. De lo contrario (la coordenada z es negativa), calculo el ángulo de obtención entre los vectores como un ángulo de 360º del producto escalar.

Como resultado, obtengo un borde (y un siguiente vértice correspondiente) con el ángulo máximo.

Agrego a la lista de resultados cada vértice pasado. La lista de resultados es el polígono de unión.

Observaciones

Este algoritmo nos permite fusionar múltiples polígonos para aplicar iterativamente con los pares de polígonos.
Si tiene una ruta que consta de muchas curvas y líneas bezier, primero debe aplanar esta ruta.

Este es un tema desafiante pero bien entendido, que a menudo se conoce con el nombre de "operaciones booleanas regularizadas en polígonos". Puede ver esta respuesta de MathOverflow , que incluye la siguiente figura (de la biblioteca de recortes de Alan Murta ), con la unión rosa que combinan los OP:

Necesitaba resolver el mismo problema hoy y encontré la solución con esta lib: gpc .

Tiene muchas implementaciones de lenguaje, la lista aquí incluye Java, Obj-C, C #, Lua, python y más.

Prueba gpc .

Una solución que he visto usando árboles BSP se describe here .

Básicamente, describe la intersección en términos de una unión de los bordes del polígono A que están dentro del polígono B (incluidos los bordes parciales, y calculados mediante un árbol BSP ). Luego, puede definir A / B como ~ (~ A / / ~ B ), donde ~ denota la inversión del devanado del polígono, / denota unión y / / indica intersección.