python：对两个多边形列表的交集进行排序
我有两个大的多边形列表。
使用 python，我想获取列表 1 中的每个多边形，并找到其与列表 2 中的多边形的几何交集的结果（我使用 shapely 来做到这一点）。
因此，对于列表 1 中的多边形 i，列表 2 中可能有多个与其相交的多边形。
问题是两个列表都很大，如果我只是嵌套两个循环并为每个循环运行交集命令 可能的多边形对，这需要很长时间。我不确定在交集之前进行布尔测试是否会显着加快速度（例如，如果相交：返回交集）。
对我来说，对这两个多边形列表进行排序或组织以使相交的好方法是什么 更有效率？是否有适合这种情况的排序算法，并且我可以用 python 制作该算法？
我对编程比较陌生，并且没有离散数学背景，所以如果你知道现有的算法 我应该使用（我认为在这种情况下存在），请链接到或给出一些可以帮助我实际的解释 在Python中实现它。
另外，如果对于这个问题有更好的 StackExchange 站点，请告诉我。我觉得它有点像一般 python 编程、地理信息系统和几何的桥梁，所以我不太确定。
I have two big lists of polygons.
Using python, I want to take each polygon in list 1, and find the results of its geometric intersection with the polygons in list 2 (I'm using shapely to do this).
So for polygon i in list 1, there may be several polygons in list 2 that would intersect with it.
The problem is that both lists are big, and if I simply nest two loops and run the intersection command for every
possible pair of polygons, it takes a really long time. I'm not sure if preceding the intersection with a boolean test would speed this up significantly (e.g. if intersects: return intersection).
What would be a good way for me to sort or organize these two lists of polygons in order to make the intersections
more efficient? Is there a sorting algorithm that would be appropriate to this situation, and which I could make with python?
I am relatively new to programming, and have no background in discrete mathematics, so if you know an existing algorithm
that I should use, (which I assume exist for these kinds of situations), please link to or give some explanation that could assist me in actually
implementing it in python.
Also, if there's a better StackExchange site for this question, let me know. I feel like it kind of bridges general python programming, gis, and geometry, so I wasn't really sure.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
四叉树通常用于缩小需要针对每个多边形进行检查的多边形集的范围其他 - 如果两个多边形都占据四叉树中至少一个相同区域，则只需相互检查两个多边形。四叉树的深度（对于多边形，而不是点）取决于您。
Quadtrees are often used for the purpose of narrowing down the sets of polygons that need to be checked against each other - two polygons only need to be checked against each other if they both occupy at least one of the same regions in the quadtree. How deep you make your quadtree (in the case of polygons, as opposed to points) is up to you.
即使只是将空间划分为较小的恒定大小区域也会加快相交检测速度（如果您的多边形足够小且稀疏）。您创建一个网格并将每个多边形标记为属于网格中的某些单元格。然后找到其中包含多个多边形的单元格，并仅对这些多边形进行相交计算。这种优化是最容易编码的，但也是最无效的。第二个最简单且更有效的方法是四叉树。然后是 BSP tres、KD 树和 BVH 树，它们可能是最有效的，但最难编码。
编辑：
另一种优化如下：找出每个多边形的最左边和最右边的顶点，并将它们放入列表中。对列表进行排序，然后以某种方式从左到右循环它，轻松找到边界框 x 坐标重叠的多边形，然后对这些多边形进行相交计算。
Even just dividing your space up to smaller constant-size areas would speed up the intersection detection (if your polygons are small and sparse enough). You make a grid and mark each polygon to belong to some cells in the grid. And then find cells that have more than one polygon in them and make the intersection calculations for those polygons only. This optimization is the easiest to code, but the most ineffective. The second easiest and more effective way would be quadtrees. Then there are BSP tres, KD trees, and BVH trees that are probably the most effective, but the hardest to code.
Edit:
Another optimization would be the following: find out the left-most and the right-most vertices of each polygon and put them in a list. Sort the list and then loop it somehow from left to right and easily find polygons whose bounding boxes' x coordinates overlap, and then make the intersection calculations for those polygons.