Python：对两个多边形列表进行排序以寻找交点
我有两个很大的多边形列表。
我想用Python来处理第一个列表中的每个多边形，找出它与第二个列表中多边形的几何交集（我在用shapely来实现这个功能）。
也就是说，对于列表1中的每个多边形i，在列表2中可能会有几个多边形与它相交。
问题是这两个列表都很大，如果我简单地用两个循环来检查每一对多边形的交集，这样会花费很长时间。我不确定在进行交集计算之前加一个布尔测试（比如：如果相交就返回交集）是否能显著加快速度。
那么，有什么好的方法可以帮助我对这两个多边形列表进行排序或组织，以便让交集计算更高效呢？有没有适合这种情况的排序算法，我可以用Python来实现？
我对编程还比较陌生，也没有离散数学的背景，所以如果你知道有现成的算法可以使用（我想这种情况应该有现成的算法），请给我一个链接或者简单解释一下，帮助我在Python中实现它。
另外，如果有更合适的StackExchange网站来问这个问题，请告诉我。我觉得这个问题涉及到Python编程、地理信息系统和几何，所以我不太确定该问哪里。
2 个回答
把你的空间划分成更小的固定大小区域，可以加快交集检测的速度（如果你的多边形足够小且分散）。你可以创建一个网格，然后把每个多边形标记到网格中的某些单元格里。接着，找出那些有多个多边形的单元格，只对这些多边形进行交集计算。这种优化方法是最简单的，但效果不是很好。第二简单且效果更好的方法是使用四叉树。还有一些像BSP树、KD树和包围体层次树（BVH树）这样的结构，它们可能是最有效的，但编写起来是最复杂的。
编辑： 另一种优化方法是：找出每个多边形最左边和最右边的顶点，并把它们放在一个列表里。然后对这个列表进行排序，再从左到右循环遍历，轻松找到那些边界框的x坐标重叠的多边形，然后对这些多边形进行交集计算。
四叉树常常用来减少需要相互检查的多边形的数量。只有当两个多边形至少占据四叉树中的同一个区域时，它们才需要进行相互检查。至于你想把四叉树分得多深（在处理多边形而不是点的时候），这完全取决于你自己。