基于衍生多邊形的混合坐標

黃 茹，李亞娟，鄧重陽

(杭州電子科技大學理學院，浙江 杭州 310018)

1827 年，M?BIUS[1]首次提出2D 重心坐標的概念：平面三角形內任意一點可由三角形的頂點線性表示，該線性組合的系數(shù)就是三角形內該點的重心坐標。1975 年，WACHSPRESS[2]首次提出多邊形頂點數(shù)量大于 3 的重心坐標(wachspress coordinates，WC)，但該重心坐標僅對凸多邊形有明確的定義。2003 年，F(xiàn)LOATER[3]提出2D 的均值坐標(mean value coordinates，MVC)，該坐標對任意多邊形有明確的定義，且在多邊形內部光滑。2005 年，F(xiàn)LOATER 等[4]提出3D 的均值坐標，該坐標可表示四面體內部的一點關于四面體頂點的凸組合。2006 年，LANGER 等[5]提出球重心坐標(spherical barycentric coordinates)，在球體上定義平面重心坐標系中的任意重心坐標，并給出球體上一點相對于給定球面三角形頂點的重心坐標。2007 年，JOSHI 等[6]利用調和坐標(harmonic coordinates，HC)，將重心坐標的定義擴展到任意維度，且即使在強凹的情況下重心坐標仍然具有非負性。調和坐標沒有具體的表達式，而是通過求解Laplace方程得到。2008 年，HORMANN 和SUKUMAR[7]提出最大熵坐標(maximum entropy coordinates，MEC)，通過牛頓法求解凸優(yōu)化問題計算得到。最大熵坐標可應用于平面內任意多邊形，且具有非負性。2008 年，LIPMAN 等[8]提出格林坐標(Green coordinates，GC)，利用cage 的頂點與面的法向信息，通過格林第三等式推導得到，在空間變形中具有良好的保形性。2011 年，MANSON 等[9]提出正Gordon-Wixom 坐標(positive Gordon-Wixom coordinates，PGWC)，在任意多邊形內具有非負性，但其光滑性會受到多邊形邊界光滑性的限制。2014 年，ZHANG 等[10]提出局部重心坐標(local barycentric coordinates，LBC)。LBC僅依賴于一部分控制頂點，且通過基于全變分的凸約束優(yōu)化計算得到。2016 年，ANISIMOV 等[11]提出細分重心坐標(subdividing barycentric coordinates，SBC)，將被廣泛使用于構造曲面的細分算法應用于構造重心坐標。2017 年，ANISIMOV等[12]利用混合重心坐標(blended barycentric coordinates，BBC)，對任意多邊形先進行約束Delaunay 三角剖分，在剖分得到的三角形上計算均值坐標，再通過合適的混合函數(shù)計算得到。2019，TAO 等[13]提出新的數(shù)值計算方法計算局部坐標，與之前的局部坐標[10]相比提高了計算效率，但未滿足非負性。2020 年，DENG 等[14]提出迭代坐標(iterative coordinates，IC)，將初始多邊形投影至單位圓，并通過迭代圓上的多邊形，直至計算均值心坐標為非負，最后通過回代得到關于初始多邊形的重心坐標。

本文在三角網格的內部將三角形衍生得到點多邊形、邊多邊形和面多邊形，提出基于衍生多邊形的混合坐標，繼承了HC，LBC 和IC 的局部性和非負性，通過實例還表明在多邊形內部光滑。

1 衍生多邊形

1.1 點多邊形

圖1 點多邊形示意圖((a)邊界點的點多邊形；(b)內部點的點多邊形) Fig.1 Diagram of the point polygon ((a) The point polygon of the boundary point;(b) The point polygon of the inner point)

1.2 邊多邊形

1.3 面多邊形

圖2 邊多邊形示意圖((a)邊界邊的邊多邊形；(b)內部邊的邊多邊形) Fig.2 Diagram of the edge polygon ((a) The edge polygon of the boundary edge;(b) The edge polygon of the inner edge)

2 基于衍生多邊形的混合坐標算法

HC，LBC 和IC 均滿足上述性質，本文提出的基于衍生多邊形的混合坐標繼承了其局部性和非負性，并且在選取合適的混合系數(shù)后還滿足光滑性。

2.1 混合系數(shù)的選取

2.2 基于衍生多邊形的混合坐標

3 實例分析

由文獻[6,10,14]可知HC，LBC 和IC 滿足非負性，則Ak和均滿足非負性，故Bk也滿足非負性。又因為混合系數(shù)為非負的，因此由式(4)可知基于衍生多邊形的混合坐標具有非負性。

因為衍生子多邊形的頂點關于初始多邊形的重心坐標僅與部分初始多邊形的頂點相關，即存在λi=0。又因為點p關于衍生子多邊形頂點的重心坐標僅與部分衍生子多邊形的頂點相關，即存在可知點p通過第k個衍生子多邊形得到關于初始多邊形的初始混合坐標具有局部性，故基于衍生多邊形的混合坐標具有局部性。

圖3 比較了同一多邊形的同一頂點處不同重心坐標的等高線與偽彩圖，其中圖3(d)～(f)分別為使用IC，HC 和LBC 計算衍生多邊形的頂點關于初始多邊形頂點的重心坐標，再使用IC 計算點關于衍生多邊形頂點的重心坐標。如圖3 所示，與均值坐標、迭代坐標、調和坐標相比，基于衍生多邊形的混合坐標具有更好的光滑性。

圖3 不同重心坐標的等高線與偽彩圖((a)均值坐標；(b)迭代坐標；(c)調和坐標；(d) IC_IC 混合坐標；(e) HC_IC 混合坐標；(f) LBC_IC 混合坐標) Fig.3 Iso-high lines and pseudo-color drawings of different center of gravity coordinates ((a) Mean value coordinates; (b) Iterative coordinates;(c) Harmonic coordinates;(d) IC_IC Blended coordinates; (e) HC_IC Blended coordinates;(f) LBC_IC Blended coordinates)

圖4(a)～(f)分別展示了六邊形、七邊形、八邊形、九邊形、十邊形和Woody 的同一頂點處的等高線與偽彩圖。圖4 中從上到下分別使用IC，HC 和LBC計算衍生多邊形的頂點關于初始多邊形頂點的重心坐標，再使用IC 計算點關于衍生多邊形頂點的重心坐標，繪制對同一個多邊形的同一頂點的等高線與偽彩圖，并將其簡稱為 IC_IC，HC_IC，LBC_IC。其中IC_IC，HC_IC 使用MATLAB 的PDE工具箱進行三角化，LBC_IC 使用LBC 使用的Triangle 進行三角化。

圖4 不同多邊形的等高線與偽彩圖((a)六邊形；(b)七邊形；(c)八邊形；(d)九邊形；(e)十邊形；(f) Woody) Fig.4 Iso-high lines and pseudo-color drawings of different polygons ((a) Hexagon;(b) Heptagon;(c) Octagon; (d) Enneagon;(e) Decagon;(f) Woody)

將同一多邊形的初始化三角形網格的數(shù)量取相近數(shù)量，每個面取100 個采樣點，最終計算這些采樣點的時間，見表1。實例表明本文提出的基于衍生多邊形的混合坐標具有好的局部性、非負性和光滑性。由圖4(a)～(d)可觀察到LBC_IC 的局部性比HC_IC 和IC_IC 的更好，對于相同的點處的等高線LBC_IC 顯然與更少的頂點相關。由圖4(c)～(f)可觀察到HC_IC 的光滑性比LBC_IC，IC_IC 的更好。由表1 可觀察到IC_IC 的計算時間最短。

表1 不同多邊形的計算坐標的時間(s) Table 1 The time of calculate barycentric coordinates for different polygons (s)

4 結束語

本文首先給出衍生多邊形的定義，利用三角網格定義點多邊形、邊多邊形和面多邊形?；谘苌噙呅卫肏C，LBC 和IC 計算點關于初始多邊形的初始混合坐標。再使用合適的混合系數(shù)，得到基于衍生多邊形的混合坐標。其中，點多邊形PP?對應的混合系數(shù)為邊多邊形EP?對應的混合系數(shù)為(λ0+λ1)2，(λ1+λ2)2，(λ2+λ0)2；面多邊形EP?對應的混合系數(shù)為

因為衍生多邊形的結構簡單且可經過少許迭代次數(shù)便可使均值重心坐標為正，因此對于相同的多邊形，基于衍生多邊形的混合坐標在計算過程中需要迭代的次數(shù)少于IC，減少了計算量。今后工作的重點是將二維的基于衍生多邊形的混合坐標推廣到三維，并尋找更合適的混合系數(shù)，使得在不改變光滑性的前提下達到更高的連續(xù)性。