Mencari apakah dua poligon berpotongan dengan Python?

Saya mencari algoritma, solusi tingkat tinggi, atau bahkan perpustakaan yang dapat membantu saya menentukan apakah dua poligon berpotongan, dengan Python.

Saya memiliki simpul dari dua poligon (Ini adalah poligon bagian tunggal tanpa lubang) dalam dua array yang berbeda. Poligon adalah 2D (yaitu hanya koordinat X dan Y)

Saya ingin membuat fungsi yang akan mengembalikan boolean yang menunjukkan apakah kedua poligon bersilangan.

Harap dicatat bahwa saya tidak dapat menggunakan arcpy, atau arcgiskomponen apa pun dalam hal ini.

Bisakah Anda menyarankan algoritma atau pustaka untuk melakukan ini?

Anda bisa mencoba dengan cantik .

Mereka menggambarkan hubungan spasial dan berfungsi pada windows

Model data spasial disertai oleh sekelompok hubungan bahasa alami antara objek geometris - berisi, berpotongan, tumpang tindih, menyentuh, dll. - dan kerangka kerja teoritis untuk memahaminya menggunakan matriks 3x3 dari persimpangan saling persimpangan set poin komponen mereka

Kode berikut menunjukkan bagaimana Anda bisa menguji persimpangan:

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

Anda dapat menggunakan binding Python GDAL / OGR untuk itu.

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

Itu kembali Nonejika mereka tidak berpotongan. Jika mereka memotongnya kembali maka geometri keduanya berpotongan.

Anda juga dapat menemukan info lebih lanjut di Cookbook GDAL / OGR .

Jika Anda tahu atau tertarik mempelajari R, ia memiliki beberapa paket spasial yang berguna. http://cran.r-project.org/web/views/Spatial.html Ada modul Python untuk berinteraksi dengan R (RPy *)

Saya tahu ini adalah pertanyaan lama, tetapi saya telah menulis perpustakaan python untuk menangani tabrakan antara polong cekung dan cembung, serta lingkaran.

Cukup mudah digunakan, ini dia!

Contoh:

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

Anda juga dapat membuatnya menghasilkan respons, yang meliputi:

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

jika Anda ingin mengetahui levelnya, Anda bisa menggunakan ini. Sebagai argumen, Anda dapat memberikan daftar poligon. Dan sebagai nilai balik Anda mendapatkan daftar level. Dalam daftar level ada poligon.

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