直线上的重心坐标
给定两点A与B,可以定义由直线AB到$\{(b_1,b_2)\in\mathbb{R}^2\mid b_1+b_2=1\}$的双射$b_1=\dfrac{x_P-x_B}{x_A-x_B},b_2=\dfrac{x_A-x_P}{x_A-x_B}$,称为重心坐标,则有$x_P=b_1x_A+b_2x_B$.特别地,A的坐标是(1,0),B的坐标是(0,1).它的物理意义是:在A处放置质量为$b_1$的质点,在B处放置质量为$b_2$的质点,力矩平衡点为P.
三角形重心坐标
对于$\triangle ABC$,可以定义由平面ABC到$\{(b_1,b_2,b_3)\in\mathbb{R}^3\mid b_1+b_2+b_3=1\}$的双射.
设$v=\overrightarrow{OP},v_1=\overrightarrow{OA},v_2=\overrightarrow{OB},v_3=\overrightarrow{OC},$由$b_1v_1+b_2v_2+b_3v_3=v$解得$b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i =\begin{vmatrix}x&y&1\\x_{i-1}&y_{i-1}&1\\x_{i+1}&y_{i+1}&1\end{vmatrix},i=1,2,3$
即$b_1=\dfrac{S_{\triangle PBC}}{S_{\triangle ABC}},b_2=\dfrac{S_{\triangle PCA}}{S_{\triangle ABC}},b_3=\dfrac{S_{\triangle PAB}}{S_{\triangle ABC}}$.
事实上,满足$f(A)=(1,0,0),f(B)=(0,1,0),f(C)=(0,0,1)$的线性函数$f:$平面$ABC\to\mathbb{R}^3$只有重心坐标.
第一种推广
Wachspress坐标(瓦赫斯普雷斯坐标)对任何凸n边形有定义.它保持了三角形重心坐标除了正定性以外的所有性质. $b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i = \dfrac{C_i}{A_{i-1}A_i}=\dfrac{\cot{\angle vv_iv_{i+1}}+\cot{\angle vv_iv_{i-1}}}{|vv_i|^2}$,i=1…n
对于接近n边形的边界的点,分母变得接近0,导致公式不稳定,为此,将$w_i$改成$\bar{w}_i ,\bar{w}_i = C_i\prod\limits_{j\not=i-1,i} A_j$
实际上,修改后时间复杂度由$o(n)$变为$o(n^2)$.但在数学上这种修改并不改变坐标.
使分母${\sum_{j=1}^n w_j}=0$的点的集合是一条经过边的延长线的交点的曲线,这种点共有$\dfrac12n(n-3)$个. 第二种推广
离散调和坐标也是对任何凸n边形有定义.它保持了三角形重心坐标除了正定性以外的所有性质,事实上,$w_i>0\iff\alpha+\beta<\pi$.一个有趣的特性是,对于圆内接多边形,它与 Wachspress坐标相等. $b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i = \dfrac{r_{i+1}^2A_{i-1}-r_i^2B_i+r_{i-1}^2A_i}{A_{i-1}A_i}$,i=1…n.
对于接近n边形的边界的点,公式变得不稳定,为此,与上一小节类似,将$w_i$改成$\bar{w}_i ,\bar{w}_i = (r_{i+1}^2A_{i-1}-r_i^2B_i+r_{i-1}^2A_i)\prod\limits_{j\not=i-1,i} A_j$
实际上,修改后时间复杂度由$o(n)$变为$o(n^2)$.但在数学上这种修改并不改变坐标.
第三种推广
与前述两种推广不同,中值坐标对任何简单n边形有定义.它保持了三角形重心坐标除了正定性以外的所有性质,事实上,它对于多边形的核之外的点可能取负值(多边形的核为图中红色区域.定义见星形域).
对于这些坐标,我们还有两个算法: 一个是精确的,一个是快速的.
精确方法对平面的任何点有效但它的计算步骤包含开平方运算.这个算法是基于下面的权重公式$b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i = \sigma_i\bar{w}_i,|\bar{w}_i |= (r_{i-1}r_{i+1}-d_{i-1}d_{i+1})^{1/2}\prod\limits_{j\not= i-1,i}(r_jr_{j+1} + d_jd_{j+1})^{1/2}, r_i = \|d_i\|.$
其中$\bar w_i$在褐色折线的左边总是取正值,在它的右边总是取负值,以逆时针方向移动.
快速方法不包含开平方运算但是当接近多边形的边时变得不稳定.
$w_i = \dfrac{t_{i-1} + t_i}{r_i},t_i = \dfrac{\text{det}(d_i, d_{i+1})}{r_ir_{i+1} + d_id_{i+1}}$
三角形内部的点的重心坐标是3个介于0与1之间的数,将它们乘以255作为RGB值,这样一来,重心坐标可以给三角形着色,称为Gouraud shading.
若只绘制一个坐标,得到是线性着色:
对于多边形,只绘制一个坐标,得到等值线如下:
有趣的事实:这三种坐标系都属于同一个广义重心坐标系,称为三点坐标系
参考资料
给定两点A与B,可以定义由直线AB到$\{(b_1,b_2)\in\mathbb{R}^2\mid b_1+b_2=1\}$的双射$b_1=\dfrac{x_P-x_B}{x_A-x_B},b_2=\dfrac{x_A-x_P}{x_A-x_B}$,称为重心坐标,则有$x_P=b_1x_A+b_2x_B$.特别地,A的坐标是(1,0),B的坐标是(0,1).它的物理意义是:在A处放置质量为$b_1$的质点,在B处放置质量为$b_2$的质点,力矩平衡点为P.
三角形重心坐标
对于$\triangle ABC$,可以定义由平面ABC到$\{(b_1,b_2,b_3)\in\mathbb{R}^3\mid b_1+b_2+b_3=1\}$的双射.
设$v=\overrightarrow{OP},v_1=\overrightarrow{OA},v_2=\overrightarrow{OB},v_3=\overrightarrow{OC},$由$b_1v_1+b_2v_2+b_3v_3=v$解得$b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i =\begin{vmatrix}x&y&1\\x_{i-1}&y_{i-1}&1\\x_{i+1}&y_{i+1}&1\end{vmatrix},i=1,2,3$
即$b_1=\dfrac{S_{\triangle PBC}}{S_{\triangle ABC}},b_2=\dfrac{S_{\triangle PCA}}{S_{\triangle ABC}},b_3=\dfrac{S_{\triangle PAB}}{S_{\triangle ABC}}$.
事实上,满足$f(A)=(1,0,0),f(B)=(0,1,0),f(C)=(0,0,1)$的线性函数$f:$平面$ABC\to\mathbb{R}^3$只有重心坐标.
第一种推广
Wachspress坐标(瓦赫斯普雷斯坐标)对任何凸n边形有定义.它保持了三角形重心坐标除了正定性以外的所有性质. $b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i = \dfrac{C_i}{A_{i-1}A_i}=\dfrac{\cot{\angle vv_iv_{i+1}}+\cot{\angle vv_iv_{i-1}}}{|vv_i|^2}$,i=1…n
对于接近n边形的边界的点,分母变得接近0,导致公式不稳定,为此,将$w_i$改成$\bar{w}_i ,\bar{w}_i = C_i\prod\limits_{j\not=i-1,i} A_j$
实际上,修改后时间复杂度由$o(n)$变为$o(n^2)$.但在数学上这种修改并不改变坐标.
使分母${\sum_{j=1}^n w_j}=0$的点的集合是一条经过边的延长线的交点的曲线,这种点共有$\dfrac12n(n-3)$个. 第二种推广
离散调和坐标也是对任何凸n边形有定义.它保持了三角形重心坐标除了正定性以外的所有性质,事实上,$w_i>0\iff\alpha+\beta<\pi$.一个有趣的特性是,对于圆内接多边形,它与 Wachspress坐标相等. $b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i = \dfrac{r_{i+1}^2A_{i-1}-r_i^2B_i+r_{i-1}^2A_i}{A_{i-1}A_i}$,i=1…n.
对于接近n边形的边界的点,公式变得不稳定,为此,与上一小节类似,将$w_i$改成$\bar{w}_i ,\bar{w}_i = (r_{i+1}^2A_{i-1}-r_i^2B_i+r_{i-1}^2A_i)\prod\limits_{j\not=i-1,i} A_j$
实际上,修改后时间复杂度由$o(n)$变为$o(n^2)$.但在数学上这种修改并不改变坐标.
第三种推广
与前述两种推广不同,中值坐标对任何简单n边形有定义.它保持了三角形重心坐标除了正定性以外的所有性质,事实上,它对于多边形的核之外的点可能取负值(多边形的核为图中红色区域.定义见星形域).
对于这些坐标,我们还有两个算法: 一个是精确的,一个是快速的.
精确方法对平面的任何点有效但它的计算步骤包含开平方运算.这个算法是基于下面的权重公式$b_i = \dfrac{w_i}{\sum_{j=1}^n w_j},w_i = \sigma_i\bar{w}_i,|\bar{w}_i |= (r_{i-1}r_{i+1}-d_{i-1}d_{i+1})^{1/2}\prod\limits_{j\not= i-1,i}(r_jr_{j+1} + d_jd_{j+1})^{1/2}, r_i = \|d_i\|.$
其中$\bar w_i$在褐色折线的左边总是取正值,在它的右边总是取负值,以逆时针方向移动.
快速方法不包含开平方运算但是当接近多边形的边时变得不稳定.
$w_i = \dfrac{t_{i-1} + t_i}{r_i},t_i = \dfrac{\text{det}(d_i, d_{i+1})}{r_ir_{i+1} + d_id_{i+1}}$
三角形内部的点的重心坐标是3个介于0与1之间的数,将它们乘以255作为RGB值,这样一来,重心坐标可以给三角形着色,称为Gouraud shading.
若只绘制一个坐标,得到是线性着色:
对于多边形,只绘制一个坐标,得到等值线如下:
| Wachspress 坐标 | 离散调和坐标 | 中值坐标 |
|
|
|
参考资料
PREVIOUSTheory of majorization