蟒蛇：排序多邊形的兩個列表交叉路口

我有多邊形的兩個大名單。使用python，我想獲取列表1中的每個多邊形，並找到它與列表2中的多邊形的幾何交集的結果（我正在使用shapely來做到這一點）。蟒蛇：排序多邊形的兩個列表交叉路口

因此，對於列表1中的多邊形i，列表2中可能有多個與其相交的多邊形。

問題是這兩個列表都很大，如果我只是嵌套兩個循環併爲每個可能的多邊形對運行交叉命令，則需要很長時間。我不確定在布爾測試之前交叉點是否會顯着提高速度（例如，如果intersects：return intersection）。

對於我來說，排序或組織這兩個多邊形列表以便使交點更有效率是一個好方法？有沒有適合這種情況的排序算法，以及我可以使用python進行的排序算法？

我是比較新的規劃，並在離散數學沒有背景，所以如果你知道一個現有的算法，我應該使用，（我假設存在這類情況），請將鏈接或給予一定的解釋，可以幫助我實際上在Python中實現它。

此外，如果有一個更好的StackExchange網站這個問題，讓我知道。我覺得它像橋樑一般python編程，gis和幾何，所以我不太確定。

來源

2011-01-24 BenjaminGolder

是凸多邊形？ – 2011-01-24 00:16:53

它們的頂點可以形成凸或凹的角度，他們也有洞，但我可以很容易地使用他們的邊界框是否會有所幫助。 – BenjaminGolder 2011-01-24 00:21:19

空間分區！四邊形樹或邊界框上的體積kd樹。 – 2011-01-24 00:21:44

Quadtrees通常用於縮小需要互相檢查的多邊形集合 - 如果兩個多邊形都佔據至少一個相同的區域，則只需要檢查兩個多邊形四叉樹。你做四叉樹的深度（多邊形，而不是積分）取決於你。

來源

2011-01-24 00:23:19 Amber

即使只是將你的空間達到更小的固定大小的區域將加快路口檢測（如果你的多邊形足夠小和稀疏）。您製作網格並將每個多邊形標記爲屬於網格中的某些單元格。然後查找其中包含多個多邊形的單元格，並僅對這些多邊形進行交點計算。這種優化是最簡單的代碼，但最無效。第二種最簡單和最有效的方法是四叉樹。然後是BSP tres，KD樹和BVH樹，可能是最有效的，但最難編碼的。

編輯：另一個優化如下：找出每個多邊形的最左邊和最右邊的頂點並將它們放入一個列表中。對列表進行排序，然後從左向右循環，並輕鬆找到邊界框的x座標重疊的多邊形，然後對這些多邊形進行交集計算。

來源

2011-01-24 00:34:15 kynnysmatto

蟒蛇：排序多邊形的兩個列表交叉路口

回答

相關問題