c - 嵌入式处理器的快速斜边算法？

Question

是否有一种聪明/高效的算法来确定角度的斜边(即 sqrt(a² + b²))，在嵌入式处理器上使用定点数学而不使用硬件乘法？

Answer 1

如果结果不必特别准确，你可以得到一个粗略的近似值非常简单:

取 a 的绝对值和 b , 并在必要时进行交换，这样你就有了 a <= b .然后:

h = ((sqrt(2) - 1) * a) + b

要直观地了解其工作原理，请考虑在像素显示器上绘制浅斜线的方式(例如使用 Bresenham 算法)。它看起来像这样:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |*|*|*|    ^
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    |
| | | | | | | | | | | | |*|*|*|*| | | |    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    |
| | | | | | | | |*|*|*|*| | | | | | | | a pixels
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    |
| | | | |*|*|*|*| | | | | | | | | | | |    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    |
|*|*|*|*| | | | | | | | | | | | | | | |    v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 <-------------- b pixels ----------->

对于 b 中的每一步方向，要绘制的下一个像素要么紧靠右侧，要么在右侧向上一个像素。

从一端到另一端的理想线可以近似为连接每个像素中心到相邻像素中心的路径。这是一系列 a长度段 sqrt(2) , 和 b-a长度为1的段(以像素为度量单位)。因此，上面的公式。

这清楚地给出了 a == 0 的准确答案和 a == b ;但高估了两者之间的值。

误差取决于比例b/a ; b = (1 + sqrt(2)) * a 时出现最大错误结果是 2/sqrt(2+sqrt(2)) , 或比真实值高出约 8.24%。这不是很好，但如果它对您的应用程序来说足够好，这种方法的优点是简单和快速。 (与常数的乘法可以写成一系列移位和加法。)