algorithm - 有什么公式可以在没有循环的情况下在 Bresenham 的 2D 线中获得点？

Question

假设我们有 (x1,y1) 和 (x2,y2) 可能很远

我们可以计算与 (x1,y1) 有 N 距离的直线上的点吗？

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

*注意：不能使用浮点数

标签： algorithmmathgraphics2ddeterministic

Answer 1

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

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

如果您不能使用浮点数，那么您可能需要使用地板除法。您可以像这样进行舍入：

y(x) = y1 + floor( ( 2(x-x1)(y2-y1) + (x2-x1) ) / 2(x2-x1) )

Bresenham 算法的重点是逐步计算这个公式，以避免乘法和除法，这在当时比现在通常要昂贵得多。

注意：我假设您想要沿 x 或 y 的距离，因为您想要剪裁线。如果您真的想要欧几里德距离，请参阅@Beta 答案