祝 林，胡鐵牛

(上海交通大學船舶海洋與建筑工程學院，上海 200240）

船舶工程計算中圖形剪裁方法的改進及應用

祝 林，胡鐵牛

(上海交通大學船舶海洋與建筑工程學院，上海 200240）

提出一種在船舶工程計算中具有廣泛用途的用任意閉曲線裁剪任意閉曲線的裁剪方法。將這種改進的裁剪算法與環(huán)形積分法相結合編制計算模塊，可將原來工程計算中繁瑣的運算過程大大簡化，可用來處理船舶工程中經(jīng)常遇到的圖形面積和形心的計算等問題。闡述其在船舶工程性能計算中的應用，并通過實例計算驗證其精度。

任意閉曲線;圖形裁剪;船舶性能計算

0 引言

在船舶工程設計計算過程中，經(jīng)常要進行各種性能的計算，例如初穩(wěn)性、破艙穩(wěn)性等。這些計算要涉及到大量的圖形幾何特征值 (如面積、形心等）的計算，在之前的設計計算中，通常對不同的計算問題采用不同的計算模型，這種處理方法不僅計算繁瑣，而且通用性差。而這些二維圖形的幾何特征值計算實際上都可看作二維圖形剪裁，因此理論上可以用二維圖形裁剪的方法對這類問題進行處理。

針對二維裁剪，國內(nèi)外學者們先后提出許多算法，如凸多邊形窗對線段進行裁剪的Cyrus-Beck算法、凸多邊形窗對線段進行裁剪的Sutherland-Hodgman算法和任意多邊形對任意多邊形裁剪的Weiler-Atherton算法［1－3］等。國內(nèi)的一些學者也提出一些改進的算法或相似的新算法，例如李雪、石廣田的一種新的任意四邊形窗口線裁剪算法［4］;陳濤的適用于凹多邊形的Cyrus-Beck改進算法［5］等。

在船舶工程設計計算中，所涉及的圖形常為用離散點表示的任意形狀圖形，裁剪多邊形也常為任意閉曲線。而上述二維裁剪方法中被裁剪圖形和裁剪多邊形大多被限制為多邊形。為此，本文從比較成熟的多邊形裁剪多邊形的Weiler－Atherton算法出發(fā)，對其進行改進，使改進后的算法可以用任意閉曲線去裁剪任意形狀圖形，從而適合船舶與海洋工程設計計算的特點。

利用改進后的裁剪算法并結合環(huán)形積分法編制二維圖形計算模塊，利用該模塊可以方便地計算船舶工程設計當中求解二維圖形幾何特征值的問題，例如，求任意傾斜水線下船體或艙室橫剖面面積及形心等。

1 基本原理

1.1 任意閉曲線裁剪任意圖形的方法

圖形的裁剪運算通過圖形邊界來進行，當2個圖形進行裁剪運算產(chǎn)生新的圖形，就意味著產(chǎn)生了新的圖形邊界，新的邊界由原來圖形的部分邊界構成。求新圖形邊界的關鍵是準確求出原圖形邊界的所有交點的數(shù)目、位置及其順序，進而求得組成新邊界的各段原圖形邊界，按正確的順序組成新圖形邊界。利用改進算法進行圖形裁剪的基本原理如下(見圖1）:

現(xiàn)規(guī)定被裁減圖形A的邊界離散點和閉曲線B的離散點均按順時針方向排序。

圖1 改進后裁剪原理示意Fig.1 Principle of improved figure clippingmethod

3）計算交點特征值 (確定求得的交點是入點還是出點）。如果被裁減圖形A的邊界曲線從該交點按順時針方向進入裁剪閉曲線B且按逆時針方向則離開裁剪閉曲線B，則該點稱為入點;如果被裁減圖形A的邊界曲線從該交點按順時針方向離開裁剪閉曲線且按逆時針方向則進入裁剪閉曲線B，則該點稱為出點。具體可按如下方法確定:

1.2 環(huán)行積分法

求得FC(x，y）后，繞裁剪后圖形C的邊界閉曲線按順時針方向進行環(huán)行積分，即可求得裁剪后的圖形C區(qū)域面積等幾何特征值。證明如下:

圖2 波浪與船體橫截面示意圖Fig.2 Sketch of wave and ship cross section

2 計算應用

下面結合該方法在船舶處于波浪中時排水量計算中的應用來進一步闡述該改進的二維圖形剪裁方法的原理并驗證其計算精度。

在求某時刻船舶處于波浪中的排水量時，通常已知該時刻船舶所處區(qū)域內(nèi)波浪在船舶坐標系下的統(tǒng)計散點數(shù)據(jù)以及該船舶的型值。為了求得船舶的排水量，通常采用先在不同站處進行橫截面積積分，再沿船舶縱向進行積分［6］，從而求得船舶的排水量。該計算過程當中，在不同站處的橫截面即可用二維裁剪的方法進行處理，如圖2所示。在下面的算例中，因為該船體橫截面及波浪散點數(shù)據(jù)均對稱于Y軸，所以取該船體橫截面的一半和可包圍這一半橫截面的波浪散點數(shù)據(jù)進行計算 (見圖3）。

圖3 剪裁實例Fig.3 Example of improved figure clipping

2.1 已知數(shù)據(jù)

如圖3所示，船體半橫截面邊界所構成的被剪裁閉曲線散點序列見表1(其中點Q是為將船體橫截面構成閉曲線而人為增加的點，不包括a，b兩點）;某時刻某波浪在圖3所示坐標系下的統(tǒng)計數(shù)據(jù)所構成的剪裁閉曲線散點序列如表2所示 (其中點22和點23是為將波浪曲線構成閉曲線而人為增加的兩點）。

表1 被裁減閉曲線散點序列 (單位:m）Tab.1 Discrete points of the clipped figure

表2 裁剪閉曲線散點序列 (單位:m）Tab.2 Discrete points of the clipping figure

2.2 求被裁剪閉曲線和裁減閉曲線的擬合方程

將原始的船體橫截面散點用參數(shù)樣條進行擬合，人為增加的點R與相鄰點之間用直線擬合，記擬合后的被裁減閉曲線函數(shù)為FA;

將原始的波浪散點數(shù)據(jù)用參數(shù)樣條進行擬合，人為增加的點與點之間以及人為增加的點與原始的波浪散點之間用直線擬合，記擬合后的裁剪閉曲線函數(shù)為FB。

2.3 求入點和出點

令FA=FB，可求得裁剪閉曲線與被裁減曲線的交點有2個，分別為:

根據(jù)前面入點和出點的定義可知，點b為入點，點a為出點。

將a和b點的坐標數(shù)據(jù)分別按順序放入裁剪和被裁減曲線數(shù)據(jù)中，在本例中a，b兩點恰為裁剪閉曲線的原始數(shù)據(jù)點5和點18，排列好的數(shù)據(jù)見表1(包括a，b兩點）和表2(標號加粗的5，18兩點為交點）。

2.4 求新邊界曲線數(shù)據(jù)

在表1中按順序需找到入點b，按順序記錄b，C，D，E，F(xiàn)，G，H，I，J，K，L，M，N，O，P，a的數(shù)據(jù)，并標記這些點屬于被裁減曲線;因為a為出點，此時轉(zhuǎn)向表2，從表2中5處按順序記錄5，6，7，8，9，10，11，12，13，14，15，16，17，18的數(shù)據(jù)，并標記這些點屬于剪裁曲線;因為18點屬于入點且與初始入點b相同，裁剪結束。

裁剪后的曲線邊界由 b(18），C，D，E，F(xiàn)，G，H，I，J，K，L，M，N，O，P，a(5），6，7，8，9，10，11，12，13，14，15，16，17，b(18）等點按順時針順序確定，如圖4所示。

圖4 剪裁后的新圖形CFig.4 New figure after clipping

求得新邊界后對屬于被裁減曲線和裁剪曲線的邊界數(shù)據(jù)點分別按照被裁減曲線和裁剪曲線的擬合方式進行擬合即可。擬合后的曲線方程記為FC。

2.5 求新邊界所圍成的區(qū)域的面積

利用1.2節(jié)中的環(huán)形積分法，即可求得圖4中閉曲線所圍部分的面積

式中:D為FC所圍成的平面區(qū)域;C為D的邊界曲線 (方向為順時針）。

在本例中，將已知數(shù)據(jù)輸入已經(jīng)編好的計算模塊，可得圖3陰影部分的面積S=8.189 m2。

2.6 精度分析

實際上，波浪的真實曲線函數(shù)為:

由此可見，這種改進后的剪裁方法的計算精度還是非常高的，而且隨著有效數(shù)據(jù)點的增多，這種精度將進一步提高。

3 結語

本文提出一種適用于二維圖形裁剪中任意圖形裁剪任意圖形的改進算法，可以廣泛應用于船舶工程設計計算中，計算實例也證明了其計算精度相當可靠。該方法還可應用于船舶與海洋工程工程計算的其他各個領域。例如:求解橫剖面形狀比較特殊船舶面積和形心;在半潛式鉆井平臺破艙計算中求解各傾斜水線面下的進水艙體積及形心等。根據(jù)該算法編制的計算模塊可以方便地作為船舶與海洋工程設計計算的基礎模塊供開發(fā)調(diào)用。該方法還可處理二維裁剪中偶爾出現(xiàn)的特殊情況(如裁剪過程出現(xiàn)切點、線段重疊等），進一步提高了該改進算法的通用性。

［1］CYRUS I.BECK J.Generalized two-and-three-dimensional clipping［J］.Computer and Graphies，1978，3(1）:23 －28.

［2］SUTHERLAND I E.HODGMAN G W.Reentrant polygon clipping［J］.Communication of the ACM，1994，17(1）:32 －40.

［3］WEILER K，ATHERTON P.Hidden surface removal using polygon area sorting［J］.SiGGPAPH 77 Proceedings，1977，11(2）:214－222.

［4］李雪，石廣田.一種新的任意四邊形窗口線裁剪算法［J］.蘭州交通大學學報，2005，24(6）:90 －92.

LIXue，SHIGuang-tian.A new algorithm for line clipping against a general quadrilateral［J］.Journal of Lanzhou Jiaotong University，2005，24(6）:90 －92.

［5］陳濤.適用于凹多邊形的Cyrus－Beck改進算法［J］.計算機科學，2006，33(12）:217 －220.

CHEN Tao.An improved algorithm of cyrus beck segment clipping to process concave polygon［J］.Computer Science，2006，33(12）:217 －220.

［6］盛振邦，楊尚榮，陳雪深.船舶靜力學.北京:國防工業(yè)出版社，1992.

SHENG Zheng-bang，YANG Shang-rong，CHEN Xue-shen.Statics of the ship［M］.Beijing:National Defence Industry Press，1992.

The improvement and application of figure clippingmethod in ship design

ZHU Lin，HU Tie-niu
(School of Naval Architecture，Ocean and Civil Engineering，Shanghai Jiaotong University，Shanghai200240，China）

An improved figure clippingmethod is presented，which can bewidely used in ship design and ocean engineering to calculate the area and center of the figures.With the calculation module based on the improved figure clipping method，these complicated operations can be simplified and realized easily.Some examples are given to illustrate it.

closed curve;figure clippingmethod;ship performance calculation

U662

A

1672－7649(2014）04－0049－04

10.3404/j.issn.1672－7649.2014.04.009

2013－01－18;

2013－01－29

祝林(1986－），男，碩士研究生，主要從事船舶與海洋結構物設計制造方面的研究。