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

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

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

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

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

關鍵詞鋼板零件二次開發弧邊多邊形離散化最小封裝矩形

1概述

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

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

2方法的提出與改進

2.1　曲邊的預處理

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

(1)

以及

(2)

由式(2)易得

(3)

因為由式(1)很難求得圓心坐標，即使解出方程組也會產生大量的除法和根式運算，所以改用向量法。由A、B點坐標可以求出線段AB的法向量

(4)

單位化后得到單位法向量

(5)

由弦心距

(6)

及弦的中點坐標

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

(7)

可得圓心P的兩個可能坐標，滿足條件

(8)

2.2　圓心位置的判斷

無論是解方程組還是用以上方法計算，得出的圓心坐標都有兩組，分別位于弦的兩側，且其中只有一個是這一段弧線的圓心，需要判斷坐標的真偽。先將輸入邊的數據進行一次梳理，使得點的輸入順序與邊的輸入順序保持一致(比如，兩條邊AB和BC，在輸入過程中可能會出現輸入BA和CB的情況，這里即是將其梳理為AB和BC)。之后需要判斷以輸入順序構建多邊形的方向(順時針或逆時針)與該段弧線圓心P-點A-點B的旋轉方向以及h與r的大小關系。由于向量AB與向量vun滿足逆時針關系，即2D平面上AB×vun>0，當h

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

2.3　圓弧曲邊的離散化

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

(9)

計算得出第一個離散點D1(此處假設多邊形方向為逆時針，若為順時針則將α替換為-α)

(10)

(11)

對正整數i取值2到n，有

(12)

旋轉終點Dn即是點B。

2.4　誤差控制

由雙精度浮點數表達的直線邊多邊形的最小封裝矩形的計算，誤差通?？梢员３衷?0-16個最大單位以下。對于曲邊多邊形，由于要將曲邊離散為折線邊，會產生一定的誤差，需要將該誤差控制在加工精度范圍內。

如：若每次旋轉角度為α，該角度對應圓弧段的拱高為h，則有

(13)

且

(14)

解得

(15)

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

(16)

2.5　封裝矩形計算

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

3實驗結果及結論

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

3.1　有效性

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

3.2　算法效率

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

4結論

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

參考文獻

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

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

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

中圖分類號：U442； TB21

文獻標識碼：A

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

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

收稿日期：2015-11-12