algorithm - Bresenham Integer Equation(不仅仅是算法)

Question

我正在寻找基本版本的 bresenham 线算法的方程式，如果已知 X 值，它可以让我计算 Y 值的位置。

X 始终为正且始终大于 Y。循环只是将 1 添加到 X 直到到达末尾。

这是我的代码:

int err = (Y << 1) - X;
for(i=0; i<=X; i++)
{
    if(err > 0)
    {
        step++;
        err = (err - (X << 1)) + (Y << 1);
    }
    else
    {
        err = err + (Y << 1);
    }
    printf("X=%d  Y=%d\n", i, step);
}

我正在寻找的是一种在不运行算法且仅使用整数数学的情况下计算步长(Y 轴)在特定 X 值处的值的方法。

这样做的原因是我有一个可以暂停的系统，但只返回当前的 X 值(不是 Y)，发生这种情况时我需要计算出 Y 值。

戴夫

Answer 1

我假设 step最初是 0 .从您的代码中，我们可以归纳推导出等式

step * (X << 1) + err - (i + 1) * (Y << 1) == (Y << 1) - X,

在 printf 时适用陈述。求解 step .

step == ((Y << 1) - X + (i + 1) * (Y << 1) - err) / (X << 1)

这里的划分是准确的。自 X > Y ，我们归纳地知道 -err介于 -(Y << 1) 之间包括和(X << 1) - (Y << 1)排他性的，所以我们应该加上那个范围的最大值，让 floor division 做它的事情。

step == ((Y << 1) - X + (i + 1) * (Y << 1) + (X << 1) - (Y << 1) - 1) / (X << 1),

或者，简化，

step == ((i + 1) * (Y << 1) + X - 1) / (X << 1).

我们可以得到 err 的方程式

((Y << 1) - X + (i + 1) * (Y << 1) - err) % (X << 1) == 0
err ==   ((Y << 1) - X + (i + 1) * (Y << 1) + (X << 1) - (Y << 1) - 1) % (X << 1)
       - (X << 1) + (Y << 1) + 1
err == ((i + 1) * (Y << 1) + X - 1) % (X << 1) - (X << 1) + (Y << 1) + 1