¿Cómo combino polígonos complejos?

81

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)?

ingrese la descripción de la imagen aquí

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

granada
fuente

Respuestas:

67

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á.


Objetivo

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. Grafico

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.

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. Vectores

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.
xtmq
fuente
2
Creo que debería mencionarse que para comparar los productos escalares, los vectores deberían normalizarse antes de calcular su producto escalar (es decir, dividir las coordenadas del vector por sus longitudes). De todos modos, gracias por esta respuesta.
eyalzba
¿Este algoritmo tiene un nombre o es tu propia creación?
Andrés Oviedo
Lo leí en alguna parte, pero ahora no recuerdo dónde y cuándo =)
xtmq
NOTA: Ver unión de polígono sin agujeros , que muestra un diagrama diferente: dos polígonos se superponen, PERO hay un "agujero" que ninguno de ellos cubre. De acuerdo con @ comentario Hay xtmq, este algoritmo "rellenos" ese agujero (aunque es no parte de cualquiera de los dos polígonos de entrada). Si, en cambio, desea "retener" esos agujeros como agujeros, entonces (a) calcule los agujeros y (b) devuelva el "conjunto de agujeros" [En algunos sistemas / modos gráficos, estos agujeros se pueden incluir en el conjunto de polígono de salida , y dará como resultado agujeros cuando se dibuje.] ...
ToolmakerSteve
2
... Para hacer "(a) calcular los agujeros", busque puntos que nunca sean visitados por el "Paso 4. Construya un contorno común". Utilice uno de estos puntos para "comenzar" el hoyo. Realice un algoritmo de "contorno" similar, excluyendo los puntos ya utilizados por el polígono de salida principal. El polígono resultante es un "agujero". Repita hasta que TODOS los puntos se hayan incluido en algún polígono o hueco.
ToolmakerSteve
11

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 :


      BooleanOps


Joseph O'Rourke
fuente
2
Este tipo literalmente escribió el libro sobre esto;)
Constantin
6

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.

Benjamin Bannier
fuente
1
+1 para vincular a Bourke. Treinta segundos más lento y te habría adelantado :)
David Seiler
4

¡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.

FrustratedWithFormsDiseñador
fuente
Sí, la pregunta real es ¿cómo calculamos esos dos puntos de intersección agregados ?
Pacerier
2

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.

nornagon
fuente
1

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

Rowland Shaw
fuente
2
"Al agrupar países, espero que no haya superposición" ... no todos los países están de acuerdo en sus propias fronteras o en las de sus vecinos, aunque sería bueno que lo hicieran.
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner de hecho, pero la mayoría de los cartógrafos asignarán la región en disputa a su aliado político o como una entidad separada por derecho propio; por eso también describo mi algoritmo como ingenuo ...
Rowland Shaw
1

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;
}
Yonatan
fuente
Recuerde "corregir" sus polígonos si es necesario. Ver stackoverflow.com/questions/22258784/…
anumi
1

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)
Rabindra Nath Nandi
fuente
Clipper está disponible directamente en c ++ aquí: angusj.com/delphi/clipper.php
Catskul