彭丰富，方 明



基于稀疏解组合优化的广义重心坐标

彭丰富，方 明

(桂林电子科技大学数学与计算科学学院，广西 桂林 541004)

根据广义重心坐标线性运算的性质与特点，运用广义重心坐标的稀疏解权函数的调和平均组合方法，对空间凸多面体顶点设计了一种求解广义重心坐标的算法，且权函数是带有保形参数的一元函数，因而具有保形优化的特点。构造了2种不同类型的带形参权函数，运用不同权函数及其参数的广义重心坐标将平面图形映射到空间曲面的实例进行了分析，并应用重心坐标常用的等值线工具对保形性进行了比较。

广义重心坐标；稀疏解；组合优化；权函数

MÖBIUS[1]于1827年首先提出了位于三角形内任一点的重心坐标的概念，即该点表示为相应3个顶点的加权系数为该点的重心坐标。通过对顶点加权方法可以推广到任意多边形，称之为广义重心坐标(generalized barycentric coordinate，GBC)。GBC在有限元计算、网格编辑、计算机图形学等有着广泛的应用，由于GBC的不唯一性，从而不同的方法所计算的重心坐标有差异。目前，主要有多种基于平面多边形提出的方法，并一直在发展、应用这些理论，同时也有一些新的方法在不断提出。

1976年WACHSPRESS[2]首次提出了第一种建立在任意凸多边形的GBC：Wachspress coordinates (W坐标)，其计算量较小，得到了如仿射不变形、光滑性等较好的性质，其不足是不能处理非凸多边形。1995年ECK等[3]基于能量最小原理提出了离散调和(discrete harmonic)的GBC，其与W坐标有许多相似性质，但不要求坐标的非负性。2003年FLOATER[4]提出了均值广义重心坐标，其可以对任意多边形计算重心坐标，可以为非凸的，且不要求坐标非负。2004年冯结青和赵豫红[5]分析和比较了各种重心坐标的定义方法，提出一种鲁棒的均值重心坐标计算方法，并从理论和实验两方面证明了均值重心坐标在多边形边界上的拉格朗日性质和线性性质。2005年谷留新和刘克轩[6]将改进的均值坐标应用于平面多边形的变形，提出一种基于多边形星形分解的同构三角网格剖分算法，选用较少的额外点降低了算法复杂度。2015年DENG等[7]对于Floater提出的四边形的广义重心坐标族的极限给出了证明。2016年CHEN和GOTSMAN[8]提出由于调和坐标一般没有封闭的形式，因此必须通过求解一个关于域的离散化的大型线性方程进行数值逼近。2016年FLOATER[9]又研究了凸多边形中常见的几种广义重心坐标的单调性，并发现这些GBC有共同的简单的单调性：与一个顶点相关的坐标函数沿着多边形边界到此顶点的任意直线递增。ÁKOS[10]对W坐标、调和坐标及均值坐标3种GBC方法做了详细地阐述，并运用等值线作为工具进行了比较。

上述GBC方法的提出主要针对平面多边形，并且都是基于点线面之间的距离、面积、角度等尺度关系来构造权系数，优点是其几何意义明显，缺点是难以做到保形及形状调配和优化。近二十年，该方法又被推广到空间多面体领域。2007年JU等[11]对Mean value坐标进行了拓展，推广应用于3D四面体及高维单形多面体的研究。2011年WACHSPRESS[12]对运用W坐标构造有理基函数应用于多边形和四面体做了相应的研究和总结。2013年GUESSAB[13]对任意凸多面体应用重心坐标得到的一元凸函数进行了逼近分析。本文基于四面体的仿射变换应用重心坐标对曲线曲面的构造也得到了一些结论[14-16]。

本文基于GBC本身的代数性质来构造其计算方法，使得重心坐标的计算回到其向量运算的本源，并对该方法进行算法优化，同时考虑基于保形的坐标优化。

1 稀疏解组合广义重心坐标

1.1 单形的稀疏解

其中，≥0，由于重心坐标的规范性，其可以等价于[n]=(0,1,···,–1,+1,···,)T。因而式(1)等价于

1.2 单形的选取准则

在R3中设计了如下的最简单形取法和求解稀疏解：

输入：空间数据点{}，；

输出：最简单形{}，稀疏解。

步骤1.=0={}(=1,2,···,)；

步骤2.3. 若步骤2.2中的假设不成立，扩充到0中寻找，找到可能重复的2，3，同样得到非零数为4的稀疏解；

步骤2.4. 否则为边界面上的内点，由={,1,2,3}确定非零数不超过3的稀疏解；

步骤3.={}，重复步骤2。

图1 R3中最简单形选取方法

2 稀疏解的组合

对于GBC的连续性有如下定理。

权函数u()的选取目标是使得GBC变换对曲线具有保形性，譬如将一条平面线段通过GBC描述到一个曲面上，理想的保形是确保映射到曲面的是一条测地线，由于其优化计算过于复杂，一般也可以通过能量最小的方法进行优化处理。对单形()的u()计算时，选取()的几何重心与的距离d(V())作为参数来进行优化，直观地理解是u()应该随d的增大而减少，也就是单形的重心与越近，该单形占有权重越大。其函数关系如一些文献选取概率密度函数或其他的递减函数。可从计算的角度及重心坐标的性质出发，构造二者的2个实验函数

3 实例分析

从图中可以看出，前者参数具有较好的保形性和等值曲线的光顺性，而后者保形性和光顺性都比较差，其原因是权重函数的递减速度太快，导致图形某些方向的收缩过大，从而导致等值曲线的曲率急速增大。

图2 式(4)参数(x,y)=(2,0)将平面图形映射到曲面

图3 式(4)参数(x,y)=(1,2)把平面图形映射到曲面

图4 式(5)中z=1的平面图形映射及等值线

图5描述的是不同权函数关于d的变化情况。

图5 不同权函数ui (P)关于di的变化情况

4 结束语

为了求解空间广义重心坐标，根据广义重心坐标本源的线性运算性质，运用稀疏解权函数组合的方法，对空间凸多面体顶点构造了一种求解重心坐标的方法，且能选择参数对保形效果进行优化调配。在实例中的等值线均为离散的点，所以未考虑先插值再计算曲率进行对比，从实例的计算结果也验证了方法的可行性。对非凸情形本文未考虑，若是取消重心坐标的非负性，方法应该可以推广。

未来工作的展望主要包括：①对GBC变换的保形性可以用直线映射到测地线为目标的优化方法来研究，但是计算量可能会相当大；②对光滑曲面的映射保形可以选用连续的带参数的概率密度函数作保形优化处理，已有文献对连续闭合曲线的情形给予了讨论，但是对空间闭合曲面还有一定的挑战；③设计自适应的方法来保形优化，而不是对全局进行参数优化，虽然会增加计算量，但是在细节上可以得到更好的效果。

[1] MÖBIUS A F. Derbarycentrischecalcul [D]. Leipzig: Nabu Press, 2010.

[2] WACHSPRESS E L. A rational finite element basis [J]. Journal of Tribology, 1976, 98(4): 635.

[3] ECK M, DEROSC T, DUCHAMP, et al. Multiresolution analysis of arbitrary meshes [C]//In SIGGRAPH ’95: Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1995: 173-182.

[4] FLOATER M S. Mean value coordinates [J]. Computer Aided Geometric Design, 2003, 20(1): 19-27.

[5] 冯结青, 赵豫红. 均值重心坐标的鲁棒算法及其几何性质[J].计算机辅助设计与图形学学报, 2004, 16(6): 772-776.

[6] 谷留新, 刘克轩. 改进的基于Mean value重心坐标的多边形变形[J]. 计算机工程与应用, 2005, 41(29): 74-76.

[7] DENG C Y, SHI F F, LIU J Z. The limit of barycentric coordinates for quadrilaterals [J]. Computer Aided Geometric Design, 2015, 38(C): 38-39.

[8] CHEN R J, GOTSMAN C. On pseudo-harmonic barycentric coordinates [J]. Computer Aided Geometric Design, 2016, 44(15): 15-35.

[9] FLOATER M S. On the monotonicity of generalized barycentric coordinates on convex polygons [J]. Computer Aided Geometric Design, 2016, 42: 34-39.

[10] ÁKOS T. Comparison and affine combination of generalized barycentric coordinates for convex polygons [J]. Annales Mathematicaeet Informaticae, 2017, 47: 185-200.

[11] JU T, LIEPO P, WARREN J. A general geometric construction of coordinates in a convex simplicial polytope [J]. Computer Aided Geometric Design, 2007, 24(3): 161-178.

[12] WACHSPRESS E L. Barycentric coordinates for polytopes [J]. Computers and Mathematics with Applications, 2011, 61(11): 3319-3321.

[13] GUESSAB A. Generalized barycentric coordinates and approximations of convex functions on arbitrary convex polytopes [J]. Computers and Mathematics with Applications, 2013, 66(6): 1120-1136.

[14] CHEN J J, PENG F F. Approximate spline of G2-continuity on a generalized hyperbolic paraboloid [J]. Journal of Computational and Applied Mathematics, 2013, 248(2): 99-117.

[15] PENG F F, HAN X L. Parametric splines on a hyperbolic paraboloid [J]. Journal of Computational and Applied Mathematics, 2009, 229(1): 183-191.

[16] PENG F F, CHEN J J. Spline on a generalized hyperbolic paraboloid [J]. Journal of Computational and Applied Mathematics, 2011, 235(8): 2451-2458.

Generalized Barycentric Coordinates Based on Combinatorial Optimization of Sparse Solutions

PENG Feng-fu, FANG Ming

(School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China)

According to the nature and characteristic of the linear operation of generalized barycentric coordinates, by means of a combination of weighted harmonic mean funcitons, an algorithm for solving generalized barycentric coordinates is designed to meet the demands of the vertexes of spatial convex polyhedron, in which the weighted function is a unary function with conformal parameters, thus it is characterized with conformal optimization. Two different types of weighted functions are constructed in this paper, and they are both used to calculate the generalized barycentric coordinates. An example of a plane figure is mapped into a space surface by the means, which is to be described and analyzed with different weighted functions and parameters. By means of their contours, the generalized barycentric coordinates for the example are analyzed and compared.

generalized barycentric coordinates; sparse solution; combinatorial optimization; weighted functions

TP 391

10.11996/JG.j.2095-302X.2019010054

A

2095-302X(2019)01-0054-05

2018-06-18；

2018-06-28

国家自然科学基金项目(1170119)；广西高校数据分析与计算重点实验室项目

彭丰富(1972-)，男，湖南娄底人，博士，副教授。主要研究方向为计算机辅助几何设计。E-mail：pengfengfu@aliyun.com