python:排序相交的两个多边形列表

Question

我有两个多边形的大列表。在

使用python，我希望获取列表1中的每个多边形，并找到其与列表2中的多边形的几何交集结果（我使用shapely来完成此操作）。在

因此，对于列表1中的polygoni，列表2中可能有几个多边形与它相交。在

问题是这两个列表都很大，如果我简单地嵌套两个循环并对每个循环运行交集命令 可能是一对多边形，需要很长时间。我不确定在交集之前进行布尔测试是否会显著加快速度（例如，if intersects:return intersection）。在

对我来说，什么是一个好的方法来排序或组织这两个多边形列表，以便使交叉点 效率更高？有没有一个适合这种情况的排序算法，我可以用python做这个？在

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

另外，如果有更好的StackExchange网站来回答这个问题，请告诉我。我觉得这有点像是连接一般python编程、gis和几何的桥梁，所以我不太确定。在

Answer 1

Quadtrees通常用于缩小需要相互检查的多边形集的范围-仅当两个多边形都占据四叉树中相同区域中的至少一个时，才需要对照它们进行检查。四叉树的深度（对于多边形，与点相反）取决于您。在