首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >数值稳定角平分线算法

数值稳定角平分线算法
EN

Stack Overflow用户
提问于 2017-04-16 07:57:17
回答 5查看 1.5K关注 0票数 5

有数值稳定的角平分线算法吗?

问题如下:

  • 给定三个向量(二维) A,B,C
  • 找出B角的平分线( AB和BC之间的夹角)

实际上,我计算它的方式如下:

  • 规范化AB
  • 规范BC
  • 查找(AB+CD)/2f (中点)
  • 平分线是B和中间点之间的一条线。

我的方法的问题是,当夹角接近180°(AB几乎平行于BC)时,平分线非常不准确(当然,因为中点几乎与B重合)。目前的算法是如此不准确,有时得到的平分线几乎平行于其他两个段中的一个。

是的,没有“转换”问题,所有的计算都是用单精度浮点进行的。

EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2020-04-19 16:11:19

这可不是小事。假设两个边向量是a和b:

代码语言:javascript
代码运行次数:0
运行
复制
float2 a = A - B;
float2 b = C - B;
  1. 计算点积float dp = dot( a, b )
  2. 将两个向量标准化:
代码语言:javascript
代码运行次数:0
运行
复制
float2 a_norm = normalize( a );
float2 b_norm = normalize( b );
  1. 检查点产品的符号位。当dp是非负值时,return normalize( a_norm + b_norm );和您就完成了.
  2. 当点积为负值时,输入向量之间存在钝角。在这种情况下应用天真的公式会破坏数值的精度。需要另一个方法。
代码语言:javascript
代码运行次数:0
运行
复制
float2 c = normalize( a_norm - b_norm );
float dir = dot( a, rotate90( b ) );
return ( dir < 0 ) ? rotate90( c ) : rotate270( c );

注意,-而不是+,这才是精确取胜的原因。当ab的夹角大于90°时,a-b的夹角小于90°,a_norm - b_norm的长度足以给出精确的方向。我们只需要把它旋转90度,然后,在正确的方向。

将二维矢量按90°倍数旋转是无损运算。下面是rotate90和rotate270函数的伪代码:

代码语言:javascript
代码运行次数:0
运行
复制
float2 rotate90( float2 vec )
{
    return float2( vec.y, -vec.x );
}
float2 rotate270( float2 vec )
{
    return float2( -vec.y, vec.x );
}
票数 2
EN

Stack Overflow用户

发布于 2017-04-16 10:23:21

如果你把BA旋转+90°,BC旋转-90°,你可以使用角度平分线保持不变。

所以,如果情况稳定,即BA和BC的点积是正的,就使用原来的公式。

如果为负值,则对BA (x,y) -> (-y,x)BC (x,y) -> (y,-x)应用旋转,这也会使点乘积变为正。像以前一样处理新的向量。

如果你尝试这一点,你会注意到,在向量之间的角-90°中,现在发生了平分线方向的跳跃。这是不可能避免这种跳转,因为一个连续的平分线将只有在两个回合后(固定BA和移动C)相同。

票数 3
EN

Stack Overflow用户

发布于 2017-04-16 09:36:30

您可以很简单地通过以下方法找到二分法向量:

代码语言:javascript
代码运行次数:0
运行
复制
∥BC∥ * BA + ∥BA∥ * BC

但是,在ABC共线或接近共线的情况下,这在数值上也不会稳定。更好的方法是通过点积找到AB和BC之间的夹角。

代码语言:javascript
代码运行次数:0
运行
复制
cos θ = (BA · BC) / (∥BC∥ * ∥BA∥)

即使在共线情况下也会产生正确的角度。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/43435055

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档