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

周 敏， 鄭國磊， 陳樹林

（1. 北京航空航天大學機械工程及自動化學院，北京 100191；2. 沈陽飛機工業（集團）有限公司，遼寧 沈陽 110034）

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

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

（1. 北京航空航天大學機械工程及自動化學院，北京 100191；2. 沈陽飛機工業（集團）有限公司，遼寧 沈陽 110034）

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

計算幾何；最狹長包絡矩形；長寬比；飛機樣板設計

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

圖1 不同設計坐標系下設計的樣板

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

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

1 最狹長包絡矩形及其性質

1.1 包絡角

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

圖2 二維圖形的包絡矩形

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

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

定義 3 當 R順時針包絡轉動到極限位置時，稱R的包絡位角為R的包絡始角，用ω1表示。而當R逆時針包絡轉動到極限位置時，稱R的包絡位角為 R的包絡終角，用 ω2表示。令ωb=ω2-ω1，則稱ωb為R的包絡角。

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

圖3 包絡角示意圖

為求包絡始角與包絡終角，引入定義4。

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

或

圖4 包絡矩形的有效轉動角

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

或

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

或

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

或

引理1得證。

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

1.2 最狹長包絡矩形

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

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

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

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

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

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

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

進而可得R的長寬比f為：

圖 5 過凸包上四頂點 vl、vd、vr和 vu的包絡矩形

為單調遞增的有界連續函數。

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

圖6 θ與ω線性相關

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

圖7 當θ取得最大值時的包絡矩形

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

表1 矩形逆時針轉動時f求解公式及其最小值

分析表1有：

2） 當矩形在滿足ω1≤ω≤ω2條件的范圍內轉動時，A, B, C, D的相對位置關系發生變化，如由B, A, D, C（①）變為A, B, C, D（④），f的計算公式由（2）變為（1），但f仍在ω1處取得最小值；當A, B, C, D的相對位置關系繼續變化時，這個結論不變。即f在何處取得最小值由A, B, C, D的初始位置確定，所以，f總是在ω1或ω2處取得最小值或最大值，而包絡位角ω為ω1或ω2，矩形都有一條邊與凸包的某一條邊共線。由此，定理1得證。

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

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

2 計算方法及其實現

2.1 計算方法

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

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

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

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

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

其中：

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

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

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

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

2.2 實現及分析驗證

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

圖 11 開曲線

圖 12 任意圖形

圖13 飛機壁板輪廓1

圖14 飛機壁板輪廓2

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

分析表2可知：

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

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

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

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

3 結 論

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

[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中一個較優的排料算法[J]. 計算機輔助設計與圖形學學報, 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.薛迎春，須文波, 孫 俊. 基于遺傳模擬退火混合算法的矩形包絡求解[J]. 計算機科學與工程, 2007, 28(22): 5457-5460.

[8] Zhou Peide. Computational geometry—algorithm design and analysis [M]. 2nded. Beijing: Tsinghua University Press, 2005: 101-102.周培德. 計算幾何——算法設計與分析(第2版). [M].北京: 清華大學出版社, 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-），女，四川崇州人，博士研究生，主要研究方向為面向智能化設計制造的模型幾何屬性計算方法與應用。E-mail：zhoumin.buaa@139.com

鄭國磊（1964-），男，福建莆田人，教授，博士生導師，主要研究方向為CAD/CAM，夾具智能化設計和數字化裝配。E-mail：zhengguolei@buaa.edu.cn陳樹林（1984-），男，江西余江人，博士，主要研究方向為CAD/CAM/NC。Email: csl_buaa@139com