Sprawdzanie, czy dwa wielokąty przecinają się w Pythonie?

Szukam algorytmu, rozwiązania na wysokim poziomie, a nawet biblioteki, która może pomóc mi ustalić, czy dwa wielokąty przecinają się w Pythonie.

Mam wierzchołki dwóch wielokątów (są to wielokąty jednoczęściowe bez otworów) w dwóch różnych układach. Wielokąty są 2D (tzn. Tylko współrzędne X i Y)

Chciałbym utworzyć funkcję, która zwróci wartość logiczną wskazującą, czy te dwa wielokąty się przecinają.

Pamiętaj, że nie mogę używać arcpyani żadnych arcgisskładników tego.

Czy możesz zasugerować algorytm lub bibliotekę, aby to zrobić?

Możesz spróbować zgrabnie .

Opisują relacje przestrzenne i działa w systemie Windows

Modelowi danych przestrzennych towarzyszy grupa naturalnych relacji językowych między obiektami geometrycznymi - zawiera, przecina, nakłada się, dotyka itp. - oraz teoretyczne ramy dla ich zrozumienia przy użyciu macierzy 3x3 wzajemnych przecięć ich zestawów punktów składowych

Poniższy kod pokazuje, jak można przetestować skrzyżowanie:

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

W tym celu można użyć powiązań Python GDAL / OGR .

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

Zwraca, Nonejeśli się nie przecinają. Jeśli się przecinają, zwraca geometrię.

Dalsze informacje można znaleźć w książce kucharskiej GDAL / OGR .

Jeśli znasz lub jesteś zainteresowany nauką języka R, ma on kilka przydatnych pakietów przestrzennych. http://cran.r-project.org/web/views/Spatial.html Istnieje moduł Pythona do interakcji z R (RPy *)

Wiem, że to stare pytanie, ale napisałem bibliotekę Pythona do obsługi kolizji między wklęsłymi i wypukłymi wielokątami, a także okręgami.

Jest dość prosty w użyciu, proszę bardzo!

Przykład:

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

Możesz również wygenerować odpowiedź, która obejmuje:

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

jeśli chcesz poznać poziom, możesz tego użyć. Jako argument możesz podać listę wielokątów. Jako wartość zwracaną otrzymasz listę poziomów. Na liście poziomów znajdują się wielokąty.

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