蟒蛇：排序多边形的两个列表交叉路口

我有多边形的两个大名单。使用python，我想获取列表1中的每个多边形，并找到它与列表2中的多边形的几何交集的结果（我正在使用shapely来做到这一点）。蟒蛇：排序多边形的两个列表交叉路口

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

问题是这两个列表都很大，如果我只是嵌套两个循环并为每个可能的多边形对运行交叉命令，则需要很长时间。我不确定在布尔测试之前交叉点是否会显着提高速度（例如，如果intersects：return intersection）。

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

我是比较新的规划，并在离散数学没有背景，所以如果你知道一个现有的算法，我应该使用，（我假设存在这类情况），请将链接或给予一定的解释，可以帮助我实际上在Python中实现它。

此外，如果有一个更好的StackExchange网站这个问题，让我知道。我觉得它像桥梁一般python编程，gis和几何，所以我不太确定。

来源

2011-01-24 BenjaminGolder

是凸多边形？ – 2011-01-24 00:16:53

它们的顶点可以形成凸或凹的角度，他们也有洞，但我可以很容易地使用他们的边界框是否会有所帮助。 – BenjaminGolder 2011-01-24 00:21:19

空间分区！四边形树或边界框上的体积kd树。 – 2011-01-24 00:21:44

Quadtrees通常用于缩小需要互相检查的多边形集合 - 如果两个多边形都占据至少一个相同的区域，则只需要检查两个多边形四叉树。你做四叉树的深度（多边形，而不是积分）取决于你。

来源

2011-01-24 00:23:19 Amber

即使只是将你的空间达到更小的固定大小的区域将加快路口检测（如果你的多边形足够小和稀疏）。您制作网格并将每个多边形标记为属于网格中的某些单元格。然后查找其中包含多个多边形的单元格，并仅对这些多边形进行交点计算。这种优化是最简单的代码，但最无效。第二种最简单和最有效的方法是四叉树。然后是BSP tres，KD树和BVH树，可能是最有效的，但最难编码的。

编辑：另一个优化如下：找出每个多边形的最左边和最右边的顶点并将它们放入一个列表中。对列表进行排序，然后从左向右循环，并轻松找到边界框的x坐标重叠的多边形，然后对这些多边形进行交集计算。

来源

2011-01-24 00:34:15 kynnysmatto

蟒蛇：排序多边形的两个列表交叉路口

回答

相关问题