平面多邊形增減頂點(diǎn)時(shí)中值坐標(biāo)的計(jì)算

朱方妍，張善奎，鄧重陽(yáng)

(杭州電子科技大學(xué)理學(xué)院,浙江 杭州 310018)

摘要：中值坐標(biāo)是定義在任意平面多邊形上最常用的重心坐標(biāo)。揭示了增減平面多邊形的頂點(diǎn)時(shí)，多邊形所在平面內(nèi)點(diǎn)的中值坐標(biāo)的變化情況，即當(dāng)多邊形減少或增加一個(gè)頂點(diǎn)時(shí)，則除去所增減的點(diǎn)以及它的兩個(gè)相鄰點(diǎn)外，其余各點(diǎn)對(duì)應(yīng)的規(guī)范化中值坐標(biāo)變?yōu)樵瓉淼某?shù)倍。

關(guān)鍵詞：推廣的重心坐標(biāo);中值坐標(biāo)；平面多邊形

DOI: 10.13954/j.cnki.hdu.2015.01.022

平面多邊形增減頂點(diǎn)時(shí)中值坐標(biāo)的計(jì)算

朱方妍，張善奎，鄧重陽(yáng)

(杭州電子科技大學(xué)理學(xué)院,浙江 杭州 310018)

摘要：中值坐標(biāo)是定義在任意平面多邊形上最常用的重心坐標(biāo)。揭示了增減平面多邊形的頂點(diǎn)時(shí)，多邊形所在平面內(nèi)點(diǎn)的中值坐標(biāo)的變化情況，即當(dāng)多邊形減少或增加一個(gè)頂點(diǎn)時(shí)，則除去所增減的點(diǎn)以及它的兩個(gè)相鄰點(diǎn)外，其余各點(diǎn)對(duì)應(yīng)的規(guī)范化中值坐標(biāo)變?yōu)樵瓉淼某?shù)倍。

關(guān)鍵詞：推廣的重心坐標(biāo);中值坐標(biāo)；平面多邊形

DOI:10.13954/j.cnki.hdu.2015.01.022

收稿日期：2014-06-16

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61370166)

通信作者：

作者簡(jiǎn)介：朱方妍(1991-)，女，河南商丘人，在讀研究生，計(jì)算數(shù)學(xué).鄧重陽(yáng)副教授，E-mail: dcy@hdu.edu.cn.

中圖分類號(hào)：O24

文獻(xiàn)標(biāo)識(shí)碼：：A

文章編號(hào)：：1001-9146(2015)01-0104-03

Abstract:Mean value coordinates are the most commonly barycentric coordinates defined in arbitrary planar polygon. This paper reveals how the coordinates of the interior point in a planar polygon change as the vertexes are increased or decreased， namely， when the polygon reduces or increases a vertex， except the increased or decreased and its two adjacent points， the rest values of the normalized coordinates at the corresponding points turn into a constant multiple of the original.

0引言

定義在三角形上的重心坐標(biāo)可以將三角形所在平面內(nèi)的任意點(diǎn)唯一地表示為三角形三個(gè)頂點(diǎn)的線性組合，所以廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué)、幾何造型、地形建模和有限元[1]等領(lǐng)域。近年來，涌現(xiàn)出很多類型的重心坐標(biāo)，使之推廣到任意多邊形乃至多面體，如調(diào)和坐標(biāo)[2]、中值坐標(biāo)[3]、復(fù)數(shù)坐標(biāo)[4]、矩陣坐標(biāo)[5]、泊松坐標(biāo)[6]以及局部坐標(biāo)[7]。其中最成功的方法當(dāng)屬Floater提出的中值坐標(biāo)[8-10]，因?yàn)槠渚哂羞m用于平面任意多邊形、在多邊形平面內(nèi)任意一點(diǎn)都有定義、無窮階連續(xù)、計(jì)算穩(wěn)定等優(yōu)良特性。

在計(jì)算機(jī)動(dòng)畫設(shè)計(jì)和幾何造型等領(lǐng)域中，為了設(shè)計(jì)出所需的形狀，常常要在已有多邊形的基礎(chǔ)上增加或者減少頂點(diǎn)。在增減頂點(diǎn)后，如果所有的中值坐標(biāo)全部重新計(jì)算，必然會(huì)導(dǎo)致很大的計(jì)算量。本文揭示了增減平面多邊形的頂點(diǎn)時(shí)，多邊形所在平面內(nèi)點(diǎn)的中值坐標(biāo)的變化情況，即當(dāng)多邊形減少或增加一個(gè)頂點(diǎn)時(shí)，則除去所增減的點(diǎn)以及它的兩個(gè)相鄰點(diǎn)外，其余各點(diǎn)對(duì)應(yīng)的規(guī)范化中值坐標(biāo)變?yōu)樵瓉淼某?shù)倍。這樣可以大大減少后續(xù)的計(jì)算量。

1多邊形在增減頂點(diǎn)時(shí)中值坐標(biāo)的變化

1.1　減少一個(gè)頂點(diǎn)

如圖1所示，記多邊形Ψ的頂點(diǎn)為v1，v2，…，vn，ri(v)為vi到v的歐幾里得距離，αi(v)表示三角形[v，vi，vi+1]在頂點(diǎn)v處的有向角，則點(diǎn)v相對(duì)多邊形Ψ的各個(gè)頂點(diǎn)的齊次中值坐標(biāo)函數(shù)[9]為：

(1)

圖1　減少多邊形的一個(gè)頂點(diǎn)

(2)

(3)

(4)

從上述關(guān)系式可以看出，多邊形Ψ減少一個(gè)頂點(diǎn)vj之后，除了點(diǎn)vj的相鄰點(diǎn)vj-1和vj+1外，其余各點(diǎn)對(duì)應(yīng)的規(guī)范化中值坐標(biāo)與原來的相比只相差一個(gè)常數(shù)倍。

1.2　增加一個(gè)頂點(diǎn)

增加新點(diǎn)可以分為新點(diǎn)在邊上或不在邊上這兩種情況，前一種情況已有定論(參見文獻(xiàn)[9])，這里只考慮第二種情況。

(5)

(6)

圖2　增加多邊形的一個(gè)頂點(diǎn)

2數(shù)值例子

取多邊形邊數(shù)為n=10，多邊形的頂點(diǎn)坐標(biāo)x0=[0.400 4，0.607 4，0.806 6，0.896 5，0.646 5，0.419 9，0.162 1，0.322 3，0.150 4，0.193 4]，y0=[0.962 8，0.956 1，0.848 0，0.543 9，0.003 4，0.091 2，0.077 7，0.327 7，0.523 6，0.848 0]。

然后，在該多邊形內(nèi)任取一點(diǎn)(x，y)=(0.537 1，0.543 9)的關(guān)于此多邊形的重心坐標(biāo)λ1=[0.073 3，0.079 3，0.112 7，0.219 6，0.118 3，0.059 3，0.027 9，0.089 5，0.127 8，0.092 4]。

去掉第4個(gè)頂點(diǎn)后，得到九邊形的重心坐標(biāo)λ2=[0.063 6，0.068 8，0.304 5，0.219 0，0.051 5，0.024 2，0.077 6，0.110 8，0.080 1]。在第4和第5個(gè)頂點(diǎn)之間加上一個(gè)新頂點(diǎn)(0.959 0，0.091 2)后，得到十一邊形的重心坐標(biāo)λ3=[0.077 5，0.083 9，0.119 2，0.162 1，0.076 3，0.061 2，0.062 8，0.029 5，0.094 6，0.135 2，0.097 7]。

通過計(jì)算，除了減少的頂點(diǎn)和此頂點(diǎn)的兩個(gè)相鄰點(diǎn)之外，其余頂點(diǎn)對(duì)應(yīng)的中值坐標(biāo)與原來比值均為0.867 4，除了增加的頂點(diǎn)和此頂點(diǎn)的兩個(gè)相鄰點(diǎn)外，其余頂點(diǎn)對(duì)應(yīng)的中值坐標(biāo)與原來的比值為1.057 7。

以上數(shù)值模擬實(shí)驗(yàn)說明，理論分析與實(shí)驗(yàn)?zāi)M相吻合。另外，根據(jù)多次數(shù)值模擬結(jié)果得出，對(duì)于內(nèi)部點(diǎn)，多邊形減少頂點(diǎn)時(shí)，它相對(duì)其余頂點(diǎn)的的中值坐標(biāo)變?yōu)樵瓉淼膍倍，其中m≤1；多邊形增加頂點(diǎn)時(shí)，它相對(duì)其余頂點(diǎn)的中值坐標(biāo)變?yōu)樵瓉淼膎倍，其中n≥1。對(duì)于外部點(diǎn)，中值坐標(biāo)的變化情況正好與此相反。

3結(jié)束語

在形狀編輯中，平面多邊形增減頂點(diǎn)是一個(gè)非常常見的操作。通過理論分析，本文得出多邊形增減頂點(diǎn)時(shí)，多邊形所在平面內(nèi)一點(diǎn)的中值坐標(biāo)的變化規(guī)律。本文所討論算法可以有效地提高圖形編輯中所涉及的數(shù)值計(jì)算的效率。

參考文獻(xiàn)

[1]Wachspress E L. A Rational Finite Element Basis[M]. Burlington： Elsevier，1975：88-125.

[2]Joshi P， Meyer M， DeRose T， et al. Harmonic coordinates for character articulation[J]. ACM Transactions on Graphics(TOG)，2007，26(3):71.

[3]Floater M S. Mean value coordinates[J]. Computer Aided Geometric Design，2003，20(1):19-27.

[4]Weber O， Ben-Chen M，Gotsman C.Complex Barycentric Coordinates with Applications to Planar Shape Deformation[J]. Computer Graphics Forum，2009，28(2):587-597.

[5]黃力慰，李桂清，熊赟暉.矩陣重心坐標(biāo)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23(12):1 959-1 966.

[6]Li X Y， Hu S M. Poisson coordinates[J]. IEEE Transactions on Visualization and Computer Graphics，2013，19(2):344-352.

[7]Zhang J Y， Deng B L， Liu Z S， et al. Local Barycentric Coordinates[J]. ACM Transactions on Graphics， 2014，33(EPFL-ARTICLE-201 853).

[8]Ju T， Schaefer S， Warren J. Mean value coordinates for closed triangular meshes[J]. ACM Transactions on Graphics(TOG)，2005，24(3):561-566.

[9]Hormann K， Floater M S. Mean value coordinates for arbitrary planar polygons[J]. ACM Transactions on Graphics(TOG)，2006，25(4):1 424-1 441.

[10]Bruvoll S， Floater M S. Transfinite mean value interpolation in general dimension[J]. Journal of Computational and Applied Mathematics，2010，233(7):1 631-1 639.

Calculation of Mean Value Coordinates in Process of

Planar Polygon Vertexes’ Decrease or Increase

Zhu Fangyan， Zhang Shankui， Deng Chongyang

(SchoolofScience，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Key words: general barycentric coordinates; mean value coordinates; planar polygon