王楚奇(香港城市大學(xué)，香港　999077)Method for Calculating Minimum Enclosing Rectangle of Polygons with Arc EdgeWANG Chuqi

一種計(jì)算帶有圓弧曲邊多邊形最小封裝矩形的方法

王楚奇(香港城市大學(xué)，香港999077)Method for Calculating Minimum Enclosing Rectangle of Polygons with Arc EdgeWANG Chuqi

摘要在大型鐵路或公路鋼桁架橋梁中，其桿件和節(jié)點(diǎn)主要由不同形狀和尺寸的平面鋼板采用焊接或高強(qiáng)螺栓等方式拼接而成。在完成橋梁的BIM三維模型后，工程師需要計(jì)算鋼板的最小外包尺寸以形成BOM表。常用的三維建模軟件如Solidworks本身不具備這樣的功能，需要進(jìn)行二次開發(fā)。針對(duì)該需求，提出一種用于計(jì)算帶有曲邊(曲邊為圓弧)的多邊形(下略稱曲邊多邊形)的最小封裝矩形的方法。由于輸入數(shù)據(jù)具有規(guī)則性，該方法將輸入的曲邊以一定規(guī)則離散化，化為離散點(diǎn)集后以快包法(Akl-Toussaint啟發(fā)式)或格雷厄姆法與旋轉(zhuǎn)卡殼算法求得最小封裝矩形的4個(gè)頂點(diǎn)坐標(biāo)，隨后求得矩形的長(zhǎng)和寬。

關(guān)鍵詞鋼板零件二次開發(fā)弧邊多邊形離散化最小封裝矩形

1概述

在工程零件的設(shè)計(jì)中，經(jīng)常會(huì)遇到需要計(jì)算目標(biāo)零件的最小封裝矩形的問題。對(duì)散點(diǎn)集合以及直邊凸、凹多邊形的最小封裝矩形的計(jì)算，已經(jīng)有了成熟的算法[1]，其基本思想在于先求出圖形的最小凸殼，再根據(jù)該凸包求得最小面積的封裝矩形。然而，這些算法都沒有應(yīng)對(duì)帶有曲邊，尤其是外凸曲邊的多邊形方法[2]。若是不對(duì)圖形進(jìn)行處理，直接使用旋轉(zhuǎn)法進(jìn)行計(jì)算，則會(huì)陷入每次旋轉(zhuǎn)角度過大而不夠精確，或是每次旋轉(zhuǎn)角度過小從而導(dǎo)致計(jì)算時(shí)間大增的矛盾中[3]。再者，由于零件的正、反兩面形狀可能會(huì)有一定的區(qū)別，需要先對(duì)兩面的圖形進(jìn)行并集計(jì)算再求最小封裝矩形，這些算法同樣無法應(yīng)對(duì)這些情況。

通常情況下，零件的曲邊可視為圓弧，且其端點(diǎn)位置及拱高是比較容易獲得與控制的數(shù)據(jù)。針對(duì)以上問題，提出將曲邊以一定規(guī)則離散化后求并，再以傳統(tǒng)方法求得最小封裝矩形的方法。

2方法的提出與改進(jìn)

2.1　曲邊的預(yù)處理

要將圓弧曲邊離散化，首先要對(duì)曲邊進(jìn)行預(yù)處理，包括判斷圓弧的凹凸性，求圓弧半徑以及圓心坐標(biāo)。圓弧曲邊多邊形的每一條邊都包括3組數(shù)據(jù)：兩端點(diǎn)的直角坐標(biāo)以及拱高，而拱高即是判斷圓弧凹凸性的依據(jù)。輸入的值為正，表示圓弧向多邊形外部凸出，為負(fù)表示向多邊形內(nèi)部凹陷，為零則表示該邊為直線段。由于多邊形在離散為點(diǎn)集后還要進(jìn)行凸殼計(jì)算，故可將向內(nèi)凹陷的曲邊作為直線段來處理。假設(shè)兩端點(diǎn)的坐標(biāo)分別為A(xa，ya)與B(xb，yb)拱高為h，半徑為r，弦長(zhǎng)為l，有

(1)

以及

(2)

由式(2)易得

(3)

因?yàn)橛墒?1)很難求得圓心坐標(biāo)，即使解出方程組也會(huì)產(chǎn)生大量的除法和根式運(yùn)算，所以改用向量法。由A、B點(diǎn)坐標(biāo)可以求出線段AB的法向量

(4)

單位化后得到單位法向量

(5)

由弦心距

(6)

及弦的中點(diǎn)坐標(biāo)

擁有自信，能讓自身的智慧的靈光得以閃亮，創(chuàng)造出許多自己也意想不到的奇跡。小仲馬在自己艱難的創(chuàng)作中并沒有困為一時(shí)的挫折而放棄，而是憑借著自己的信心和才能去闖出了一番天地。巴魯瑪面臨唾手可得的成功放棄了，選擇了一條與大相徑庭的充滿挑戰(zhàn)的道路勇敢的走下去，是心燭點(diǎn)亮了她的錦繡人生；也是心燭使她驕傲地面對(duì)人生。

(7)

可得圓心P的兩個(gè)可能坐標(biāo)，滿足條件

(8)

2.2　圓心位置的判斷

無論是解方程組還是用以上方法計(jì)算，得出的圓心坐標(biāo)都有兩組，分別位于弦的兩側(cè)，且其中只有一個(gè)是這一段弧線的圓心，需要判斷坐標(biāo)的真?zhèn)巍Ｏ葘⑤斎脒叺臄?shù)據(jù)進(jìn)行一次梳理，使得點(diǎn)的輸入順序與邊的輸入順序保持一致(比如，兩條邊AB和BC，在輸入過程中可能會(huì)出現(xiàn)輸入BA和CB的情況，這里即是將其梳理為AB和BC)。之后需要判斷以輸入順序構(gòu)建多邊形的方向(順時(shí)針或逆時(shí)針)與該段弧線圓心P-點(diǎn)A-點(diǎn)B的旋轉(zhuǎn)方向以及h與r的大小關(guān)系。由于向量AB與向量vun滿足逆時(shí)針關(guān)系，即2D平面上AB×vun>0，當(dāng)h

而當(dāng)h>r時(shí)，若多邊形方向與PAB同向則說明圓心P位置錯(cuò)誤，若反向，則圓心位置正確(如圖2)。

2.3　圓弧曲邊的離散化

計(jì)算圓弧上的離散點(diǎn)需要圓弧的圓心角，根據(jù)上文易知，可根據(jù)h與r的大小關(guān)系來判斷弧線是優(yōu)弧還是劣弧，然后由余弦定理求得圓心角。利用起點(diǎn)角度和終點(diǎn)角度計(jì)算圓弧曲邊的離散點(diǎn)坐標(biāo)會(huì)產(chǎn)生大量的除法和反三角函數(shù)運(yùn)算，從而導(dǎo)致計(jì)算效率低。所以本文使用旋轉(zhuǎn)法依次計(jì)算出每個(gè)離散點(diǎn)的位置。假設(shè)計(jì)算得出的圓心角為θ，具體計(jì)算如下：

(9)

計(jì)算得出第一個(gè)離散點(diǎn)D1(此處假設(shè)多邊形方向?yàn)槟鏁r(shí)針，若為順時(shí)針則將α替換為-α)

(10)

(11)

對(duì)正整數(shù)i取值2到n，有

(12)

旋轉(zhuǎn)終點(diǎn)Dn即是點(diǎn)B。

2.4　誤差控制

由雙精度浮點(diǎn)數(shù)表達(dá)的直線邊多邊形的最小封裝矩形的計(jì)算，誤差通?？梢员３衷?0-16個(gè)最大單位以下。對(duì)于曲邊多邊形，由于要將曲邊離散為折線邊，會(huì)產(chǎn)生一定的誤差，需要將該誤差控制在加工精度范圍內(nèi)。

如：若每次旋轉(zhuǎn)角度為α，該角度對(duì)應(yīng)圓弧段的拱高為h，則有

(13)

且

(14)

解得

(15)

拱高h(yuǎn)即是產(chǎn)生較大誤差的原因所在。為限制誤差的大小，只能增大離散點(diǎn)的密集程度，通過限制α來達(dá)到限制誤差的目的，有

(16)

2.5　封裝矩形計(jì)算

由上文的方法可以得到某曲邊多邊形的離散點(diǎn)集，而每個(gè)零件都存在有些微區(qū)別的正反兩面，故本文方法的最后一步就是將兩面求得的點(diǎn)集求并，然后以快包法(Akl-Toussaint啟發(fā)式)求得點(diǎn)集的最小凸殼，再用旋轉(zhuǎn)卡殼法求得凸殼的最小封裝矩形，由此獲得完整零件的最小封裝矩形。

3實(shí)驗(yàn)結(jié)果及結(jié)論

在VS 2013，CGAL4.6.1，Boost 1.58.0環(huán)境下實(shí)現(xiàn)本文提出的最小封裝矩形的計(jì)算方法。為了驗(yàn)證該方法的有效性和高效性，用sketchpad 5.0軟件進(jìn)行精密繪圖測(cè)試。運(yùn)行環(huán)境為Intel? CoreTMi7-3630QM 2.40 GHz處理器，8GB內(nèi)存，64位Windows8.1操作系統(tǒng)

3.1　有效性

如圖3(極限情況)，將邊的端點(diǎn)以及拱高精確控制并輸入后，畫出對(duì)應(yīng)圖形。將數(shù)據(jù)輸入程序進(jìn)行計(jì)算，將封裝矩形4個(gè)頂點(diǎn)坐標(biāo)的計(jì)算結(jié)果輸入畫板(左上角)。確定圓弧圓心后，從圓心向可能相切的矩形邊做垂線與圓弧交于點(diǎn)Ei，隨后測(cè)量該點(diǎn)到對(duì)應(yīng)矩形邊的距離(右下角)。此距離應(yīng)小于輸入數(shù)據(jù)中的最大誤差限制(圖3(a)的誤差限制為0.000 01 cm，圖3(b)的誤差限制為0.001 cm，定義坐標(biāo)系的單位長(zhǎng)度是1 cm)，由此可見本文算法正確有效。

3.2　算法效率

根據(jù)軟件使用者的體驗(yàn)，在一般情況下，對(duì)于零件的數(shù)學(xué)計(jì)算處理要求是200個(gè)左右的零件需要在5 s內(nèi)處理完成，即1 000個(gè)零件的處理時(shí)間需要控制在25 s以內(nèi)。表1給出了各個(gè)精度要求下的如圖3和圖4所示的1 000個(gè)零件的計(jì)算時(shí)間總和。從表1可以看出，本文的計(jì)算方法時(shí)間性能完全符合要求。

4結(jié)論

提出一種計(jì)算零件的最小封裝矩形的方法，充分利用已有算法的特性，將帶有曲邊的多邊形離散為散點(diǎn)集后進(jìn)行計(jì)算。該方法能對(duì)任意零件的正反兩面進(jìn)行并集計(jì)算，從而獲取零件最小封裝矩形的規(guī)格，并且具有令人滿意的精確度和效率。

參考文獻(xiàn)

[1]郭慶勝，馮代鵬，劉遠(yuǎn)剛，等.一種解算空間幾何對(duì)象的最小外接矩形算法[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2014，39(2):177-180

[2]薛迎春，須文波，孫俊.基于遺傳模擬退火混合算法的矩形包絡(luò)求解[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(22):5457-5460.

[3]盧蓉，范勇，陳念年，等.一種提取目標(biāo)圖像最小外接矩形的快速算法[J].計(jì)算機(jī)工程，2010，36(21):178-180.

中圖分類號(hào)：U442； TB21

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-7479(2015)06-0082-03

作者簡(jiǎn)介：王楚奇(1993—)，男，香港城市大學(xué)科學(xué)及工程學(xué)院電子工程系信息工程專業(yè)。

收稿日期：2015-11-12