基于角平分線的無孔復(fù)雜多邊形中軸提取算法

黃斌 劉軍 范啟東 唐嘉胤

摘要：中軸可以有效表達(dá)多邊形拓?fù)浣Y(jié)構(gòu)信息，同時(shí)可以去除冗余信息，并且具備對(duì)局部幾何變形不敏感等特點(diǎn)，吸引了學(xué)術(shù)界的廣泛重視。但現(xiàn)有的中軸提取方法存在計(jì)算資源消耗大，運(yùn)行速度慢，數(shù)據(jù)不穩(wěn)定等問題。本文在現(xiàn)有草火模型及最大圓盤模型的基礎(chǔ)上，提出了一種基于角平分線的無孔復(fù)雜多邊形中軸提取算法。該算法利用多邊形凹凸點(diǎn)的偏置處理來獲得中間分支點(diǎn)，然后通過“手?jǐn)D”方式獲得中軸，并利用邊界的連續(xù)性保持中軸的連續(xù)性。實(shí)驗(yàn)結(jié)果表明該算法能滿足中軸的提取并能保持中軸的連續(xù)性，而且減少了自交檢測的復(fù)雜程度。

Abstract The central axis has the characteristics of effectively expressing the topological structure and geometric information of polygons， removing redundant information， and not sensitive to local deformation， which has attracted extensive attention of academia. There are many problems in the existing methods， such as large consumption of computing resources， slow running speed， and data instability and so on. In this paper， based on the existing grass fire model and the largest disk model， an algorithm of extracting the central axis of complex polygon without hole based on angle bisector is proposed. The algorithm uses the offset processing of polygon concave and convex points to obtain the middle branch points， then uses the way of "hand extruding" the boundary to obtain the central axis， and uses the continuous topological structure of the boundary to maintain the continuity of the central axis. The experimental results show that the algorithm can meet the requirements of axis extraction and maintain the continuity of the axis， and reduce the complexity of self-intersection detection.

1. 引言

隨著CAD/CAM/CAE的應(yīng)用日趨廣泛及計(jì)算機(jī)圖形學(xué)的不斷發(fā)展，利用多邊形對(duì)數(shù)字模型進(jìn)行表達(dá)的方式在實(shí)際應(yīng)用中越來越多。但該表達(dá)方式會(huì)隱藏模型的關(guān)鍵信息，不利于拓展模型的應(yīng)用。另外，數(shù)字模型通常蘊(yùn)含巨大的數(shù)據(jù)量，對(duì)模型上所有數(shù)據(jù)進(jìn)行操作，如重建運(yùn)動(dòng)場景，分析結(jié)構(gòu)受力，規(guī)劃加工路徑等，對(duì)于大多數(shù)硬件設(shè)備都是一個(gè)巨大的挑戰(zhàn)[1-3]。對(duì)于數(shù)量級(jí)巨大的多邊形模型，如果要以常規(guī)硬件實(shí)現(xiàn)大數(shù)據(jù)處理，就需要將模型的結(jié)構(gòu)信息濃縮，并從中提取核心數(shù)據(jù)，然后以現(xiàn)有硬件進(jìn)行有限數(shù)量級(jí)別操作，最后將操作數(shù)據(jù)逆向重建，實(shí)現(xiàn)數(shù)量巨大的多邊形模型處理。

結(jié)構(gòu)信息濃縮概念在日常生活中并不少見，例如人類肢體及機(jī)械結(jié)構(gòu)的運(yùn)動(dòng)簡圖。人類運(yùn)動(dòng)可以看成是忽略神經(jīng)系統(tǒng)和肌肉細(xì)胞控制作用的骨骼運(yùn)動(dòng);而機(jī)械結(jié)構(gòu)也可以將復(fù)雜的零件特征簡化為抽象線框。因此，結(jié)構(gòu)信息濃縮的概念也可以用于將多邊形模型濃縮為抽象的骨架線框。從多邊形中抽取出的骨架線框，學(xué)術(shù)界將其定義為多邊形中軸。多邊形中軸由于包含著豐富的幾何機(jī)構(gòu)信息，可以直接應(yīng)用于科學(xué)工程領(lǐng)域，包括地理信息系統(tǒng)、人臉識(shí)別、圖像處理、計(jì)算機(jī)視覺和機(jī)械結(jié)構(gòu)分析等[4]。

多邊形中軸的提取模型主要有兩種：草火模型和最大圓盤模型。草火模型是假設(shè)圖形的邊界同時(shí)點(diǎn)火，火源向圖形內(nèi)部各個(gè)方向等速燃燒直至熄滅，熄滅點(diǎn)形成的點(diǎn)集為多邊形的中軸[5];而最大圓盤模型是指平面幾何圖形中的中軸是內(nèi)切于幾何圖形邊界至少兩個(gè)或兩個(gè)以上等距離的點(diǎn)的軌跡[4]。

多邊形中軸具備有效表達(dá)多邊形的拓?fù)浣Y(jié)構(gòu)和幾何信息，同時(shí)可以去除冗余信息，并且對(duì)局部變形不敏感等特點(diǎn)，吸引了學(xué)術(shù)界的廣泛重視。而中軸提取更是眾多研究學(xué)者關(guān)注的焦點(diǎn)，合理快速的中軸提取算法一直是學(xué)術(shù)界及工業(yè)界追求的目標(biāo)。本文將在草火模型和最大圓盤模型的基礎(chǔ)上提出一種基于角平分線的改良中軸提取算法。

2. 相關(guān)工作

目前對(duì)多邊形中軸的提取方法都是基于草火模型和最大圓盤模型，常用的中軸提取方法包括有形態(tài)學(xué)細(xì)化法[6]、拓?fù)溥壿嬍萆矸ǎ╰opological thinning）[7]、距離變換法（distance transform/DT）[8]、草火法（simulations of grassfire propagation）[5]、泰森多邊形法（Voronoi diagram）等[9]。而從計(jì)算精度來看，眾多的中軸提取方法大致可以分為精確算法和逼近算法兩類[12]。

精確中軸提取算法包括形態(tài)學(xué)細(xì)化法、拓?fù)溥壿嬍萆矸ā⒕嚯x變換法等。形體學(xué)細(xì)分法屬于圖像處理范疇，通過膨脹、腐蝕、開閉運(yùn)算、擊中或擊不中變換、細(xì)化、骨架及重構(gòu)對(duì)象等一系列運(yùn)算獲得最終的中軸圖形[1]。形態(tài)細(xì)化法最常用的就是最大圓盤法[6]，通過多邊形內(nèi)所有最大圓盤的圓心提取多邊形的中軸，但存在著連通性不佳的缺點(diǎn)。拓?fù)溥壿嬍萆矸╗7]是在形態(tài)學(xué)細(xì)化法的基礎(chǔ)上發(fā)展出來的中軸提取方法，通過逐步去掉簡單點(diǎn)（不影響拓?fù)湫再|(zhì)和形狀的點(diǎn)）而獲得中軸，但其僅能保證在二維空間的正確性。距離變換法是通過尋找距離梯度脊線來形成骨架，該方法得到的骨架位置精確，但難以保證骨架的連通性。但精確中軸提取算法多采用全局遍歷法，存在計(jì)算資源消耗大，運(yùn)行速度慢等問題;另外一些精確中軸提取算法將圖形進(jìn)行分割成簡單多邊形，然后提取中軸，最后將各部分中軸融合成為最終的總中軸，則在中軸融合時(shí)出現(xiàn)準(zhǔn)確性不佳及計(jì)算復(fù)雜等問題。

針對(duì)精確中軸提取算法存在的問題，研究人員相繼開發(fā)出效率更高的逼近算法。逼近算法主要包括擴(kuò)展草火法[13]、泰森多邊形法[9]、Delaunay三角剖分法[10]和柵格法等。擴(kuò)展草火法采用類似草火法的統(tǒng)一方法來定義二維中軸全局形狀度量（EDF）及二維形狀的中心（EMA），并通過厚度腐蝕方法得到圖形的中軸。該方法在修剪中軸、對(duì)齊形狀和形狀描述方面的具有一定的實(shí)用性。泰森多邊形法[9]將復(fù)雜多邊形界線分解成點(diǎn)集，然后通過這些點(diǎn)集構(gòu)成泰森多邊形圖（Voronoi diagram），泰森多邊形圖在多邊形內(nèi)的公共邊即是多邊形的中軸，但該方法依賴于規(guī)模或密度。Delaunay三角剖分法[10]利用Delaunay三角剖分的空球特性（平面上是圓），對(duì)邊界點(diǎn)集細(xì)化，以提取多邊形的中軸。柵格法[11]則通過最近邊緣點(diǎn)集距離的均值變換，結(jié)合新的中軸點(diǎn)判定規(guī)則，利用種子點(diǎn)生長判別法提取曲邊多邊形的中軸。但基本上使用逼近中軸提取算法均存在數(shù)據(jù)提取不穩(wěn)定的缺點(diǎn)，迄今為止還沒得到很好的解決。

3. 理論算法

針對(duì)上述精確及逼近中軸提取算法的不足，本文利用結(jié)合角平分線的概念及多邊形邊界拓?fù)溥B續(xù)性，實(shí)現(xiàn)無孔復(fù)雜多邊形的中軸提取。無孔復(fù)雜多邊形的中軸提取的理論主要分為以下四個(gè)基本算法：多邊形凹凸判斷算法，凸多邊形偏置算法，非凸多邊形 偏置算法，及中軸重構(gòu)算法。

3.1 多邊形凹凸判斷算法

要從復(fù)雜的封閉多邊形進(jìn)行中軸提取，首先要定義一個(gè)實(shí)體方向的概念。

多邊形實(shí)體方向定義（如圖1）：

多邊形的邊界線段是有向線段或多段線。

有向線段或多段線的前進(jìn)方向的左側(cè)為實(shí)體，則該線段或多段線的前進(jìn)方向?yàn)槎噙呅蔚膶?shí)體方向。

要確定多邊形的凹凸性。在各種多邊形中軸定義模型中，多邊形的輪廓實(shí)體方向的凸點(diǎn)存在中軸，凹點(diǎn)不存在中軸;但凹凸點(diǎn)也會(huì)影響中軸的位置，因此需要對(duì)多邊形的凹凸性進(jìn)行判斷。

多邊形頂點(diǎn)凹凸性判斷方法主要有角度法、左右點(diǎn)法、矢量面積法、向量積法、射線法和極點(diǎn)順序法等[14]，這些算法基本上是等效的。本文采用的是向量積法來判斷多邊形頂點(diǎn)的凹凸性。如圖1所示，邊界ABC（C）的左側(cè)為實(shí)體，頂點(diǎn)C位于矢量線段AB的左側(cè)，則計(jì)算向量AB和向量BC的外積，外積公式采用：

向量BD的單位向量與z軸的正方向相同，這時(shí)多邊形的頂點(diǎn)屬于凸頂點(diǎn)。而對(duì)于頂點(diǎn)C而言，其位置位于矢量線段AB的右側(cè)，向量BD的單位向量與z軸的正方向相反，這時(shí)多邊形的頂點(diǎn)屬于凹頂點(diǎn)。

由于多邊形的輪廓上有多個(gè)頂點(diǎn)，因此必須采用歷遍法對(duì)各個(gè)頂點(diǎn)進(jìn)行凹凸性判斷，并最終確定多邊形的凹凸性：若全部頂點(diǎn)均為凸頂點(diǎn)，那么，該多邊形為凸多邊形;反之，若多邊形上存在一個(gè)或以上的凹頂點(diǎn)，該多邊形為非凸多邊形。

3.2凸多邊形偏置算法

草火模型和最大圓盤模型均采用其描述方式對(duì)多邊形的中軸進(jìn)行定：草火模型采用的是由外至內(nèi)的距離延伸方法，而最大圓盤模型采用的是相反的由內(nèi)至外的距離延伸方法。通過比較兩種定義方法，可以發(fā)現(xiàn)其最終的目標(biāo)都是在尋找距離相等的點(diǎn)或線段。而在平面幾何學(xué)中，角平分線的性質(zhì)就剛好滿足這一要求，如圖2。林福嚴(yán)等[15]利用這角平分線的性質(zhì)提出了一種平面凸多邊形中軸提取方法，但該方法的判據(jù)并未考慮多邊形的特殊情況。而這里提出的凸多邊形偏置算法是在林福嚴(yán)等提出的方法上進(jìn)行改良，將多邊形的特殊情況也進(jìn)行考慮。

凸多變形偏置算法描述如下：

步驟1：尋找凸多邊形的最小厚度。

（1） 按凸多邊形實(shí)體方向獲取各頂點(diǎn)的坐標(biāo)，然后計(jì)算每一個(gè)頂點(diǎn)的角平分線的單位向量，求出兩頂點(diǎn)間線段與兩頂點(diǎn)法向量所構(gòu)成的三角形的高（圖3）。三角形的高的計(jì)算公式如下：

（2） 比較凸多邊形上所有輪廓線段對(duì)應(yīng)三角形的高，尋找最小值，作為多邊形的最小厚度。凸多邊形頂點(diǎn)角平分線與頂點(diǎn)簡單的多邊形輪廓線段構(gòu)成了三角形，三角形對(duì)應(yīng)高的最小值選擇方式如下：

（3） 求出最小厚度所在的三角形上由兩多邊形頂點(diǎn)角平分線構(gòu)成的頂點(diǎn)坐標(biāo)，作為中軸線的中間分支點(diǎn)。計(jì)算方式如下（以圖2為例，A為第一個(gè)中間分支點(diǎn)）：

步驟2：尋找第一個(gè)無自交的凸多邊形環(huán)。

（1） 按凸多邊形實(shí)體方向?qū)γ總€(gè)頂點(diǎn)角平分線進(jìn)行截點(diǎn)計(jì)算。計(jì)算方式如下：

（2） 按凸多邊形頂點(diǎn)的拓?fù)潢P(guān)系對(duì)截點(diǎn)進(jìn)行連接，構(gòu)成了一個(gè)新的凸多邊形（圖4）。由于最小厚度所在三角形對(duì)應(yīng)的凸多邊形輪廓線段已退化成一點(diǎn)，如圖7的V1、V2兩點(diǎn)退化成P1點(diǎn)，新凸多邊形的邊數(shù)為N-1。

圖4利用截點(diǎn)的拓?fù)潢P(guān)系形成新的凸多邊形。

步驟3：找出所有中間分支點(diǎn)。 重復(fù)步驟1和2，找出所有無自交的凸多邊形環(huán)及所有的中間分支點(diǎn)，直到多邊形上所有頂點(diǎn)退化到一點(diǎn)。這時(shí)，中間分支點(diǎn)到其對(duì)應(yīng)的多邊形輪廓線段的距離為多邊形在該輪廓線段上的最大厚度。

3.3非凸多邊形偏置算法

凸多邊形僅是多邊形中的特例，而實(shí)際上更多存在的是非凸多邊形。非凸多邊形的偏置算法長期以來都是以一個(gè)難以解決的問題，而問題關(guān)鍵是在于如何處理非凸多邊形輪廓在偏置后出現(xiàn)的自交現(xiàn)象。自交現(xiàn)象產(chǎn)生的原因是由于偏置距離設(shè)置與輪廓線拓?fù)浣Y(jié)構(gòu)的相互影響而產(chǎn)生的，如圖5。正常情況下，輪廓ABCD在偏置d1距離后會(huì)生成偏置曲線ABCD，如圖5（a），但若偏置距離過大時(shí)，輪廓ABCD的偏置曲線ABCD在保持原有拓?fù)浣Y(jié)構(gòu)的情況下會(huì)出現(xiàn)AB和CD兩段曲線自交，如圖5（b）這就是自交產(chǎn)生的原因。自交現(xiàn)象的出現(xiàn)會(huì)增加中間分支點(diǎn)位置的不確定性。對(duì)于這種情況，通常的處理情況是在偏置后對(duì)所有線段進(jìn)行自交檢測，但會(huì)隨著多邊形變數(shù)的增多，算法的執(zhí)行效率會(huì)降低。針對(duì)這種情況，在凸多邊形偏置算法的基礎(chǔ)上，本文通過整合臨界偏置處理，如圖5（c），提出了一種基于非凸多邊形最小厚度的角平分線偏置算法，其核心在于找到偏置處理的臨界點(diǎn)。

非凸多變形偏置算法描述如下：

步驟1：尋找非凸多邊形的最小厚度。

（1） 按凸多邊形偏置算法的步驟1計(jì)算出兩頂點(diǎn)間線段與兩頂點(diǎn)法向量所構(gòu)成的三角形的高。但不同的地方在非凸多邊形上計(jì)算出來三角形的高是帶正負(fù)方向的，因此，這里規(guī)定只有正向的三角形高才是有效數(shù)值。

（2） 多邊形凹凸判斷算法找出非凸多邊形輪廓線上的凹頂點(diǎn)，并計(jì)算凹頂點(diǎn)的角平分線正方向（從頂點(diǎn)交出發(fā)指向多邊形內(nèi)部方向）與距離最近的輪廓邊界線段的交點(diǎn)。具體方法如下：

尋找跟凹頂點(diǎn)的角平分線正方向相交的輪廓邊界線段。假設(shè)角平分線與輪廓邊界線段相交，輪廓邊界線為直線線段，輪廓線段的兩端點(diǎn)必在角平分線的兩側(cè)。圖6所示為角平分線與輪廓邊界線段相交的判斷，BQ為多邊形凹頂點(diǎn)角CBA的正向角平分線，與輪廓邊界線段EF交于P點(diǎn)，端點(diǎn)E和F分別位于BQ左側(cè)和右側(cè)。然后引入相交判斷系數(shù)，并進(jìn)行計(jì)算：

為E到BQ的有向距離，

為F到BQ的有向距離，

為的單位向量

為的單位向量

為相交判斷系數(shù)。當(dāng)?shù)扔?時(shí)，角平分線與輪廓邊界線段相交。

求出交點(diǎn)P的位置。借助有向距離的模及邊界線段端點(diǎn)坐標(biāo)，可以快速計(jì)算出交點(diǎn)坐標(biāo)。計(jì)算方式如下：

為角平分線與輪廓線段的交點(diǎn)坐標(biāo)

為角平分線與輪廓線段的交點(diǎn)坐標(biāo)

計(jì)算所有與同一凹頂點(diǎn)的角平分線相交邊界線段的距離，找出最短距離，確定最近的邊界線段。

計(jì)算凹頂點(diǎn)所在角平分線與相交邊界線段等高的交點(diǎn)，如圖7。計(jì)算方法如下：

比較所有凹頂點(diǎn)角平分線及最近輪廓邊界線的等高距離，尋找最小值，

和分別為第個(gè)凹頂點(diǎn)角平分線及最近輪廓邊界線的等高距離及最后一個(gè)凹頂點(diǎn)角平分線及最近輪廓邊界線的等高距離。

（3） 比較凹頂點(diǎn)等高距離及輪廓邊界線對(duì)應(yīng)三角形的高，尋找最小值作為非凸多邊形的最小厚度.

步驟2：尋找第一個(gè)無自交的非凸多邊形環(huán)。

（1） 利用式（4）計(jì)算非凸多邊形實(shí)體方向的每個(gè)頂點(diǎn)角平分線上的截點(diǎn)計(jì)算。

（2） 按凸多邊形頂點(diǎn)的拓?fù)潢P(guān)系對(duì)截點(diǎn)進(jìn)行連接，構(gòu)成了新的多邊形。非凸多邊形在這里會(huì)出現(xiàn)兩種情況，第一種情況，輪廓邊界線對(duì)應(yīng)三角形的高為最小值，最小厚度所在三角形對(duì)應(yīng)的凸多邊形輪廓線段會(huì)退化成一點(diǎn)，新的多邊形只有一個(gè)且邊數(shù)為N-1，與凸多邊形偏置的情況一樣。

第二種情況，凹頂點(diǎn)等高距離為最小值，凹頂點(diǎn)角平分線正方向上與最近輪廓邊界線段的偏置線段會(huì)出現(xiàn)分支交點(diǎn)（圖8），此時(shí)，新的多邊形會(huì)出現(xiàn)兩個(gè)或以上的多邊形。由于分支交點(diǎn)P5既屬于角平分線V5P5上的點(diǎn)，又屬于輪廓線段V1V7的偏置線段P1P7上的點(diǎn)，但實(shí)際上偏置線段P1P7上并無P5這點(diǎn)，需要通過插值的方式將P5放到P1P7上以保持多邊形邊界的合法性。分支交點(diǎn)也是非凸多邊形中的中間分支點(diǎn)。

步驟3：找出所有中間分支點(diǎn)。對(duì)于分割出來的新多邊形，則對(duì)其的多邊形凹凸性進(jìn)行判斷，然后按照其屬于凸多邊形或非凸多邊形的偏置算法進(jìn)行處理。如果新生成的多邊形是凸多邊形，則按凸多邊形偏置方法找出所有無自交的凸多邊形環(huán)以及所有的中間分支點(diǎn)，直到多邊形上所有頂點(diǎn)退化到一點(diǎn)，如果新生成的多邊形是非凸多邊形，則按步驟1和2 進(jìn)行操作，找出所有無自交的非凸多邊形環(huán)以及所有的中間分支點(diǎn)。偏置操作直至該非凸多邊形中內(nèi)再無多邊形環(huán)可提取。

3.4中軸重構(gòu)算法

中軸重構(gòu)算法可分為對(duì)兩類：凸多邊形中軸重構(gòu)算法及非凸多邊形中軸重構(gòu)算法。而重構(gòu)算法的關(guān)鍵在于保持中軸拓?fù)浣Y(jié)構(gòu)的連續(xù)性。本文提出一種“手?jǐn)D（Hand Squeeze/HS）”式中軸重構(gòu)算法，利用輪廓邊界拓?fù)浣Y(jié)構(gòu)的連續(xù)性來保持凸多邊形及非凸多邊形中軸的連續(xù)性。

3.4.1 凸多邊形中軸重構(gòu)算法

凸多邊形中軸重構(gòu)算法如圖9， 假設(shè)用手握著凸多邊形，然后均勻用力握住凸多邊形。由于手形的生理特征，多邊形較長的方向會(huì)與四指彎卷方向呈銳角方向。另外假設(shè)凸多邊形的硬度為零，輪廓邊線可以隨意向垂直方向擠壓，并在擠壓過程中，輪廓邊線允許軸向收縮?；谶@兩點(diǎn)假設(shè)，凸多邊形可以向內(nèi)部收縮直到輪廓邊線間沒有收縮“空間”，這樣就成為該凸多邊形的中軸。但此時(shí)，輪廓邊線間還是連續(xù)的。通過這種算法，可以快速得到連續(xù)中軸。而這種算法的定義為：

定義1：在頂點(diǎn)偏置過程中保持每個(gè)頂點(diǎn)間的拓?fù)潢P(guān)系，不作任何添加和修改。

定義2：在到達(dá)最小偏置距離及出現(xiàn)中間分支點(diǎn)時(shí)，允許出現(xiàn)重合點(diǎn)，但仍舊保持輪廓的拓?fù)溥B續(xù)關(guān)系。

定義3：從中間分支點(diǎn)繼續(xù)偏置時(shí)，假設(shè)在“手?jǐn)D”過程中，物體已經(jīng)到達(dá)“背靠背”的狀態(tài)其無法繼續(xù)擠壓，從而形成一條直線段。此時(shí)，分支點(diǎn)不再移動(dòng)，其他點(diǎn)仍然向線段的垂直方向“擠壓”。這種情況下，需要在重合點(diǎn)間插入中間分支點(diǎn)并固定，其它點(diǎn)仍沿著頂點(diǎn)的角平分線正方向移動(dòng)，如圖10。

定義4：繼續(xù)擠壓直到所有輪廓邊界線段間沒有“空間”，得到中軸，如圖11。

3.4.2 非凸多邊形中軸重構(gòu)算法

非凸多邊形中軸重構(gòu)算法如圖12，與凸多邊形的“手?jǐn)D”中軸重構(gòu)算法類似。但不同的是凸多邊形是單手“手?jǐn)D”壓縮，而非凸多邊形是多手在兩凹點(diǎn)間構(gòu)成的半凸多邊形進(jìn)行“手?jǐn)D”壓縮。非凸多邊形的“手?jǐn)D”壓縮過程的假設(shè)跟凸多邊形一樣，通過均勻施加壓力，擠去非凸多邊形上的冗余空間，得到非凸多邊形的中軸。非凸多邊形的“手?jǐn)D”壓縮中軸提取的定義如下：

定義1：在頂點(diǎn)偏置過程中保持每個(gè)頂點(diǎn)間的拓?fù)潢P(guān)系，不作任何添加和修改，同凸多邊形中軸重構(gòu)算法定義1。

定義2：在到達(dá)最小偏置距離及出現(xiàn)中間分支點(diǎn)時(shí)，允許出現(xiàn)重合點(diǎn)，但仍舊保持輪廓的拓?fù)溥B續(xù)關(guān)系，同凸多邊形中軸重構(gòu)算法定義2。

定義3：從中間分支點(diǎn)繼續(xù)偏置時(shí)，到達(dá)“背靠背”的狀態(tài)，且形成一條直線段。此時(shí)，分支點(diǎn)不再移動(dòng)，其他點(diǎn)仍然向線段的垂直方向“擠壓”。這種情況下，需要分兩種情況。第一種情況，如果是凸頂點(diǎn)形成的中間分支點(diǎn)，處理方式同凸多邊形中軸重構(gòu)算法步驟3，即在重合點(diǎn)間插入中間分支點(diǎn)并固定，其它點(diǎn)仍沿著頂點(diǎn)的角平分線移動(dòng)。第二種情況，如果是凹頂點(diǎn)形成的中間分支點(diǎn)，除了將中間分支點(diǎn)固定以外，還需要插入額外控制點(diǎn)，并沿著先出現(xiàn)的角平分線正方向移動(dòng)（圖13）。

定義4：繼續(xù)擠壓直到所有輪廓邊界線段間沒有“空間”，得到中軸，如凸多邊形中軸重構(gòu)算法定義4。

4. 實(shí)驗(yàn)驗(yàn)證

對(duì)于上述理論，需要通過實(shí)驗(yàn)進(jìn)行驗(yàn)證，以下將分別對(duì)凸多邊形和非凸多邊形進(jìn)行實(shí)驗(yàn)。

4.1 凸多邊形

為確保凸多邊形偏置算法的有效性，實(shí)驗(yàn)樣本為隨機(jī)一個(gè)凸多邊形。在凸多邊形的實(shí)驗(yàn)樣本上，按逆時(shí)針順序作各頂點(diǎn)的角平分線，計(jì)算出第一個(gè)無自交的凸多邊形環(huán)的最小偏置距離，利用式（4）求出的中間分支點(diǎn)及第一個(gè)無自交凸多邊形環(huán)上的控制點(diǎn)，連接成新的凸多邊形（圖14）。然后按3.2凸多邊形偏置算法的步驟3按計(jì)算得出的各最小偏置距離進(jìn)行偏置，直至所有凸多邊形頂點(diǎn)退化到一點(diǎn)。最后中軸提取方法提取凸多邊形的中軸（圖15）。

4.2 非凸多邊形

同樣，為確保非凸多邊形偏置算法的有效性，實(shí)驗(yàn)樣本為隨機(jī)一個(gè)非凸多邊形。在非凸多邊形的實(shí)驗(yàn)樣本上，按逆時(shí)針順序作各頂點(diǎn)的角平分線，計(jì)算出第一個(gè)無自交的非凸多邊形環(huán)的最小偏置距離，利用式（4）求出的中間分支點(diǎn)及第一個(gè)無自交非凸多邊形環(huán)上的控制點(diǎn)，連接成新的非凸多邊形（圖16）。然后按3.3凸多邊形偏置算法的步驟對(duì)所有無自交凸多邊形環(huán)進(jìn)行偏置操作直至無法再提取多邊形環(huán)為止。最后中軸提取方法提取凸多邊形的中軸（圖17）。

5.結(jié)果分析

從凸多邊形和非凸多邊形的偏置處理及中軸提取實(shí)驗(yàn)結(jié)果來看，基于角平分線的無孔復(fù)雜多邊形中軸提取算法可以基本滿足多邊形的偏置及中軸提取的目的，同時(shí)可以減少自交檢測的復(fù)雜度。

6.結(jié)論

本文在現(xiàn)有草火模型及最大圓盤模型的基礎(chǔ)上，提出了一種基于角平分線的無孔復(fù)雜多邊形中軸提取算法。該算法利用多邊形凹凸點(diǎn)的偏置處理來獲得中間分支點(diǎn)，然后利用“手?jǐn)D”邊界的方式獲得中軸，并利用邊界的連續(xù)拓?fù)浣Y(jié)構(gòu)保持中軸的連續(xù)性。實(shí)驗(yàn)結(jié)果表明該算法能滿足中軸提取的要求并能保持中軸的連續(xù)性，而且減少了自交檢測的復(fù)雜程度。但目前該算法局限于無孔的復(fù)雜多邊形結(jié)構(gòu)，尚未進(jìn)行有孔多邊形驗(yàn)證。下一步將進(jìn)行有孔多邊形驗(yàn)證及編寫程序驗(yàn)證。

參考文獻(xiàn)

[1] 黎茂. 中軸變換研究[D]. 電子科技大學(xué)， 2006

[2] 徐春. 一種基于手的力反饋虛擬現(xiàn)實(shí)系統(tǒng)的研究[J]. 畢業(yè)生， 2003.

[3] 巴文蘭， 曹利新. 基于中軸變換的刀具優(yōu)化選擇與刀具路徑規(guī)劃[J]. 大連理工大學(xué)學(xué)報(bào)， 2013（01）：63-68.

[4] Smogavec G， Zalik B. A fast algorithm for constructing approximate medial axis of polygons， using Steiner points [J]. Advances in Engineering Software， 2012， 52：p.1-9.

[5] Blum，H. A transformation for extracting new descriptors of shape [J]. Models for the Preception of Speech & Visual Form， 1967， 19：362-380.

[6] 呂哲， 王福利， 常玉清， et al. 改進(jìn)的形態(tài)學(xué)骨架提取算法 [J]. 計(jì)算機(jī)工程， 2009， 035（019）：23-25.

[7] Arcelli， Carlo & Sanniti di Baja， Gabriella. （1985）. A Width- Independent Fast Thinning Algorithm. Pattern Analysis and Machine Intelligence， IEEE Transactions on.4. 463-474.

[8] 徐超， 肖瀟， 駱燕， 等. 基于距離變換的新型骨架提取方法 [J]. 儀器儀表學(xué)報(bào)， 2012（12）：213-218.

[9] Dey T K， Zhao W. Approximate medial axis as a Voronoi subcomplex[J]. Computer Aided Design， 2004， 36（2）：195-202.

[10] Yong， L.K. （2009）. 3D medial axis approximation through Delaunay triangulation. Journal of Science and Technology in the Tropics. 5. 133-139.

[11] 潘鵬， 賀三維， 吳艷蘭， 等. 曲邊多邊形中軸提取的新方法 [J]. 測繪學(xué)報(bào)， 2012， 041（002）：278-283，290.

[12] 王新生， 謝凱， 姜友華， 等. 復(fù)雜多邊形中軸構(gòu)建方法 [J]. 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2014，39：2， 2014， 39（2）：181-185.

[13] Liu L ， Chambers E W ， Letscher D ， et al. Extended grassfire transform on medial axes of 2D shapes[J]. Computer Aided Design， 2011， 43（11）：1496-1505.

[14] SONG Xiaomei， CHENG Changxiu， ZHOU Chenghu. An Analysis and Investigation of Algorithms for Identifying Convexity-Concavity of a Simple Polygon [J]. Remote Sensing for Land & Resources， 2011， 19（3）：25-31.

[15] 林福嚴(yán)， 鄭奇志， 胡于進(jìn)， 周濟(jì). 平面形體的中線提取及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件 2000