多边形相交的更快方法

Question

我有大量的多边形（〜100000），并尝试找到一种聪明的方法来计算与常规网格单元的相交面积。

当前，我正在使用形状（基于它们的角坐标）来创建多边形和网格单元。然后，使用简单的for循环，遍历每个多边形并将其与附近的网格单元进行比较。

只是一个小例子来说明多边形/网格单元。

from shapely.geometry import box, Polygon
# Example polygon 
xy = [[130.21001, 27.200001], [129.52, 27.34], [129.45, 27.1], [130.13, 26.950001]]
polygon_shape = Polygon(xy)
# Example grid cell
gridcell_shape = box(129.5, -27.0, 129.75, 27.25)
# The intersection
polygon_shape.intersection(gridcell_shape).area

（顺便说一句：网格单元的尺寸为0.25x0.25，多边形的最大值为1x1）

实际上，对于单个多边形/网格单元组合来说，这非常快，大约需要0.003秒。但是，在我的机器上在大量的多边形上运行此代码（每个多边形可以相交数十个网格单元）大约需要15+分钟（取决于相交的网格单元的数量，最多需要30+分钟），这是不可接受的。不幸的是，我不知道如何为多边形相交编写代码以获取重叠区域。你有什么建议吗？除了身材外，还有其他选择吗？

Answer 1

考虑使用Rtree帮助确定多边形可以相交的网格单元。这样，您可以删除经纬度数组使用的for循环，这可能是最慢的部分。

构造代码如下：

from shapely.ops import cascaded_union
from rtree import index
idx = index.Index()

# Populate R-tree index with bounds of grid cells
for pos, cell in enumerate(grid_cells):
    # assuming cell is a shapely object
    idx.insert(pos, cell.bounds)

# Loop through each Shapely polygon
for poly in polygons:
    # Merge cells that have overlapping bounding boxes
    merged_cells = cascaded_union([grid_cells[pos] for pos in idx.intersection(poly.bounds)])
    # Now do actual intersection
    print(poly.intersection(merged_cells).area)