python:为交叉点排序两个多边形列表

Question

我有两大多边形列表。

使用 python，我想获取列表 1 中的每个多边形，并找到它与列表 2 中的多边形的几何交集结果(我正在使用 shapely 来执行此操作)。

因此对于列表 1 中的多边形 i，列表 2 中可能有多个多边形会与其相交。

问题是两个列表都很大，如果我简单地嵌套两个循环并为每个循环运行交集命令可能的一对多边形，这需要很长时间。我不确定在交集之前进行 bool 测试是否会显着加快速度(例如，如果相交:返回交集)。

对我来说，对这两个多边形列表进行排序或组织以形成交点的好方法是什么？更高效？是否有适合这种情况的排序算法，我可以用 python 制作？

我对编程比较陌生，没有离散数学的背景，所以如果你知道一个现有的算法 我应该使用，(我假设在这些情况下存在)，请链接到或给出一些可以帮助我实际的解释在 python 中实现它。

另外，如果这个问题有更好的 StackExchange 站点，请告诉我。我觉得它有点像通用 python 编程、gis 和几何学的桥梁，所以我不太确定。

Answer 1

Quadtrees通常用于缩小需要相互检查的多边形集的范围 - 如果两个多边形都至少占据四叉树中的相同区域之一，则它们只需要相互检查。四叉树的深度(在多边形的情况下，而不是点)由您决定。