¿Cómo encontrar si dos polígonos se intersectan en Python?

Question

Estoy buscando un algoritmo, una solución de alto nivel, o incluso una biblioteca que pueda ayudarme a determinar si dos polígonos se cruzan, en Python.

Tengo los vértices de los dos polígonos (Son polígonos de una sola pieza sin agujeros) en dos matrices diferentes. Los polígonos son 2D (es decir, sólo coordenadas X e Y)

Me gustaría hacer una función que devuelva un booleano indicando si estos dos polígonos se cruzan.

Tenga en cuenta que no puedo utilizar arcpy o cualquier arcgis componentes en esto.

¿Puede sugerir un algoritmo o una biblioteca para hacer esto?

Answer 1

Puedes probar elegante .

Describen las relaciones espaciales y funcionan en las ventanas

El modelo de datos espaciales va acompañado de un grupo de lenguajes naturales relaciones entre objetos geométricos - contiene, interseca solapamientos, toques, etc. - y un marco teórico para comprenderlas utilizando la matriz 3x3 de las intersecciones mutuas de sus conjuntos de puntos componentes

El siguiente código muestra cómo se puede comprobar la intersección:

from shapely.geometry import Polygon
p1 = Polygon([(0,0), (1,1), (1,0)])
p2 = Polygon([(0,1), (1,0), (1,1)])
print(p1.intersects(p2))

Answer 2

Puede utilizar el Enlaces GDAL/OGR Python por eso.

from osgeo import ogr

wkt1 = "POLYGON ((1208064.271243039 624154.6783778917, 1208064.271243039 601260.9785661874, 1231345.9998651114 601260.9785661874, 1231345.9998651114 624154.6783778917, 1208064.271243039 624154.6783778917))"
wkt2 = "POLYGON ((1199915.6662253144 633079.3410163528, 1199915.6662253144 614453.958118695, 1219317.1067437078 614453.958118695, 1219317.1067437078 633079.3410163528, 1199915.6662253144 633079.3410163528)))"

poly1 = ogr.CreateGeometryFromWkt(wkt1)
poly2 = ogr.CreateGeometryFromWkt(wkt2)

intersection = poly1.Intersection(poly2)

print intersection.ExportToWkt()

Devuelve None si no se cruzan. Si se cruzan, devuelve la geometría en la que ambos se cruzan.

También puede encontrar más información en el Libro de cocina GDAL/OGR .

Answer 3

Sé que esta es una pregunta vieja, pero he escrito una biblioteca de python para manejar las colisiones entre polígonos cóncavos y convexos, así como círculos.

Es muy sencillo de usar, ¡aquí tienes!

Ejemplo:

from collision import *
from collision import Vector as v

p0 = Concave_Poly(v(0,0), [v(-80,0), v(-20,20), v(0,80), v(20,20), v(80,0),  v(20,-20), v(0,-80), v(-20,-20)])
p1 = Concave_Poly(v(20,20), [v(-80,0), v(-20,20), v(0,80), v(20,20), v(80,0),  v(20,-20), v(0,-80), v(-20,-20)])

print(collide(p0,p1))

También puedes hacer que genere una respuesta que incluya:

overlap (how much they overlap)
overlap vector (when subtracted from second shapes position, the shapes will no longer be colliding)
overlap vector normalized (vector direction of collision)
a in b (whether the first shape is fully inside the second)
b in a (whether the second shape is fully inside the first)

https://github.com/QwekoDev/collision

Answer 4

Si sabes o estás interesado en aprender R tiene algunos paquetes espaciales útiles. http://cran.r-project.org/web/views/Spatial.html Existe un módulo de Python para interactuar con R (RPy*)

Answer 5

Si quieres saber el nivel puedes usar esto. Como argumento puedes dar una lista de polígonos. Y como valor de retorno obtienes una lista de niveles. En la lista de niveles están los polígonos.

from shapely.geometry import Point
from shapely.geometry.polygon import Polygon
def isPolygonInPolygon(poly1,poly2):
    poly2 = Polygon(poly2)
    for poi in poly1:
        poi = Point(poi)
        if(poly2.contains(poi)):
            return True

def polygonTransformHierarchy(polygon_list):
    polygon_list_hierarchy = []
    for polygon1 in polygon_list:
        level = 0
        for polygon2 in polygon_list:
            if(isPolygonInPolygon(polygon1, polygon2)):
                level += 1
        if(level > len(polygon_list_hierarchy)-1):
            dif = (level+1)- len(polygon_list_hierarchy)
            for _ in range(dif):
                polygon_list_hierarchy.append([])   
        polygon_list_hierarchy[level].append(polygon1)
    return polygon_list_hierarchy