基于向量積的多邊形中心的計算方法

基于向量積的多邊形中心的計算方法

王紅喜

(陜西職業(yè)技術學院 計算機系，西安 710100)

摘要：為了確定多邊形的中心，將多邊形分割為三角形，利用向量的向量積計算各個三角形和多邊形的面積，給出計算多邊形中心的一種方法,并對具體的數(shù)據(jù)進行了仿真實驗.結果表明算法的正確性和可行性.

關鍵詞：多邊形；向量的向量積；中心

中圖分類號：O24文獻標志碼：A

文章編號：1008-5564(2015)03-0042-05

收稿日期：2015-04-30

基金項目：江蘇省高校自然科學研究面上項目(14KJB18000)；江蘇省高等學校大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(201410292025Z)；常州大學學生課外創(chuàng)新創(chuàng)業(yè)基金資助項目(2014-02-A-04)

作者簡介：李琳(1994—)，女，江蘇鎮(zhèn)江人，常州大學生物醫(yī)學工程與健康科學研究院常州市呼吸醫(yī)學工程重點實驗室學生，主要從事生物技術研究.

通訊作者：＊鄧林紅 (1960— )，男，四川夾江人，常州大學生物醫(yī)學工程與健康科學研究院常州市呼吸醫(yī)學工程重點實驗室教授，博士生導師，教育部 “長江學者獎勵計劃”特聘教授，主要從事生物力學和呼吸醫(yī)學工程研究.

An Algorithm Base on the Cross Product of Vectors forDetermining the Center of Polygons

WANG Hong-xi

(Deparment of Computer, Shaanxi Vocational & Technical College, Xi’an 710100, China)

Abstract：An algorithm is provided to determine the center of polygons. In this algorithm, polygons are divided into triangles and areas of every triangle and polygon are calculated by the cross product of vectors. Eventually the specific data are simulated and the results show that the algorithm is correct and feasible.

Key words：polygons; cross product of vectors; center of polygons

計算多邊形的中心在生產(chǎn)實踐中有著廣泛的應用.例如，在材料應用中，對多邊形的金屬板件或木質(zhì)板材的余料加工時，為了提高材料利用率，減少廢料，確定最大內(nèi)圓的圓心以及半徑是一個常見問題[1-2]；在高層建筑物維修中，需要測量建筑物諸如傾斜、彎曲等變形問題.可通過計算建筑物各層中心連線是否在同一直線上確定.計算多邊形中心有多種算法，文獻[1]給出了一種任意多邊形中心的計算方法，但該方法需根據(jù)參考點確定圓心的搜索方向，同時步長因子的選取對計算時間有著較大的影響.

本文提出一種針對任意多邊形計算中心(尋找最大內(nèi)圓)的方法，首先將多邊形分割為多個互補相交的三角形，然后利用向量的向量積計算各個三角形的面積進而得到多邊形的面積，最終確定多邊形的質(zhì)心(中心)，克服了文獻[1]中計算的缺點.同時為了驗證算法的正確性和可行性，利用Matlab軟件對具體的算例進行了實驗.同時與文獻[1]方法計算的結果進行了比較.結果表明，本文方法計算正確且易于實現(xiàn)，具有一定的應用價值.

1數(shù)學知識

則質(zhì)心即為中心，其坐標表示為：

(1)

若多邊形結構的薄片是均勻的，則密度ρ=μ(x,y)為常數(shù)，S為區(qū)域D的面積，則質(zhì)心即為中心，則公式(1)化為：

(2)

2算法與數(shù)值計算

首先，計算區(qū)域D的面積S，討論以下兩種情形：

(3)

圖1　多邊形的分割

(b)若多邊形為形邊數(shù)n(n>3)，多邊形頂點坐標為Ai(xi,yi)(i=1,…,n)，此時將多邊形分割成互不相交的n個三角形△A1OA2,△A2OA3,…,△An-1OAn，如圖1所示(以八邊形為例).

其次，質(zhì)心(中心)的計算.

(4)

故質(zhì)心(中心)的數(shù)值計算只需將(4)式的計算結果和S帶入(2)式即可.需要說明的是，若多邊形為三角形，則(2)式的分子項計算仍需要按(b)中討論的方法算出，分母項則可按公式(3)計算得到.

以上討論歸結為算法：

Step1.記多邊形的頂點個數(shù)為n(n≥3);

Step2.Fori=3:n

Ifn=3

①利用公式(3)計算多邊形的面積S；

else

轉(zhuǎn)②

End

3算例及比較結果

為驗證本算法的正確性和可行性，分別用文獻[1]的方法和本文方法對具體的數(shù)據(jù)進行了實驗.設多邊形為八邊形，其頂點以及坐標為：A1(565.454,528.012)、A2(562.058,528.012)、A3(561.39,521.477)、A4(563.782,518.108)、A5(567.941,517.407)、A6(571.255,519.857)、A7(571.938,523.953)、A8(569.5,527.356).(數(shù)據(jù)來源：2013全國大學生數(shù)學建模乙組C題).采用Matlab軟件計算八邊形的中心結果如表1.

表1　兩種方法的計算結果

對于兩組數(shù)據(jù)A、B，采用誤差公式‖A-B‖2，將表一的兩組數(shù)據(jù)帶入可得兩種方法的誤差不超過0.7.兩種方法計算的結果較為接近.而文獻[1]方法計算需花費幾分鐘，而本文方法僅僅需要幾秒鐘即可算出，需說明的是兩種方法都是在Matlab軟件環(huán)境下實現(xiàn)的.文獻[1]方法則是AutoLISP環(huán)境下實現(xiàn)的，計算時需要對數(shù)據(jù)先進行處理.由于實際問題需要處理大量的數(shù)據(jù)，使用Matlab軟件更為方便.

4結語

本文給出了一種計算任意多邊形的中心(尋找最大內(nèi)圓)的計算方法，對多邊形采用了分割的方法，利用向量的向量積計算分割出圖形的面積進而求出多邊形的面積，然后就算出多邊形的中心.最后需說明的是：本文的方法討論的是對于多邊形形狀的構件，假設材料是均勻的.若材料不均勻計算時將多邊形各頂點處的密度帶入公式(1)即可.本文數(shù)學原理清晰，構思巧妙，算法簡單且易于實現(xiàn).同時利用具體的數(shù)據(jù)對文獻[1]的方法和本文方法進行了實驗.結果表明本文算法的正確性和可行性，具有一定的應用價值.

[參考文獻]

[1]鄭梅生,陳寧,宋超.計算任意多邊形最大內(nèi)圓的一種算法[J].機械設計與制造,2003,5 :84-85..

[2]宋繼明,宋華松,汪以文.特殊地形條件下桿塔傾斜率的測量方法[J].電網(wǎng)技術,2012,34(12):219-222.

[3]竇長旭,王玉玫.多邊形中心點向量的二次插值變形算法[J].計算機工程,2010,36(16):189-191.

[4]同濟大學應用數(shù)學系.高等數(shù)學(第五版)[M].北京：高等教育出版社，2002.

[5]陸金甫,關治.偏微分方程數(shù)值解法[M].北京：清華大學出版社,2004.

[責任編輯王新奇]

Vol.18No.3Jul.2015