簡化凹船體

Question

問題：

鑑於：n表示強相關於一個三維的k雙面非凸多邊形，其中n >> K

查找點：最適合的凹殼，該點

---

嘗試的解決方案的原始幾何匹配：

警告：僞

segments = [] 
for each point in image: 
    #segment points into planes via comparing approximate normals 
    #actual implementation is more complicated 
    findSegment(image,point) 
for each segment in image: 
    #transform coordinate system to be a 
    #2D-plane perpendicular to the normal of segment 
    transform(segment, segment.normal) 
    edges = findEdges(segment) 
    polygonHull = reconstructPolygon(edges) 
    #transform back to original coordinate system 
    transform(segment, segment.normal) 

---

實施例：

___ 
| |    | 
| \__ ==>  | ___ 
|  |   |__/ /_____ 
|_______|  // \_ 
       //_____/ 
       /

輸入將是簡單地高密度點雲被近似均勻地內分佈的隨機點多邊形平面，機智有點噪音。

輸出將是3d點中多邊形的頂點。

---

我的問題是，有沒有更好的方法來解決這個問題？上述解決方案的問題是點可能很嘈雜。此外，將點光柵化爲2d，然後預先形成邊緣查找代價非常高。

任何指針都會很棒。在此先感謝

Answer 1

如果你的凹角不太銳利，我可能會嘗試在點集上做一個3d Delaunay三角測量。邊界上的點的Voronoi區域往往是無限的或比內部的要長得多。相似地，與多面體單面相關聯的邊界上的單元格將傾向於以與它們相關聯的面接近垂直的方向對齊，因爲它們將是漫長而薄的，並且它們的長軸將是幾乎平行並指出多邊形。在有點兒八九不離十準僞

Compute Delaunay triangulation 
Collect long thin Voronoi regions 
Partition the Voronoi regions into clusters that are nearby and nearly parallel. 
Create faces normal to the axes of the Voronoi regions. 

編輯現在我看你只是想要一個多邊形。上述方法有效，但最好分兩步進行。首先找到多邊形所在的平面，做一個點的小樣本的最小二乘擬合可能足夠好。將點投影到飛機上（這幾乎是你所做的），然後計算二維Delaunay三角剖分以找到邊緣點並繼續如上所述。

Answer 2

這聽起來像你想計算投影到飛機上的三維空間中的一組點的凹殼。 2D案例在一些細節here中進行了討論。

Answer 3

首先你要爲你的網格選擇一個表示。在2D中，我使用這種表示實現了一個Python凹面算法：half-edge data structure。

然後，算法2D（你應該適應3D）可以接近to alpha shape algorithm, by Edelbrunner.