周 敏， 鄭國磊， 陳樹林

（1. 北京航空航天大學(xué)機(jī)械工程及自動化學(xué)院，北京 100191；2. 沈陽飛機(jī)工業(yè)（集團(tuán)）有限公司，遼寧 沈陽 110034）

二維圖形最狹長包絡(luò)矩形的求解原理及方法

周 敏1， 鄭國磊1， 陳樹林2

（1. 北京航空航天大學(xué)機(jī)械工程及自動化學(xué)院，北京 100191；2. 沈陽飛機(jī)工業(yè)（集團(tuán)）有限公司，遼寧 沈陽 110034）

最狹長包絡(luò)矩形是二維圖形的一個潛在幾何屬性，可作為平面外形智能設(shè)計(jì)、板料優(yōu)化排樣及圖像自動識別的重要依據(jù)。目前國內(nèi)外尚無此課題的專門深入研究。提出了最狹長包絡(luò)矩形的概念，將任意二維圖形的最狹長包絡(luò)矩形的求解轉(zhuǎn)化為對其凸包的最狹長包絡(luò)矩形的求解。明確給出了過凸包上給定4個頂點(diǎn)的包絡(luò)矩形的包絡(luò)角及長寬比求解公式，并通過分析包絡(luò)角及長寬比求解公式之間的關(guān)系，證明了凸多邊形至少存在一條邊與其最狹長包絡(luò)矩形的一條邊共線?；谠摱ɡ?，求解并比較與二維圖形的凸包的n條邊分別共線的n個包絡(luò)矩形的長寬比，得到了二維圖形的最狹長包絡(luò)矩形。最后用實(shí)例驗(yàn)證了定理和求解方法的正確性和應(yīng)用效率。

計(jì)算幾何；最狹長包絡(luò)矩形；長寬比；飛機(jī)樣板設(shè)計(jì)

最狹長包絡(luò)矩形是二維圖形的一個潛在的固有幾何屬性，可作為平面外形智能設(shè)計(jì)、矩形優(yōu)化排樣及圖像自動識別的一個重要依據(jù)。例如，在飛機(jī)樣板智能化設(shè)計(jì)中，需要根據(jù)樣板工作邊曲線的形狀，自動優(yōu)化設(shè)計(jì)坐標(biāo)系。而優(yōu)化設(shè)計(jì)坐標(biāo)系的主要途徑是先找到曲線最狹長的方向，并以其作為坐標(biāo)系x軸的方向，這樣，可使樣板所用材料最少，最輕便。如圖1所示，粗實(shí)線為樣板工作邊，細(xì)實(shí)線為樣板非工作邊，非工作邊平行于設(shè)計(jì)坐標(biāo)系的坐標(biāo)軸，A為在當(dāng)前坐標(biāo)系下，曲線上具有最大y值的點(diǎn)到非工作邊的距離，A值固定；圖1(a)是在未經(jīng)優(yōu)化的設(shè)計(jì)坐標(biāo)系中設(shè)計(jì)的樣板，圖1(b)則是在優(yōu)化后的設(shè)計(jì)坐標(biāo)系中設(shè)計(jì)的樣板。圖1(a)中樣板的面積明顯大于圖1(b)中樣板的面積，因此，圖1(b)所示樣板用料更少，更輕便。那么，如何獲得曲線乃至任意二維圖形的最狹長方向？本文通過定義和計(jì)算二維圖形的最狹長包絡(luò)矩形，即可確定二維圖形的最狹長方向。

圖1 不同設(shè)計(jì)坐標(biāo)系下設(shè)計(jì)的樣板

至今，大量研究主要圍繞求解凸多邊形、封閉區(qū)域圖形的面積最小的包絡(luò)矩形展開。Freeman和Shapira[1]證明了凸多邊形的最小包絡(luò)矩形必有一條邊與凸多邊形的一條邊共線。Toussaint[2]用 Shamos[3]于 1978年在其博士論文中提出的“rotating calipers”，即旋轉(zhuǎn)卡鉗法求凸多邊形的最小包絡(luò)矩形，并將計(jì)算時間從 O(n2)縮短到O(n)（n為凸多邊形的頂點(diǎn)個數(shù)）。Alt和Hurtaddo[4]保持凸多邊形的一個頂點(diǎn)以及包絡(luò)矩形的左下角點(diǎn)與坐標(biāo)系原點(diǎn)重合，矩形兩條邊分別與x軸和y軸共線，旋轉(zhuǎn)凸多邊形，得到的包絡(luò)矩形集的右上角點(diǎn)的軌跡，為一條由橢圓弧構(gòu)成的、并以y=x為對稱軸的封閉曲線；在某段橢圓弧的一個端點(diǎn)處，矩形具有最小面積或周長。Chaudhuri和Samal[5]用封閉區(qū)域邊界點(diǎn)的形心作為最小包絡(luò)矩形的形心，以所有邊界點(diǎn)到矩形中心線的垂直距離之和最小作為條件來確定矩形的主軸和副軸的方向，從而求得最小包絡(luò)矩形。但作者并未證明用上述方法得到的矩形就是封閉區(qū)域的最小包絡(luò)矩形。黃宜軍等[6]在對鈑金進(jìn)行排料時采用窮舉法求解鈑金零件的最小面積包絡(luò)矩形。這種方法原理簡單，但計(jì)算量大且只能獲得近似值。為了提高計(jì)算效率，薛迎春等[7]利用遺傳模擬退火混合算法對凸多邊形的最小包絡(luò)矩形進(jìn)行了求解，該算法收斂速度較低且求解結(jié)果也只是近似值。

必須指出，面積最小的包絡(luò)矩形并不一定是最狹長包絡(luò)矩形。關(guān)于如何計(jì)算凸多邊形、開曲線甚至任意二維圖形的最狹長包絡(luò)矩形，目前尚未見到國內(nèi)外相關(guān)研究和介紹?；谥悄芑O(shè)計(jì)的需求以及作為對包絡(luò)矩形研究的補(bǔ)充，本文提出并進(jìn)行了二維圖形的最狹長包絡(luò)矩形求解原理與方法的研究。首先，將二維圖形最狹長包絡(luò)矩形的求解轉(zhuǎn)化為對其凸包最狹長包絡(luò)矩形的求解，使問題得以簡化；繼而，通過對經(jīng)過凸包上給定4個頂點(diǎn)的包絡(luò)矩形的包絡(luò)角及長寬比的求解，以及對包絡(luò)角及長寬比求解公式之間關(guān)系的分析，證明了凸多邊形的最狹長包絡(luò)矩形至少存在一條邊與凸多邊形的一條邊共線；最后，基于已證明的定理，給出了二維圖形的最狹長包絡(luò)矩形的求解算法，并結(jié)合實(shí)例對算法進(jìn)行了分析和驗(yàn)證。

1 最狹長包絡(luò)矩形及其性質(zhì)

1.1 包絡(luò)角

在平面空間OXY中，G為一個二維圖形，S為其離散點(diǎn)集，P為S的凸包，亦即凸多邊形，R為P的任一包絡(luò)矩形，同時也是G的包絡(luò)矩形，如圖2所示。P共有n個頂點(diǎn)，逆時針依次為v1, v2,…, vn，R的四條邊依次為e1, e2, e3和e4，即有e1// e3和e2//e4，并規(guī)定分別過P上相對位置為左、下、右和上的4個頂點(diǎn)vl，vd，vr和vu，其中1≤l、d、r、u、≤n。此外，文中規(guī)定邊與X軸正向間的夾角是指 X軸正向逆時針旋轉(zhuǎn)至與邊或邊的延長線重合時所經(jīng)過的角度，其取值范圍為[0°, 180°]。圖2中ω即為R中邊e1與X軸正向間的夾角。這樣，可給出如下定義：

圖2 二維圖形的包絡(luò)矩形

定義1 若順時針（或逆時針）轉(zhuǎn)動R，并使其各邊始終過vl、vd、vr和vu四個頂點(diǎn)，且保證R為P的包絡(luò)矩形，則稱此轉(zhuǎn)動過程為R的順時針（或逆時針）包絡(luò)轉(zhuǎn)動，簡稱包絡(luò)轉(zhuǎn)動。R順時針包絡(luò)轉(zhuǎn)動的極限位置稱為R的包絡(luò)始位，而逆時針包絡(luò)轉(zhuǎn)動的極限位置稱為R的包絡(luò)終位。

定義2 設(shè)ω為R中邊e1與X軸正向間的夾角，且規(guī)定其取值范圍為[0°, 180°]，則稱ω為R的包絡(luò)位角。

定義 3 當(dāng) R順時針包絡(luò)轉(zhuǎn)動到極限位置時，稱R的包絡(luò)位角為R的包絡(luò)始角，用ω1表示。而當(dāng)R逆時針包絡(luò)轉(zhuǎn)動到極限位置時，稱R的包絡(luò)位角為 R的包絡(luò)終角，用 ω2表示。令ωb=ω2-ω1，則稱ωb為R的包絡(luò)角。

易知，0°≤ωb≤180°，ω1≤ω≤ω2。如圖 3所示，其中R1和R2分別為凸多邊形P的任一個包絡(luò)矩形 R順時針和逆時針包絡(luò)轉(zhuǎn)動的極限位置，R為任一滿足條件的包絡(luò)矩形。

圖3 包絡(luò)角示意圖

為求包絡(luò)始角與包絡(luò)終角，引入定義4。

定義4 設(shè)vp和vq為P上頂點(diǎn)vl的前后兩個相鄰頂點(diǎn)，vs和vt為vr的前后兩個相鄰頂點(diǎn)，如圖4所示。設(shè)邊與X軸夾角為與X軸夾角為同理設(shè)邊與X軸夾角為與X軸夾角為若不等式

或

圖4 包絡(luò)矩形的有效轉(zhuǎn)動角

引理1 在平面空間OXY中，G為一個二維圖形，S為其離散點(diǎn)集，P為S的凸包，R為P的任一包絡(luò)矩形，則R的包絡(luò)始角ω1和包絡(luò)終角ω2分別為：

或

證明：由于 e1⊥ e2，因此， e2, e4逆時針旋轉(zhuǎn)后應(yīng)與 e1, e3平行。所以，應(yīng)與有重合部分，其重合部分即為 ωb。故當(dāng)不等式：

或

成立時，經(jīng)過點(diǎn) vl, vd, vr, vu，保持 e1//e3，e2//e4，e1⊥ e2且將P包絡(luò)在內(nèi)的矩形存在。重合部分的邊界即為R的包絡(luò)始角 ω1和包絡(luò)終角 ω2：

或

引理1得證。

引理 2 若R的包絡(luò)位角為 ω1或 ω2，則 R某一條邊與P的某一條邊共線。

1.2 最狹長包絡(luò)矩形

R為一矩形，令b和a為R的長和寬，即a≤b，稱b與a之比值為R的長寬比。下文中，將長寬比的倒數(shù)用f表示，即

引理3 在G的所有包絡(luò)矩形中，一定存在長寬比最大的包絡(luò)矩形。

證明：設(shè)P為G的凸包， R1, R2,… ,Rm為過P上各不相同的4個頂點(diǎn)的m個包絡(luò)矩形。其中，m為P上所有可能構(gòu)成包絡(luò)矩形的4個頂點(diǎn)的組合的個數(shù)，每一個 Ri( i = 1,2,… ,m)均可在其包絡(luò)角范圍內(nèi)進(jìn)行包絡(luò)轉(zhuǎn)動產(chǎn)生一系列過P上相同4個頂點(diǎn)的包絡(luò)矩形，則 R1, R2,… ,Rm可表示P的所有包絡(luò)矩形。 Ri在其包絡(luò)轉(zhuǎn)動過程中，長和寬在有限的轉(zhuǎn)動范圍內(nèi)發(fā)生連續(xù)變化，根據(jù)實(shí)數(shù)的基本性質(zhì)，連續(xù)函數(shù)在閉區(qū)間上必取到最大最小值， Ri必然在某個包絡(luò)位角取得最小 fi，令其為因此，在有限的m個可數(shù)且可比較的中，及其所對應(yīng)的包絡(luò)矩形一定存在，亦即引理得證。

由引理3，給出如下定義和定理：

定義5 給定一個二維圖形G，R為其一個包絡(luò)矩形，若在G的所有包絡(luò)矩形中，R的長寬比最大，則稱R為G的最狹長包絡(luò)矩形，表示為 ξ( G)。

定理1 設(shè)R為凸多邊形P的最狹長包絡(luò)矩形，則R一定存在一條邊與P的某一條邊共線。

證明：任意給定一個凸多邊形P，如圖5所示，P和 R分別由粗實(shí)線和細(xì)實(shí)線表示，線段且交線段于點(diǎn) A，線段且交線段于點(diǎn)B，線段且交線段于點(diǎn)C，線段且交線段于點(diǎn)D，線段且交邊 e3于點(diǎn) E。令，，則矩形的長b、寬a分別為：

進(jìn)而可得R的長寬比f為：

圖 5 過凸包上四頂點(diǎn) vl、vd、vr和 vu的包絡(luò)矩形

為單調(diào)遞增的有界連續(xù)函數(shù)。

如圖6所示，當(dāng)4個頂點(diǎn)給定時，γ不隨矩形包絡(luò)轉(zhuǎn)動而改變。由于 θ = ω+ γ- 180°（圖6(a)）或θ =-ω- γ+ 180°（圖6(b)），故θ與ω線性相關(guān)。當(dāng)ω取得極限值時，θ亦取得極限值。所以當(dāng)θ在 [θ1, θ2]范圍內(nèi)變化時，f一定在某一個θ處取得唯一一個最小值，即當(dāng)包絡(luò)位角ω在[ω1, ω2]范圍內(nèi)變化時，存在唯一一個過P上給定四頂點(diǎn)且長寬比最大的包絡(luò)矩形。

圖6 θ與ω線性相關(guān)

圖5中，當(dāng)R逆時針包絡(luò)轉(zhuǎn)動時，θ角增大，f增大。當(dāng) ω = ω1時，θ = θ1最小，f最小。此時，可得到過 P上點(diǎn) vl、 vd、vr和 vu且長寬比最大的包絡(luò)矩形。當(dāng) ω = ω2時， θ = θ2，f最大，矩形長寬比最小。無論θ與ω正相關(guān)或負(fù)相關(guān)，f始終在 ω1或 ω2處取得最小值。

圖7 當(dāng)θ取得最大值時的包絡(luò)矩形

當(dāng) R逆時針包絡(luò)轉(zhuǎn)動至使 ω = ω2時，θ最大，f最小。圖 7所示為 ω = ω2時的情況。此時，矩形的一邊 e4與 P的一條邊重合，過 P上點(diǎn)vl、 vd、 vr和 vu的包絡(luò)矩形長寬比最大。相反，當(dāng)ω = ω1時，f最大，矩形長寬比最小。

表1 矩形逆時針轉(zhuǎn)動時f求解公式及其最小值

分析表1有：

2） 當(dāng)矩形在滿足ω1≤ω≤ω2條件的范圍內(nèi)轉(zhuǎn)動時，A, B, C, D的相對位置關(guān)系發(fā)生變化，如由B, A, D, C（①）變?yōu)锳, B, C, D（④），f的計(jì)算公式由（2）變?yōu)椋?），但f仍在ω1處取得最小值；當(dāng)A, B, C, D的相對位置關(guān)系繼續(xù)變化時，這個結(jié)論不變。即f在何處取得最小值由A, B, C, D的初始位置確定，所以，f總是在ω1或ω2處取得最小值或最大值，而包絡(luò)位角ω為ω1或ω2，矩形都有一條邊與凸包的某一條邊共線。由此，定理1得證。

由定理1的證明過程，同時可得出定理2：

定理2 凸多邊形的長寬比最小的包絡(luò)矩形一定存在一條邊與凸多邊形的某一條邊共線。

2 計(jì)算方法及其實(shí)現(xiàn)

2.1 計(jì)算方法

根據(jù)定理1，二維圖形G的 ()Gξ 的求解過程為：首先，將G離散為平面點(diǎn)集S；其次，用格雷厄姆方法[8]求解S的凸包即凸多邊形P；然后，求P的n個包絡(luò)矩形，并使每個包絡(luò)矩形分別過P的一條邊；最后，比較這n個矩形的f，f最小的包絡(luò)矩形即為所求。算法流程如圖8所示，其中：

Step 1 輸入任意二維圖形G。

Step 2 判斷G的類型，如果G完全由曲線或圓弧構(gòu)成，則按所需精度t進(jìn)行離散，得到平面點(diǎn)集S；如果G包含直線段，則提取直線段端點(diǎn)加入點(diǎn)集S。

Step 3 用格雷厄姆法求點(diǎn)集S的凸包，得到具有n個頂點(diǎn)vi(xi, yi)(i=1, 2,…, n)的凸多邊形P。

Step 5 對坐標(biāo)系XOY作平移和旋轉(zhuǎn)，使原點(diǎn)O與點(diǎn)vk重合，令新的原點(diǎn)為Ok，X軸的正向指向點(diǎn)得到坐標(biāo)系對P的所有頂點(diǎn)作如下坐標(biāo)變換：

其中：

得到vi(xi, yi)(i=1, 2,…, n)在坐標(biāo)系XOkY中的位置vi'(xi',yi')(i = 1,2,...,n)。

Step 6 求坐標(biāo)系XOkY中，具有最大x值、最小x值和最大y值的頂點(diǎn)，設(shè)它們分別為vr( xr',yr')、 vl( xl',yl')和 vu( xu',yu')，則 P( S)的包絡(luò)矩形的4個頂點(diǎn)坐標(biāo)分別為(xl',0)、(xl',yu')、(xr',yu')和(xr',0)，最小 f 即為：

Step 7 令k=k+1，重復(fù)步驟5和6直到k=n。當(dāng)k=n時，令k+1=1。比較n個矩形的n)，即可求出ξ(G)的 f 及其對應(yīng)的4個頂點(diǎn)。

該算法時間復(fù)雜度為O(n2)。其中，n個包絡(luò)矩形的求解可采用旋轉(zhuǎn)卡鉗法，則算法時間復(fù)雜度可降為O(n)。但本文所采用的坐標(biāo)變換法簡單易操作，且在滿足工程需求的前提下，兩種算法的計(jì)算時間并無差異。

2.2 實(shí)現(xiàn)及分析驗(yàn)證

為驗(yàn)證本文所提出方法的正確性，先后計(jì)算和測試了若干不同二維圖形的最狹長包絡(luò)矩形，其中包括4個具有代表性的圖形和兩個飛機(jī)壁板輪廓圖。利用上述方法，分別計(jì)算了這些圖形的凸包和ξ(G)，如圖9至14所示。與此同時，還運(yùn)用文獻(xiàn)[6]中所述窮舉法對上述實(shí)例計(jì)算ξ(G)及其對應(yīng)的最小f和面積。如文獻(xiàn)[6]所述，設(shè)矩形的對稱軸共旋轉(zhuǎn)90°，每旋轉(zhuǎn)Δθ作一個新的包絡(luò)矩形并求其f及面積。本文中分別取Δθ=1°和Δθ=1′進(jìn)行計(jì)算比較。實(shí)驗(yàn)結(jié)果如表2所示。

圖 11 開曲線

圖 12 任意圖形

圖13 飛機(jī)壁板輪廓1

圖14 飛機(jī)壁板輪廓2

表2 本文所述方法與窮舉法求ξ(G)極其f的對比 面積單位mm2

分析表2可知：

1） 當(dāng)Δθ=1°和Δθ=1′時，窮舉法求得的ξ(G)的最小f始終大于本文所提出方法求得的最小f。在忽略用二維圖形的離散點(diǎn)集近似表示二維圖形所產(chǎn)生的誤差的前提下，本文所提出方法是完全精確的；而在相同條件下，窮舉法只能獲得近似值。

2） 當(dāng)Δθ=1′時，窮舉法求得的最小f比Δθ=1°時求得的值更接近本文所提出方法求得的最小f，但Δθ=1′時需要計(jì)算5400次，每次需要求四個最值，即最大x值、最小x值、最大y值和最小y值；而本文只需計(jì)算n次（n為圖形凸包的邊數(shù)），每次只需計(jì)算 3個最值，而兩種方法每次計(jì)算每個值的時間是相等的。所以，當(dāng)滿足條件（Δθ單位為分）時，本文所提出方法始終比窮舉法快，工程實(shí)際需求滿足該條件。

3） 當(dāng)包絡(luò)矩形為最狹長包絡(luò)矩形時，矩形的面積非常接近凸包的最小包絡(luò)矩形的面積，甚至可能等于最小包絡(luò)矩形的面積，這說明凸包的最狹長包絡(luò)矩形與最小包絡(luò)矩形不總是一致的。

綜合上述對比分析，本文提出的求解方法是準(zhǔn)確和高效的。

3 結(jié) 論

本文首次提出了包絡(luò)角和最狹長包絡(luò)矩形等概念，探討了最狹長包絡(luò)矩形的內(nèi)在性質(zhì)，并在此基礎(chǔ)上給出了任意二維圖形的最狹長包絡(luò)矩形的求解方法。通過分析過凸包上給定四點(diǎn)的包絡(luò)矩形的包絡(luò)角與長寬比求解公式之間的關(guān)系，證明了凸多邊形的最狹長包絡(luò)矩形的某一條邊一定與凸多邊形的某一條邊共線?；谠摱ɡ?，構(gòu)建了任意二維圖形最狹長包絡(luò)矩形及其長寬比的求解方法，此方法的核心思想是將任意二維圖形最狹長包絡(luò)矩形的求解轉(zhuǎn)化為對其凸包的最狹長包絡(luò)矩形的求解，從而大大簡化了最狹長包絡(luò)矩形的計(jì)算過程。最后，選用了若干典型二維圖形作為實(shí)例，對本文所提方法進(jìn)行計(jì)算和測試，驗(yàn)證了該方法的正確性和有效性。對于最狹長包絡(luò)矩形的深層性質(zhì)，如最狹長包絡(luò)矩形個數(shù)的計(jì)算式等，還有待更進(jìn)一步的深入探究。此外，如何將二維圖形最狹長包絡(luò)矩形的探索思路拓展到三維形體，也是下一步的研究重點(diǎn)。

[1] Freeman H, Shapira R. Determining the minimum-area encasing rectangle for an arbitrary closed curve [J]. Commun. Acm, 1975, 18: 409-413.

[2] Toussaint G. solving geometric problems with the rotating calipers [C]//Proceedings of IEEE Mediferranean Electrotechnical Conference (MELECON'83), 1983: A10.02/1-4.

[3] Shamos M I. Computational geometry [D]. Ph.D. thesis, Yale University, 1978.

[4] Alt H, Hurtado F. Packing convex polygons into rectangular boxes [J]. Discrete and Computational Geometry, 2001: 67-80.

[5] D. Chaudhuri A S. A simple method for fitting of bounding rectangle to closed regions [J]. Pattern Recognition, 2007, 40: 1981-1989.

[6] Huang Yijun, Shi Deheng, Xu Qifu. A better nesting method for sheet metal CAD [J]. Journal of Computer Aided Design and Computer Graphics, 2000, 12(5): 380-383黃宜軍, 施德恒, 許啟富. 鈑金CAD中一個較優(yōu)的排料算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2000, 12(5): 380-383.

[7] Xue Yingchun, Xu Wenbo, Sun Jun. Rectanglepacking optimization utilizing hybrid genetic algorithms [J]. Computer Engineering and Design, 2007, 28(22): 5457-5460.薛迎春，須文波, 孫 俊. 基于遺傳模擬退火混合算法的矩形包絡(luò)求解[J]. 計(jì)算機(jī)科學(xué)與工程, 2007, 28(22): 5457-5460.

[8] Zhou Peide. Computational geometry—algorithm design and analysis [M]. 2nded. Beijing: Tsinghua University Press, 2005: 101-102.周培德. 計(jì)算幾何——算法設(shè)計(jì)與分析(第2版). [M].北京: 清華大學(xué)出版社, 2005: 101-102.

The Solution to Determine the Bounding Rectangle with Maximum Aspect Ratio for 2D Graphics

Zhou Min1, Zheng Guolei1, Chen Shulin2
( 1. School of Mechanical Engineering and Automation, Beihang University, Beijng 100191, China; 2. Shenyang Aircraft Industry(Group) Corporation Ltd, Shenyang Liaoning 110034, China )

The bounding rectangle with maximum aspect ratio is a potential property of 2D graphics. This plays important roles in applications including the intelligent design of plane geometry, certain packing and optimum layout problems, as well as pattern recognition. However, no previous research is known for the problem. In this paper, a solution based on the convex hull of the given graphics is proposed to determine it. By analyzing the formulae for the maximum aspect ratio and the rotation range of the rectangle on which four given vertexes of the polygon are, one significant theorem is introduced and proved to show that one side of the maximum-aspect-ratio enclosing rectangle must be collinear with an edge of the enclosed polygon. According to this theorem, we determine the target rectangle by computing and then comparing the aspect ratios of n bounding rectangles which respectively have a side being collinear with different edge of the graphics’ convex hull with n edges. The experimental results are showed to prove that the solution is both accurate and efficient.

computational geometry; bounding rectangle; aspect ratio; aircraft template design

TP 391.7

A

2095-302X (2013)04-0046-08

2012-10-11；定稿日期：2012-11-19

周 敏（1985-），女，四川崇州人，博士研究生，主要研究方向?yàn)槊嫦蛑悄芑O(shè)計(jì)制造的模型幾何屬性計(jì)算方法與應(yīng)用。E-mail：zhoumin.buaa@139.com

鄭國磊（1964-），男，福建莆田人，教授，博士生導(dǎo)師，主要研究方向?yàn)镃AD/CAM，夾具智能化設(shè)計(jì)和數(shù)字化裝配。E-mail：zhengguolei@buaa.edu.cn陳樹林（1984-），男，江西余江人，博士，主要研究方向?yàn)镃AD/CAM/NC。Email: csl_buaa@139com