從一組點創建凸層的Efficent算法

我有一個點，我試圖在python中生成凸層的列表。從一組點創建凸層的Efficent算法

目前我只是使用下列內容：

def convex_layers(points): 
    points = sorted(set(points)) 
    layers = [] 
    while points: 
     #Create the next convex hull 
     hull = convex_hull(points) 

     #Create the new list of points 
     for point in hull: 
     points.remove(point) 

     #Update the list of layers 
     layers.append(hull) 
    return layers

這僅僅是創建凸包一次一個。雖然它起作用，但看起來很像試圖通過重複添加來繁殖。所以我問的是，如果有一個更有效的算法專門用於從一組點創建凸層

來源

2012-11-09 Nuclearman

如果您使用monotone chain algorithm，則必須只進行一次詞典排序。然後可以在O（n）時間中找到每個連續層。這應該比每個圖層的排序更快。

來源

2012-11-09 04:08:37 Gene

有趣的是，我認爲可能是大約10分鐘前的事情。所以你說的是目前正在做的事情。所以也許它已經運行得儘可能好。更新了帖子反映了這一點。 – Nuclearman

那麼好吧，接受我的答案可能是適當的。謝謝。 – Gene

夠正確。儘管仍然認爲應該有一種方法來提高效率，避免必須繼續貫穿每一層的所有剩餘點。仍然可能不會有很大的改進。 – Nuclearman

你可以試試scipy spatial.convexHull。

或者，我發佈了一些code on GitHub。

來源

2013-05-25 19:05:21 octoback

這兩個都只產生凸包，這是強力凸層中的一個步驟。實際上我正在尋找類似[This pdf]中描述的算法（http://www.cs.princeton.edu/~chazelle/pubs/ConvexLayers.pdf）。儘管在接受上述答案後我確實找到了那篇文章，但我最終決定不在當時實施它，因此上述答案仍然被接受。 – Nuclearman

從一組點創建凸層的Efficent算法

回答

相關問題