比较两个角度

Question

给定平面中的四个点，A,B,X,Y，我希望确定以下两个角度哪个更小：∢ABX 或 ∢ABY。

角度∢ABX被定义为当AB被平移到开放线段(-∞,0]上时，BX的角度。 直观地说，当说∢ABX时，我指的是在访问顶点B后左转得到的角度。

为了保持准确性并最大化性能（代码将在嵌入式系统上运行），我宁愿不使用cos或sqrt。

在A=(-1,0),B=(0,0)的情况下，我可以通过计算矢量X,Y的点积并观察其符号来比较两个角度∢ABX和∢ABY。

在这种情况下，我可以做：

1. 确定 ABX 是左转还是右转。
2. 如果 ABX 左转，则检查点 Y 和 A 是否在线段 BX 的同一侧。如果它们在同一侧，则 ∢ABX 小于 ABY。
3. 如果 ABX 右转，那么 Y 和 A 在 BX 的同一侧意味着 ∢ABX 大于 ∢ABY。

但这对我来说似乎太复杂了。

有简单些的方法吗？

- Elazar Leibovich

---

请注意，仅在您的位置已经完全确定（例如表示为整数或有理数）时，保持准确性才有意义。但是，避免平方根还有其他合法的原因，即性能。 - user168715

Answer 1

以下是一些伪代码。它不能检测两个角度相等的情况。也不能处理角度方向，例如假定所有角度都小于等于180度。

v0 = A-B
v1 = X-B
v2 = Y-B

dot1 = dot(v0, v1)
dot2 = dot(v0, v2)

if(dot1 > 0)
  if(dot2 < 0)
    // ABX is smaller
  if(dot1 * dot1 / dot(v1,v1) > dot2 * dot2 / dot(v2, v2) )
    // ABX is smaller
  // ABY is smaller

if(dot2 > 0)
  // ABY is smaller
if(dot1 * dot1 / dot(v1,v1) > dot2 * dot2 / dot(v2,v2) )
  // ABY is smaller
// ABX is smaller

请注意，如果您允许进行两次平方根运算，那么大部分这种痛苦的情况都会消失。

- user168715

Answer 2

通过以下操作将原点定位于B的中心

X = X - B
Y = Y - B
A = A - B

编辑：您还需要对这3个向量进行归一化处理。

A = A / |A|
X = X / |X|
Y = Y / |Y|

通过以下方式找到两个角度

acos(A dot X)
acos(A dot Y)

===

我不明白精度损失的意义。您只是在比较，而没有以任何方式修改点的坐标...

- nico

---

你假设A和X的大小为1（或者它们互为倒数）。同样，A和Y也是如此。 - Justin Peel

Answer 3

你可能想查看有理三角学。距离和角度的概念被四面体积和扩散所代替，不涉及sqrt和cos。请查看该网页底部，了解如何计算两条线之间的扩散。该主题有自己的网站，甚至还有YouTube频道。

- brainjam

Answer 4

我宁愿不使用cos或sqrt，以保持准确性。

这根本没有任何意义。

但是对我来说，这似乎太复杂了。

对我来说，这似乎完全是错误的想法。

取两个向量之间的差异并查看分量的符号。

你需要小心的是“更小”的含义。如所述，这个想法并不是非常精确。例如，如果一个点A在第四象限（x分量> 0且y分量< 0），另一个点B在第一象限（x分量> 0且y分量> 0），那么“更小”是什么意思？从原点到A的向量的角度在零和π/2之间；从原点到B的向量的角度在3π/4和2π之间。哪一个是“更小”的？

- duffymo

---

这是一个很好的观点。角度∢ABX被定义为当AB被平移到开放线段(-∞,0]上时，BX的角度。直观地说，我指的是在访问顶点B后向左转的角度ABX。 - Elazar Leibovich

Cos是一种近似，因此除了这些操作的高成本外，还会失去一些精度。此外，他只需要单调函数而不是值本身。 - wondra

Answer 5

使用余弦定理：a ** 2 + b ** 2 - 2 * a * b * cos(phi) = c ** 2 其中，a = |ax|，b = |bx|（|by|），c = |ab|（|ay|），phi 是 ABX（ABY）的角度。

- sizzzzlerz

---

你如何在不使用sqrt的情况下获取这些距离？ - user168715

"无平方根"的想法必须被摒弃。 - duffymo

你不需要使用sqrt函数。你可以比较cos(phi1)和cos(phi2)，其中较大的一个是较大的角度。 - sizzzzlerz

真的吗？那么你如何处理 x = 0 处的不连续性呢？ - duffymo

你需要使用sqrt函数来计算2*a*b这一项（这是解决cos(phi)的必要步骤）。此外，cos(phi1)和cos(phi2)中较大的值将对应于更小的角度。 - Peter Milley

Answer 6

我不确定你是否可以不使用sqrt。

AB = A-B/|A-B|
XB = X-B/|X-B|
YB = Y-B/|Y-B|

if(dot(XB,AB) > dot (YB,AB)){
 //<ABY is grater
}
else
{
...
}

- Yogi

---

我在问题中描述了一种不使用平方根的方法。我很乐意听听为什么我的方法行不通。 - Elazar Leibovich