使用C查找多邊形的中軸＃

Question

我的任務是找出如何找到多邊形的中心線。我的谷歌搜索引導我相信，我需要的是'中軸'。就像這樣：

alt text http://www.ndl.kiev.ua/downloads/center_line.png

據我讀過，我需要可以通過使用二維Voronoi圖構建算法段生產什麼。

我已經找到了維諾算法的CodePlex上一個C＃版本（FortuneVoronoi）和應用我的多邊形來之後，我結束了這一點：

alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png

綠色是原來的多邊形。橙色是Voronoi頂點，黑色線是voronoi邊緣。

我可以看到我在這些頂點需要的材料，但我不確定是否需要下一步來過濾掉所有不需要的東西。

我很感謝您可以提供任何幫助。

Answer 1

一個簡單的解決方案是爲建議的意見：

1. 構建多邊形頂點的Delaunay三角。
2. 確定多邊形內部的頂點的Voronoi（見 http://en.wikipedia.org/wiki/Point_in_polygon）
3. 輸出的沃羅努瓦邊界連接兩個內部的Voronoi頂點。

如果您有大量數據，交叉點可能會非常昂貴。

然後你可以做類似的方法，如question，this solution也可以爲你工作。我會這樣做的方式：

1. 構建多邊形頂點的Delaunay三角剖分。
2. 插入未被delaunay邊緣覆蓋的每個多邊形邊的中點。以遞歸方式進行此操作，直到所有多邊形邊都被Delaunay邊覆蓋。
3. 標記對應於多邊形邊的所有Delaunay邊。
4. 使用步驟3至5提取中軸。在this solution

PS。注意，這兩個解決方案爲中軸的一些逼近，計算它到底是更昂貴，但作爲傳情......你可以得到這樣的結果黑色輸入採樣點：

Answer 2

哇。我將在這裏出現一個肢體，並建議可能該算法對內部與外部的多邊形感到困惑。在定義原始多邊形的邊和頂點時，必須確保它們的定義方式是「內部」總是使用類似於「右手規則」的方式來找到。只要看看右下角的多邊形，看起來多邊形的邊緣實際上是交叉的。也許該算法將該部分和其他部分視爲「內外」。左下角也是一樣。

這是我的直覺，算法似乎無法確定內部和外部的方向。

我認爲一種天真的方法是過濾出多邊形之外的所有Voroni「節點」，但是，我不認爲這會看起來。仔細看看你的圖，看起來每個節點都有3條邊連接到其他節點。也許你可以過濾掉任何3個邊連接到多邊形外的節點的節點。這會起作用嗎？

Answer 3

一個類似的結構是Straight skeleton，它可以通過縮小多邊形到自身中並在頂點接近中心時跟蹤來構建。這可能會更容易構建，儘管它與中軸不完全相同。