重心坐标的三角点试验的数值稳定性 [英] Numerical stability of point-in-triangle test with barycentric coordinates

问题描述

在研究各种用于三角测试的方法(2D情况)时，我发现使用重心坐标的方法是最常用的方法.此处是解释它的StackOverflow答案.

While looking at various methods for point-in-triangle testing (2D case), I found that the method which uses barycentric coordinates is the most used one. Here is a StackOverflow answer which explains it.

为什么此方法是最优选的方法?它可能与减少计算量有关，但是数值稳定性呢?对于点特别靠近边界的情况，此算法是否比说同侧"技术更合适?

Why is this method the most preferred one? It probably has to do with doing less calculations, but what about numerical stability? Is this algorithm better suited than say, the "same side" technique, for cases in which the point is particularly near the border?

推荐答案

如果解决了此问题:

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 )和点顺序，以免被零或较小的数量级所除.

Which gives you 2 algebraic solution options. To ensure stability you should divide with big enough magnitudes. So you should choose the axises (a,b -> x,y) , and point order so you are not dividing by zero or small magnitude numbers.

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

To avoid this you can use matrix approach

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

在这里，您还可以选择轴顺序，点顺序的更多选项，以便可以计算逆矩阵.如果将子行列式方法用于逆矩阵解，则唯一重要的是最后的除法步骤.因此，您可以选择顺序，直到行列式为非零为止.

Also here you got more options for axises order, point order so that the inverse matrix is computable. If you use sub-determinant approach for inverse matrix solution then the only thing that should matter is the final division step. So you can choose the orders until you have nonzero determinant.

这篇关于重心坐标的三角点试验的数值稳定性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！