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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

即使只是将你的空间分割成更小的恒定大小区域，也会加快交叉点检测（如果你的多边形足够小和稀疏）。创建网格并将每个多边形标记为属于网格中的某些单元。然后找到包含多个多边形的单元格，并仅对这些多边形进行交集计算。这种优化是最容易编写代码的，但效率最高。第二个简单有效的方法是四叉树。还有BSP树、KD树和BVH树，它们可能是最有效的，但最难编写代码。在

编辑： 另一个优化方法是：找出每个多边形最左边和最右边的顶点，并将它们放入一个列表中。对列表排序，然后以某种方式从左到右循环，很容易找到边界框的x坐标重叠的多边形，然后计算这些多边形的交集。在