¿Cómo combino polígonos complejos?

Dados 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 el servidor SQL 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 exponga las matemáticas reales. Estoy intentando producir mapas que combinen países de forma dinámica en regiones. Hice una pregunta relacionada aquí: Agrupar formas geográficas

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 una gráfica 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 las intersecciones.

• 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. Verifique 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:

1. Polygon1 contiene polygon2 - devuelve polygon1
2. Polygon2 contiene polygon1 - devuelve polygon2
3. Polygon1 y polygon2 no se cruzan. Devuelve polygon1 AND polygon2.

Paso 3. Encuentra el vértice inferior izquierdo.

Encuentre las coordenadas xey mínimas (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. Construya un contorno común.

Comenzamos a recorrer el gráfico desde el punto inferior izquierdo y continuamos hasta que volvamos 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 una arista con un ángulo interno máximo en dirección contraria a las agujas del reloj.

Calculo dos vectores: vector1 para el borde actual y vector2 para cada siguiente borde no visitado (como se muestra en la imagen).

Para los vectores calculo:

1. Producto escalar (producto escalar). Devuelve un valor relacionado con un ángulo entre vectores.
2. 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 dirección contraria a las agujas del reloj. De lo contrario (la coordenada z es negativa), calculo obtener el ángulo entre vectores como 360 - ángulo del producto escalar.

Como resultado, obtengo una arista (y el 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

1. Este algoritmo nos permite fusionar múltiples polígonos, para aplicar iterativamente con pares de polígonos.
2. Si tiene una ruta que consta de muchas curvas y líneas Bézier, 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 mirar esta respuesta de MathOverflow , que incluye la figura a continuación (de la biblioteca de recortes de Alan Murta ), con la unión rosa de los OP combinan :

Necesitas determinar qué puntos se encuentran dentro . 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) son donde tuvo que eliminar puntos de los conjuntos de entrada.

¡Buena pregunta! Nunca había intentado esto antes, pero lo intentaré ahora.

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

Luego: 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.

Prueba gpc .

Aquí se describe una solución que he visto usando árboles BSP .

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 ). Entonces, puede definir A  /  B como ~ (~ A  / \ ~ B ), donde ~ denota invertir el devanado del polígono, / denota unión y / \ denota intersección.

Al agrupar países, espero que no haya superposición; podría tomar un algoritmo bastante ingenuo que busque vértices compartidos; una vista simple sería iterar a través de 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. Luego simplemente elimine el vértice compartido para crear su unión

Necesitaba resolver este mismo problema hoy y encontré la solución con esta biblioteca: http://www.cs.man.ac.uk/~toby/alan/software/ .

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

Esta es una pregunta muy antigua pero Union_ función de Boost funcionó para mí.

Vea este fragmento a continuación:

#include <iostream>
#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>

#include <boost/foreach.hpp>


int main()
{
    typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;

    polygon green, blue;

    boost::geometry::read_wkt(
        "POLYGON((0 0, 0 10, 10 10, 10 0, 0 0))", green);

    boost::geometry::read_wkt(
        "POLYGON((5 5, 5 15, 15 15, 15 5, 5 5))", blue);

    std::vector<polygon> output;
    boost::geometry::union_(green, blue, output);

    int i = 0;
    std::cout << "green || blue:" << std::endl;
    BOOST_FOREACH(polygon const& p, output)
    {
        std::cout << i++ << ": " << boost::geometry::area(p) << std::endl;

        for (int i = 0; i < p.outer().size(); i++)
        {
            std::cout << p.outer().at(i).x() << " " << p.outer().at(i).y() << std::endl;
        }
    }



    return 0;
}

Me he enfrentado al mismo problema y lo resolví de la siguiente manera

Contenedor de Cython para la traducción C ++ de la biblioteca Clipper de Angus Johnson (ver. 6.4.2) https://github.com/fonttools/pyclipper

pc = pyclipper.Pyclipper()
def get_poly_union(polygons):
    pc.AddPaths(polygons, pyclipper.PT_SUBJECT, True)
    solution = pc.Execute(pyclipper.CT_UNION, pyclipper.PFT_NONZERO, pyclipper.PFT_NONZERO)
    return solution[0]

print_image = image.copy()
solution = get_poly_union(polygons_array) 
#polygons_array=[polygon,polygon,polygon, ...,polygon] and polygon=[point,point,point...,point]

cv2.drawContours(print_image, [np.asarray(solution)], -1, (0, 255, 0), 2)

plt.imshow(print_image)