如何有效地找到两个多边形数组的交集的每个组合？

Question

我有两个多边形数组，称为

grid_1

和

grid_2

。

grid_1

有 1,500,000 个多边形，

grid_2

有 60,000 个多边形。由于计算每个组合的相交多边形然后计算其面积的计算成本太高，因此我想首先计算那些相交的多边形，然后继续。使用嵌套的 for 循环，它可能看起来像这样：

from shapely.geometry import Polygon
from scipy import sparse

intersection_bool = sparse.lil_matrix((len(grid_1),len(grid_2))),astype("bool")

for i in range(len(grid_1)):
    for j in range(len(grid_2)):
        if i.intersects(j):
            intersection_bool[i,j] = 1.0

但是，这在计算上仍然太昂贵。 This问题建议使用shapely的STRtrees。但是，我不确定有效地做到这一点的最佳方法是什么。我尝试了下面的实现，但它比嵌套的 for 循环慢。我认为 STRtrees 是我的答案，我只是不确定如何最有效地使用它们。谢谢！

from shapely.strtree import STRtree
from shapely.geometry import Polygon
from scipy import sparse

intersection_bool = sparse.lil_matrix((len(grid_1),len(grid_2))),astype("bool")

grid_1_tree = STRtree(grid_1)
for j in range(len(grid_2)):
    result = tree.query(grid_2[j])
    for i in range(len(grid_1)):
        if grid_1[i] in result:
            intersection_bool[i,j] = 1.0

Answer 1

这还不是理想的答案，但是将我的多边形放入

geopandas.GeoSeries

中可以使相交函数矢量化并使我下降到一个

for

循环，从而使我的代码速度加快了约 3 倍。

Answer 2

Shapely，从 2.00 开始，[包括对 SRTree 函数的一些更改][1]。此外，新的 [

prepare

函数][2] 似乎包含 SRTree（正如在项目中从纯代码升级到 SRTree 进行准备时观察到的那样）。

from shapely.geometry import Polygon
from scipy import sparse

intersection_bool = sparse.lil_matrix((len(grid_1),len(grid_2))),astype("bool")

for j in range(len(grid_2)):
    prepare(grid_2[j])
    for i, result in enumerate(intersects(grid_2[j], grid_1)):
        intersection_bool[i, j] = result


  [1]: https://shapely.readthedocs.io/en/2.0.0/release/2.x.html#strtree-api-changes-and-improvements
  [2]: https://shapely.readthedocs.io/en/2.0.0/reference/shapely.prepare.html