Python性能问题：两个多边形之间的差异

Question

我目前正在使用Python 3.7，我想找到许多多边形之间的区别。我的意思是，如果我有一个多边形A和一个多边形B，我想进行数学“ A not B”操作。如下图所示，此操作有两种可能的结果：

所以我互相减去（“切割”）的两个多边形给了我一个新的多边形或为空。所有其他情况都可以忽略。对于情况1，多边形的形式为不需要精确]。因此，如果多边形稍有变化，则可以接受。

对于情况2，我需要知道多边形是否为空。

此外，多边形A和B中没有任何“孔”，因此只能用其外部边界来描述。

我已经建立了一个使用the difference operation of shapely来完成此任务的原型。我尽可能地“切割”尽可能少（每两个多边形一次）。

我的代码有点复杂，但是基本上可以分解为这个简单的功能：

difference
现在我的问题是，这非常慢！我每批处理大约[[15.000
个操作（30.000个多边形），我大约需要10到15分钟来计算它们。我真的很想不到5分钟。

[请注意，这并不说明所有其他操作。 15分钟仅用于差异操作。我可以在1分钟内将每个多边形A排序到每个多边形B。我只是需要一种快速的方法来从这些结果中得到多边形。

我使用一台“好的”计算机（英特尔酷睿i7，16 GB Ram）进行了此测试。 CPU或RAM均未达到极限。

所以，最大的问题是：我该如何加快速度？

是否有一种方法可以将多边形转换为更易于处理的形式？还是有一种“更好”的方法来获取两个多边形的差？

是否有其他更好的库？还是可以整齐地使用其他硬件？如果是这样，那可能是哪种硬件？

最后，下一步是尝试并行化“剪切”。有内置的方法可以快速有效地执行此操作吗？因为我找不到身材匀称的人。

此外，我也非常感谢您提供分析可能的瓶颈的技巧。

附录：

某些多边形似乎相当复杂。我的意思是，平均而言，较复杂的多边形平均包含15.000个点。不复杂的多边形小于100点。但是，通常（如99％），多边形A或B在同一时间并不复杂。

def cut_hole(A : Polygon, B : Polygon) -> Polygon:
    """
    Cuts a "hole" into shapely polygon A
    :return: The polygon resulting of the operation A-B. Might be empty!
    """
    outer = A #not in my code, just to point out what I mean
    inner = B
    return outer.difference(inner)

我目前正在使用Python 3.7，我想找到许多多边形之间的区别。我的意思是，如果我有一个多边形A和一个多边形B，我想做数学上的“ A不是B” ...

Answer 1

按顺序整理要点：

• 我非常怀疑还有另一种更适合使用python处理多边形而不是用多边形的格式/库，它是参考包。您可以尝试Here is an example of an complex polygon in WKT您的几何图形，但是一些快速测试表明它也是一个缓慢的操作（simplify是您上面复制粘贴的多边形）：