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

Question

在查看三角点测试的各种方法（2D 案例）时，我发现使用重心坐标的方法是最常用的一种。 Here 是解释它的 Whosebug 答案。

为什么这种方法是最受欢迎的方法？这可能与减少计算有关，但数值稳定性呢？对于点特别靠近边界的情况，该算法是否比 "same side" 技术更适合？

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  |
------------------------------------------------------------------

这里还有更多轴顺序、点顺序选项，以便可以计算逆矩阵。如果您对逆矩阵解使用次行列式方法，那么唯一重要的是最后的除法步骤。所以您可以选择顺序，直到您有非零行列式。

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

Numerical stability of point-in-triangle test with barycentric coordinates

language-agnostic

algorithm

math

geometry

numeric