優化多邊形交點查找

我有大約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++可能具有我需要的功能。

來源

2017-04-03 Nikhil Shinday

我強烈推薦Lucanus Simonson的BOOST.polygon庫。它處理各種多邊形相互作用，計算複雜度驚人地降低。 Simonson創新的微積分技術可以降低二維問題的維度，實際上非常簡潔;在他最初提議的最後20分鐘左右，它留下了我的下巴。

來源

2017-04-03 17:41:06 Prune

唯一的問題是：「庫中實現的算法不支持浮點座標數據類型，這是因爲實現浮點健壯性意味着一組不同的算法，並且通常關於浮點表示的平臺特定假設「。我的多邊形座標是緯度/經度 - 關於如何解決這個問題的任何建議？ –

當然;乘以任何因素保留您需要的精度。做多邊形數學。當你得到結果時，按相同的因子劃分。例如，轉換爲弧的毫秒數。您的多邊形是否足夠小以至於您可以將它們視爲平面而不是球面？ **多邊形**庫假定歐幾里德幾何。 – Prune

優化多邊形交點查找

回答

相關問題