python - 如果点和多边形具有相同的最小边界框，则用于查找多边形内的点的空间索引

Question

我有一个形状优美的多边形，代表洛杉矶市的边界。我还在 geopandas GeoDataFrame 中拥有一组约 100 万个经纬度点，所有这些点都落在该多边形的最小边界框内。其中一些点位于多边形本身内，但其他点则不在多边形内。我只想保留洛杉矶边界内的那些点，并且由于洛杉矶的形状不规则，其最小边界框中只有大约 1/3 的点位于多边形本身内。

考虑到这些点和多边形具有相同的最小边界框，使用 Python 来识别哪些点位于多边形内的最快方法是什么？

我尝试使用 geopandas 及其 r-tree 空间索引:

sindex = gdf['geometry'].sindex
possible_matches_index = list(sindex.intersection(polygon.bounds))
possible_matches = gdf.iloc[possible_matches_index]
points_in_polygon = possible_matches[possible_matches.intersects(polygon)]

这使用 GeoDataFrame 的 r-tree 空间索引来快速查找可能的匹配项，然后找到多边形与这些可能匹配项的精确交集。但是，由于多边形的最小边界框与点集的最小边界框相同，因此 r-tree 认为每个点都是可能的匹配。因此，使用 r 树空间索引使得交集的运行速度不会比没有空间索引时快。此方法非常慢:大约需要 30 分钟才能完成。

我还尝试将多边形划分为小的子多边形，然后使用空间索引来查找哪些点可能与每个子多边形相交。该方法成功地找到了较少的可能匹配，因为每个子多边形的最小边界框比点集最小边界框小得多。然而，将这组可能的匹配与我的多边形相交仍然只减少了大约 25% 的计算时间，因此这仍然是一个极其缓慢的过程。

我应该使用更好的空间索引方法吗？如果点和多边形具有相同的最小边界框，那么找到多边形内的点的最快方法是什么？

Answer 1

总结一下这个问题:当多边形的边界框与点集相同时，r-tree 将每个点识别为可能的匹配，因此不会提供任何加速。当与大量点和具有大量顶点的多边形结合使用时，相交过程极其缓慢。

解决方案:从此geopandas r-tree spatial index tutorial ，使用样方例程将多边形划分为子多边形。然后，对于每个子多边形，首先将其与点的 r 树索引相交以获得一小组可能的匹配，然后将这些可能的匹配与子多边形相交以获得精确匹配的集合。这提供了大约 100 倍的加速。