多边形求交的优化方法

Question

我有大约10亿个二维多边形，每个都有5到2000个顶点，分布在地理地图上。我想在四边形的有界范围内生成这些多边形的剪切遮罩，这是地图的正方形部分。我有一个简单的编码解决方案，它收集了所有与四边形边界重叠的多边形，然后创建了一个遮罩并绘制了每个它发现与四边形边界重叠的多边形。在

相关代码：

def generate_alteration_layers_by_extent(alterations, poly_locators, extents, output_res=1000):
    left, right, upper, lower = extents
    query_rectangle = pysal.cg.shapes.Rectangle(left, lower, right, upper)
    num_layers = len(shapes_by_alterations)
    boxed_alteration_layers = []
    for i, (alteration, poly_locator) in enumerate(zip(alterations, poly_locators)):
        print "computing overlapping polygons"
        overlapping_polys = poly_locator.overlapping(query_rectangle)
        print "drawing polygons onto mask"
        img = Image.new('L', (output_res, output_res), 0)
        polys = [np.array(map(list, poly.vertices)) for poly in overlapping_polys]
        for poly in polys: 
            # normalize to the dimensions of img
            poly[:,0] -= left;  poly[:,0] *= (right-left); poly[:,0] *= output_res
            poly[:,1] -= lower; poly[:,1] *= (upper-lower); poly[:,1] *= output_res
            ImageDraw.Draw(img).polygon(poly, outline=1, fill=1)
        mask = np.array(img)
        boxed_alteration_layers.append(mask)
    return np.dstack(boxed_alteration_layers)

问题是这个计算时间太长了——我在一个大内存机器上为一个掩模运行了三个小时的程序，但仍然没有完成。最昂贵的操作是计算重叠多边形。我认为代码可以通过查看较小的多边形域，排除搜索那些绝对不会重叠的多边形。 注意poly_定位器变量是psyal.cg.locators.PolygonLocators。如有任何建议，我们将不胜感激。我并没有热衷于使用Python，并认为C++可能具有我需要的功能。在

Answer 1

我强烈推荐lucanussimonson的BOOST.polygon库。它可以处理各种多边形交互，计算复杂度惊人地降低。西蒙森用创新的微积分来减少二维问题的维数，真是妙不可言；在他最初的提议的最后20分钟左右，我的下巴都睁大了。在