重心坐标三角点试验的数值稳定性 [英] 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屋！