ポリゴンの交差点の最適化のための最適化

Question

私は、地理的地図上に5〜2000頂点の10億個の2Dポリゴンを配置しました。私はマップの正方形の部分である四角形の範囲でこれらのポリゴンのカットアウトマスクを生成したいと思います。私は、四角形の境界に重なるすべてのポリゴンを収集し、次にマスクを作成し、四角形の境界と重なっていることが分かっているポリゴンのそれぞれを描画する素朴なコード化されたソリューションを持っています。

関連するコードは：

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) 

問題は、この計算は時間がかかりすぎるということである - 私は、大メモリ・マシン上で一つのマスクのために3時間のプログラムを実行しているし、それはまだ完了していません。最もコストのかかる操作は、重なっているポリゴンを計算することです。私は、コードは、とはっきりしないが重なっているものを除いて、ポリゴンのより小さなドメインを見て見ることができると思います。 poly_locatorの変数はpsyal.cg.locators.PolygonLocatorです。アドバイスをいただければ幸いです。私はPythonを使用することで地獄ではなく、C++に必要な機能があると思っています。

Answer 1

Lucanus SimonsonによるBOOST.polygonライブラリを強くお勧めします。多種多様なポリゴン相互作用を処理し、計算の複雑さが驚異的に減少します。 2-D問題の次元性を減らすためのSimonsonの革新的な計算は本当にきれいです。私の顎は彼の最初の提案の最後の20分程度開いたままにしておきました。