Finden Sie heraus, ob sich zwei Polygone in Python schneiden?

19

Ich suche in Python einen Algorithmus, eine Lösung auf hoher Ebene oder sogar eine Bibliothek, mit deren Hilfe ich feststellen kann, ob sich zwei Polygone überschneiden.

Ich habe die Eckpunkte der beiden Polygone (Dies sind einteilige Polygone ohne Löcher) in zwei verschiedenen Arrays. Die Polygone sind 2D (dh nur X- und Y-Koordinaten)

Ich möchte eine Funktion erstellen, die einen Booleschen Wert zurückgibt, der angibt, ob sich diese beiden Polygone schneiden.

Bitte beachten Sie, dass ich arcpykeine arcgisKomponenten in diesem verwenden kann.

Können Sie einen Algorithmus oder eine Bibliothek dafür vorschlagen?

Devdatta Tengshe
quelle

Antworten:

42

Sie könnten es formschön versuchen .

Sie beschreiben räumliche Beziehungen und es funktioniert auf Fenstern

Das Geodatenmodell wird von einer Gruppe natürlicher Sprachbeziehungen zwischen geometrischen Objekten (enthält, schneidet, überlappt, berührt usw.) und einem theoretischen Rahmen zum Verständnis dieser Objekte unter Verwendung der 3x3-Matrix der gegenseitigen Schnittpunkte ihrer Komponentenpunktmengen begleitet

Der folgende Code zeigt, wie Sie auf Schnittpunkte testen können:

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))
radouxju
quelle
15

Sie können dafür die GDAL / OGR-Python-Bindungen verwenden .

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

Es wird zurückgegeben, Nonewenn sie sich nicht schneiden. Wenn sie sich schneiden, wird die Geometrie zurückgegeben, in der sich beide schneiden.

Weitere Infos finden Sie auch im GDAL / OGR-Kochbuch .

ustroetz
quelle
Ich würde das gerne benutzen, aber ich arbeite unter Windows und auf beiden Systemen, die ich ausprobiert habe, kann ich die Python-Bindungen nicht zum Laufen bringen. Ich stoße auf
Devdatta Tengshe
1
Für den Fall, dass jemand anderes darüber stolpert, ist es möglich, GDAL / OGR mit Python in Windows (und nicht weniger in ArcGIS) zu verwenden: gis.stackexchange.com/questions/74524/…
Evil Genius
Sie können auch intersection = poly1.Interect (poly2) schreiben - der Wert von intersection ist WAHR oder FALSCH, je nachdem, ob sich die Polygone schneiden
Max.
0

Ich weiß, dass dies eine alte Frage ist, aber ich habe eine Python-Bibliothek geschrieben, um Kollisionen zwischen konkaven und konvexen Polygonen sowie Kreisen zu behandeln.

Es ist ziemlich einfach zu bedienen, los geht's!

Beispiel:

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

Sie können auch eine Antwort generieren lassen, die Folgendes umfasst:

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

Qwerty
quelle
0

Wenn Sie das Level wissen wollen, können Sie dies verwenden. Als Argument können Sie eine Liste von Polygonen angeben. Und als Rückgabewert erhalten Sie eine Liste von Ebenen. In der Liste der Ebenen befinden sich die Polygone.

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
Tobias K
quelle