优化多边形交点查找

Question

我有大约10亿个2D多边形，每个顶点有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_locator变量是psyal.cg.locators.PolygonLocator s。任何意见，将不胜感激。我不想使用Python，并认为C++可能具有我需要的功能。

Answer 1

我强烈推荐Lucanus Simonson的BOOST.polygon库。它处理各种多边形相互作用，计算复杂度惊人地降低。 Simonson创新的微积分技术可以降低二维问题的维度，实际上非常简洁;在他最初提议的最后20分钟左右，它留下了我的下巴。