有什么公式可以在布雷森汉姆的 2D 线中无循环获得点？

Question

假设我们有(x1，y1(和(x2，y2(，它们可能很远

我们可以计算出距离 (x1，y1( 有 N 个距离的直线点吗？

我的简单想法是在 for 循环中添加计数，但如果距离非常大，这将很昂贵

*注意：浮点不能使用

Answer 1

A = (x 1， y₁(B = (x 2， y₂(

C = B - A = (x 2 - x 1， y 2- y₁(= (x c， y_c(C
²= C .C = x c²+ y_c²
|C|= sqrt(C²(
k = C/|C|= (x_c/|C|， y_c/|C|(

您要查找的点是 D = A + Nk

Answer 2

在第一个八进制 (0 <= y2-y1 <= x2-x1( 中，公式为：

y(x( = y1 + round( (x-x1((y2-y1(/(x2-x1( (

如果不能使用浮点运算，那么可能需要用户进行地板划分。 您可以像这样进行舍入：

y(x( = y1 + 地板( ( 2(x-x1((y2-y1( + (x2-x1((/2(x2-x1( (

布雷森纳姆算法的全部意义在于逐步计算这个公式，以避免乘法和除法，当时的乘法和除法比现在要贵得多。

注意：我假设您想要沿 x 或 y 的距离，因为您想裁剪线。 如果你真的想要欧几里得距离，那么看看@Beta答案

Answer 3

我遇到了同样的问题，Bresenham 的算法正在绘制一条漂亮的线，但我只是无法在不遍历坐标的情况下选择任何点，因为它的性质，为了避免舍入和其他"故障"，它决定即时放置一个像素，这在渲染过程中非常方便，但它使几何计算非常昂贵(例如线交叉/相交查找(。

我也不能使用浮点类型，因为我现在正在开发没有 FPU 的 MCU，但我项目中的以下代码运行良好，速度非常快，而且我还没有注意到任何错误。

inline static int16_t GetYOfLineAtX(int16_t x0, int16_t y0, int16_t x1, int16_t y1, int16_t x) {
return (y1 - y0) * (x - x0) / (x1 - x0) + y0;
}
inline static int16_t GetXOfLineAtY(int16_t x0, int16_t y0, int16_t x1, int16_t y1, int16_t y) {
return (x1 - x0) * (y - y0) / (y1 - y0) + x0;
}

很简单：x0, y0是直线起点，x1, y1是终点(斜率可能是负的或正的，方向无关紧要(，两个函数上的x或y参数是必需的坐标，它返回另一个轴值。