Trouver si deux polygones se croisent en Python?

Je cherche un algorithme, une solution de haut niveau, ou même une bibliothèque qui peut m'aider à déterminer si deux polygones se croisent, en Python.

J'ai les sommets des deux polygones (ce sont des polygones monoblocs sans trous) dans deux tableaux différents. Les polygones sont 2D (c'est-à-dire uniquement les coordonnées X et Y)

Je voudrais faire une fonction qui retournera un booléen indiquant si ces deux polygones se croisent.

Veuillez noter que je ne peux pas utiliser arcpy, ni aucun arcgiscomposant de celui-ci.

Pouvez-vous suggérer un algorithme ou une bibliothèque pour ce faire?

Vous pourriez essayer bien .

Ils décrivent les relations spatiales et cela fonctionne sur les fenêtres

Le modèle de données spatiales s'accompagne d'un groupe de relations en langage naturel entre des objets géométriques - contient, intersecte, se chevauche, se touche, etc. - et d'un cadre théorique pour les comprendre en utilisant la matrice 3x3 des intersections mutuelles de leurs ensembles de points composants

Le code suivant montre comment tester l'intersection:

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

Vous pouvez utiliser les liaisons Python GDAL / OGR pour cela.

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

Elle revient Nonesi elles ne se coupent pas. S'ils se coupent, cela renvoie la géométrie qui se croisent tous les deux.

Vous pouvez également trouver plus d'informations dans le livre de recettes GDAL / OGR .

Si vous connaissez ou êtes intéressé à apprendre R, il a quelques paquets spatiaux utiles. http://cran.r-project.org/web/views/Spatial.html Il existe un module Python pour interagir avec R (RPy *)

Je sais que c'est une vieille question, mais j'ai écrit une bibliothèque python pour gérer les collisions entre les polygones concaves et convexes, ainsi que les cercles.

C'est assez simple à utiliser, c'est parti!

Exemple:

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

Vous pouvez également lui faire générer une réponse, qui comprend:

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

si vous voulez connaître le niveau, vous pouvez l'utiliser. Comme argument, vous pouvez donner une liste de polygones. Et comme valeur de retour, vous obtenez une liste de niveaux. Dans la liste des niveaux, il y a les polygones.

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