维基百科的 Bresenham 算法是否有错误？

Question

Bresenham's algorithm 用于在正方形网格上绘制一条线，例如像素。

该算法部分基于将平面细分为 8 个部分，称为八分圆。

诀窍是使用对称性来概括算法，而不管第二个点位于何处：首先我们 "move" 它到第一个八分圆，然后进行计算，最后转换生成的点回到原来的八分圆。

维基百科提供了一个basic function来执行这个技巧。

 function switchToOctantZeroFrom(octant, x, y) 
   switch(octant)  
     case 1: return (x, y)
     case 2: return (y, x)
     case 3: return (y, -x)
     case 4: return (-x, y)
     case 5: return (-x, -y)
     case 6: return (-y, -x)
     case 7: return (-y, x)
     case 8: return (x, -y)

此外，上面写着我们只需要：

flip the co-ordinate system on the input and output

这是基于这些换位实际上是involutions：f(f(x)) = x

没太在意，一开始以为还行。

但是对于情况3和7，它不起作用，因为它不是对合。

例如：

Case 4: (-5, 1) => (5, 1) => (-5, 1) // Good
Case 3: (-1, 5) => (5, 1) => (1, -5) // Not good

我们必须再做一次：

Case 3: (-1, 5) => (5, 1) => (1, -5) => (-5, -1) => (-1, 5) // Good

所以，我是不是误会了什么？

或者实际上维基百科上的文章起草不够精确，是否应该有人改进它？

没有更好的方法来进行这些转换，我需要使用两个函数 switchToOctant_onInput 和 switchToOctant_onOutput（我现在看到的这个问题的明显解决方案）？

Answer 1

Bresenham 算法中的八分圆讨论基于关于中线和对角线的明显轴对称。不需要对合属性。（如果你需要 f 的倒数，那么，使用... f 的倒数；但这不是明确要求的）。

一个简单的变体是线的参数方程的数字版本：

X = X0 + (k.(X1 - X0)) / D
Y = Y0 + (k.(Y1 - Y0)) / D

哪里

D = Max(|X1 - X0|, |Y1 - Y0|)

和 k 在 [0..D] 范围内。

Answer 2

八分圆 2、4、6、8 通过对合（自逆）的反射映射到八分圆 1。八分圆 5 通过 180 度旋转映射到八分圆 1，这也是对合的。然而，八分圆 7 和 3 通过非内合的 +-90 度旋转映射到八分圆 1。映射根本不是内合的，因此您无能为力。如果你想要一个反函数，你必须写它。

Wikipedia 页面具有误导性，因为它说该函数是一个 "flip"，这表明对合。

我可以想到三种方法来解决这个问题：1) 创建一个非常相似的反函数，只是交换了 3 和 7 的情况（不要重命名现有函数）； 2) 添加表示反函数的负八分圆的情况，以便 switchOctant(3,x,y) 的反函数是 switchOctant(-3,x,y) 与 switchOctant(7,x,y) 相同（但是，如果您必须仔细考虑八分圆 0做这个）;或 3) 通过增强画线功能来减少或消除对几何变换功能的需要。特别是，如果您增强画线功能以处理第一象限中的任何线（不仅仅是第一八分圆！），您可以使用几何变换将任何象限映射到第一象限是内卷。

更新

关于这个问题（可以这么说），我又想到一个 "angle"：可以通过反射将您的第 3 个八分圆映射到第 1 个八分圆。通过具有倾角 theta 的原点的线的反射由

给出

x' = x * cos(2*theta) + y * sin(2*theta)
y' = x * sin(2*theta) - y * cos(2*theta)

第一和第三八分圆之间的反射线倾斜 theta = 45 + 45/2.0 度，所以 2*theta = 135 度，我们有

x' = -sqrt(2)/2 * x + sqrt(2)/2 * y
y' =  sqrt(2)/2 * x + sqrt(2)/2 * y

可以使用类似的公式将第 7 个八分圆映射到第 1 个八分圆。因此可以找到将每个八分圆映射到第一个八分圆的对合。然而，这个映射有两个问题：1）它不是连续的，而维基百科文章中给出的映射是连续的（这意味着 (x,y) 的图像中没有随着点在平面上移动而突然跳跃）；和 2) 不清楚如何使用整数运算来影响映射。

连续性不仅仅是一个理论问题。当您考虑如何在两个八分圆之间的边界上绘制一个点时，它就变得实用了。如果你不小心处理不连续的地图，你肯定会得到不正确的结果。

所以这个想法不好，但我只是想为了完整起见而提一下。

维基百科的 Bresenham 算法是否有错误？

Is there an error in the Bresenham's algorithm from Wikipedia?

algorithm

geometry

bresenham

line-drawing