数值稳定的角平分线算法

Question

有没有稳定的角平分线算法？

问题如下：

给定三个向量（二维）A，B，C

找到角度B的平分线（AB和BC之间的角度）

实际上，我是按照以下方式计算的：

1. 标准化AB 2. 标准化BC 3. 找到（AB + CD）/ 2f（中点） 4. 平分线是通过B和中点之间的线。

我的方法的问题在于，当角度接近180°时（AB几乎与BC平行），平分线非常不准确（当然是因为中点几乎与B重合）。当前的算法非常不准确，有时得到的平分线几乎与其他两条线段之一平行。

是的，没有“强制转换”问题，所有计算都以单精度浮点数进行。

- CoffeDeveloper

---

提示：尝试使用指南针和直尺构建平分线。假装你丢失了眼镜，无法区分非常接近的点。 - n. m.

我已经在做这件事情啦 ^^. 我使用的算法涉及到两个单元圆，最终我想知道如何使其在数值上更稳定，或者提供一个替代稳定版本。 - CoffeDeveloper

纸/罗盘算法需要两个相同长度的向量。如果我让它们更长，当起始向量较短时，问题仍然存在。 - CoffeDeveloper

“这正是我已经在做的。”你正在(1)连接两个点，(2)找到所得线段的中点，(3)通过中点和另一个可能非常靠近它的点画一条直线。一个角平分线可以用更简单的方法构建。不要从(1)开始。 - n. m.

“当起始向量较短时，问题仍然存在。” 在解决问题之前，您可以根据需要缩放构造。浮点数非常适合这样做。问题在于两个非常接近的数字相减会出现问题。 - n. m.

Answer 1

你可以使用这个方法，通过将向量BA旋转+90°和BC旋转-90°来保持角平分线不变。

因此，在稳定的情况下，即BA和BC的点积为正数时，请使用原始公式。

如果它是负数，则应用旋转，对于BA (x，y) -> (-y，x)和 BC （x，y） ->（y，-x），这也使得点积为正数。继续使用新向量进行操作。

如果您尝试这样做，您会注意到平分线方向的跳跃现在发生在向量之间的-90°角度处。无法避免这种跳跃，因为连续的平分线只有在两次转动后才能相同（固定BA并移动C）。

- Lutz Lehmann

Answer 2

这并不是微不足道的。假设有两个边向量a和b:

float2 a = A - B;
float2 b = C - B;

1. 计算点积：float dp = dot( a, b )

2. 归一化两个向量：

float2 a_norm = normalize( a );
float2 b_norm = normalize( b );

3. 检查点积的符号位。当dp为非负时，return normalize( a_norm + b_norm );，然后你就完成了。

4. 当点积为负数时，输入向量之间的角度是钝角。在这种情况下应用天真的公式会破坏数值精度。需要另一种方法。

float2 c = normalize( a_norm - b_norm );
float dir = dot( a, rotate90( b ) );
return ( dir < 0 ) ? rotate90( c ) : rotate270( c );

注意使用减号（-）而非加号（+），这是提高精度的关键。当向量a和向量b之间的夹角大于90°时，向量a和向量-b之间的夹角小于90°，同时向量a_norm - b_norm的长度足够大以提供精确的方向。我们只需要将其正确旋转90°即可。

附注：将2D向量旋转多个90°是无损操作。以下是rotate90和rotate270函数的伪代码：

float2 rotate90( float2 vec )
{
    return float2( vec.y, -vec.x );
}
float2 rotate270( float2 vec )
{
    return float2( -vec.y, vec.x );
}

- Soonts

---

谢谢。终于有一个稳定的算法了。 - CoffeDeveloper

@CoffeDeveloper 看到了更新，我又错误地进行了两次归一化。现在已经修复了。 - Soonts

Answer 3

有一个相当简单的方法可以用两种格式来实现（但内容是完全相同的）：

伪代码

// Move A and C to the origin for easier rotation calculations
Aprime=A-B;
Cprime=C-B;
// The counter-clockwise angle between the positive X axis to A'
angle_a = arctan(Aprime.y, Aprimet.x);
// ditto for C'
angle_c = arctan(Cprime.y, Cprime.x);
// The counter-clockwise angle from A' to C'
angle_ac = angle_c - angle_a;
// The counter-clockwise angle from the positive X axis to M'
angle_m = angle_ac/2 + angle_a;
// Construct M' which, like A' and C', is relative to the origin.
Mprime=(cos(angle_m), sin(angle_m));
// Construct M which is relative to B rather than relative to the origin.
M=Mprime+B

In Chinese

1. 通过以下公式将向量移动到原点
   • A'=A-B
   • B'=B
   • C'=C-B
2. 计算从正X轴到 A' 的角度为 angle_a = arctan(A_y, A_x)。
3. 计算从正X轴到 C' 的角度为 angle_c = arctan(C_y, C_x)。
4. 计算从 A' 到 C' 的逆时针角度为 angle_ac = angle_c - angle_a。
5. 计算从正X轴到 M' 的角度为 angle_m = angle_ac/2 + angle_a。
6. 使用该角度构建 M'，公式为 M' = (cos(angle_m), sin(angle_m))。
7. 使用公式 M = M' + B 构建 M。

向量 BM 二分角度 ABC。

由于存在任意划分，因此使用这种方法没有困难。以下是一个绘图计算器，以鼓励对解决方案的直觉理解：https://www.desmos.com/calculator/xwbno717da

- lmat - Reinstate Monica

Answer 4

你可以很简单地找到二分向量：

∥BC∥ * BA + ∥BA∥ * BC

但是如果ABC共线或接近共线，这也不会保持数值稳定。更好的方法可能是通过点积找到AB和BC之间的角度。

cos θ = (BA · BC) / (∥BC∥ * ∥BA∥)

即使在共线的情况下，这将产生正确的角度。

- TrentP

---

这是一个非常简洁的答案，但我不太确定我理解了。 |BC| 是向量 C-B 的长度，但 AB 是什么？那是从 A 到 B (B-A) 的向量吗？ - lmat - Reinstate Monica

最初的问题在术语上有些不准确，在其他答案中得到了解决。A、B、C 可以被视为点，其中 AB 表示从点 A 到点 B 的向量。 - TrentP

我看到问题了，第一个向量应该是BA。问题是要找到角平分线，所以这两个向量必须有一个共同的中点，在这种情况下是B。 - TrentP

所以，如果我们遵循数学计算，∥BC∥ * BA = (0.4, 0) 和 ∥BA∥ * BC = (0, 0.4)，它们的和是(0.4, 0.4)。从 B 到 (0.4, 0.4) 的向量将平分角度。而且确实如此，因为角度显然是90°，平分线明显是45°。 - TrentP

感谢您更新答案，现在更好了！ - lmat - Reinstate Monica

Answer 5

定义：如果A和B是点，则向量(A,B)是从点A到B的向量。

假设点O是我们坐标系的原点。

点A的坐标与半径向量(O,A)相同。

让点M成为角平分线的中点，因此需要：

-归一化向量(B,A)

-归一化向量(B,C)

-向量(B,M)=向量(B,A)+向量(B,C)//从B到中点的向量

-(可选)您可以将向量(B,M)乘以标量来获得更长的向量/增加B和M之间的距离

-向量(O,M)=向量(O,B)+向量(B,M)//从O到M的半径向量

现在中点M具有与半径向量(O,M)相同的坐标。

- JPX