中軸線算法總結

參考文檔：

1. 《確定任意多邊形中軸的算法》

2. 《多邊形坡屋頂屋脊線生成的算法研究》

3. 《清華陳宇軍的多坡屋頂》

?

生成中軸線，如果使用全遞歸的情況，則最壞情況算法的計算量為N!，就當前的計算量來說，僅10個邊的計算量為3628800(10*9*8*7*6*5*4*3*2*1)，計算量對當前的計算機來說，負荷是非常重的。

如何來提高效率，就是確保最先找的中軸是真確的中軸，如果每次都能找到正確的中軸，則對于10個邊，僅需要10次就可以尋找中軸成功。所以提高效率的關鍵在于及早識別出正確的中軸線：

在參考文檔1/2中看到兩個思路：

1.?????? 離邊最近的角平分線交點，為正確中軸線交點的概率最高

2.?????? 找到一條中軸線后，向兩邊延伸獲取角兩個平分線交點，離上一個點較近的點為正確中軸線交點的概率較高，高于1的概率

?

結合參考文檔3和實踐，再增添兩個思路：

3.?????? 影響提前檢測：在2中，附加檢測選中點對其相鄰邊的影響，如果相鄰邊角平分線與選中點形成的中軸交叉，則意味著相鄰邊受該邊影響，后續無法再生成中軸，所以置該點無效---用于提前檢測到無效中軸。

4.?????? 回溯思路：在1中，檢測相同條件下，曾經選中過的邊長度置為最大-不可重新選中---用于彌補算法部分情況出現死循環。

?

結合兩個新的思路，對多邊形中軸線的生成速度上會提高不少，對于一些圖形可以較快生成中軸線。

?

歡迎大家探討，提供新的思路。

?

Owed by: 春夜喜雨?http://blog.csdn.net/chunyexiyu??轉載請標明來源?

????????

總結

以上是生活随笔為你收集整理的中轴线算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。