重心坐标三角形点检验的数值稳定性

Question

在研究三角形点测试（2D 情况）的各种方法时，我发现使用重心坐标的方法是最常用的一种。这是 StackOverflow 的答案，对此进行了解释。

为什么这种方法是最优选的方法？这可能与计算量减少有关，但是数值稳定性呢？对于点特别靠近边界的情况，该算法是否比“同边”技术更适合？

Answer 1

如果你解决了：

p = p0 + (p1 - p0) * s + (p2 - p0) * t
s = <0.0,1.0>
t = <0.0,1.0>
s+t<=1.0

解决该系统时：

p.a = p0.a + (p1.a - p0.a) * s + (p2.a - p0.a) * t
p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t
----------------------------------------------------

你有两个代数选项：

I.  t = (p.a - p0.a - (p1.a - p0.a) * s) / (p2.a - p0.a)
II. p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t
----------------------------------------------------
II. p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * (p.a - p0.a - (p1.a - p0.a) * s) / (p2.a - p0.a)
II. s = (p.b-p0.b) / ( (p1.b-p0.b) + ( (p2.b-p0.b)*(p.a-p0.a-(p1.a-p0.a)/(p2.a-p0.a) ) )
...

和：

I.  s = (p.a - p0.a - (p2.a - p0.a) * t) / (p1.a - p0.a)
II. p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t
----------------------------------------------------
...

这为您提供了 2 个代数解决方案选项。为了确保稳定性，您应该以足够大的幅度进行除法。因此，您应该选择轴 ( a,b-> x,y) 和点顺序，这样您就不会除以零或小数值。

为了避免这种情况，您可以使用矩阵方法

p.a = p0.a + (p1.a - p0.a) * s + (p2.a - p0.a) * t
p.b = p0.b + (p1.b - p0.b) * s + (p2.b - p0.b) * t
--------------------------------------------------
|p.a|   | (p1.a - p0.a) , (p2.a - p0.a) , p0.a |   | s |
|p.b| = | (p1.b - p0.b) , (p2.b - p0.b) , p0.b | * | t |
| 1 |   |       0       ,       0     ,     1  |   | 1 |
--------------------------------------------------------
| s |           | (p1.a - p0.a) , (p2.a - p0.a) , p0.a |   | p.a |
| t | = inverse | (p1.b - p0.b) , (p2.b - p0.b) , p0.b | * | p.b |
| 1 |           |       0       ,       0       ,   1  |   |  1  |
------------------------------------------------------------------

此外，在这里您还可以选择更多的轴顺序、点顺序选项，以便可以计算逆矩阵。如果您使用子行列式方法来求解逆矩阵，那么唯一重要的是最后的除法步骤。因此，您可以选择顺序，直到获得非零行列式。