3

Bresenham 的算法用于在正方形网格上绘制一条线，例如像素。

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

八分圆

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

Wikipedia 提供了执行该技巧的基本功能。

 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)

此外，它写道，我们只需要：

翻转输入和输出的坐标系

这是基于这些换位实际上是对合的事实：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（我现在看到的这个问题的明显解决方案），就没有更好的方法来进行这些转换吗？

4

2 回答 2

2

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

维基百科页面具有误导性，因为它说该功能是“翻转”，暗示了内卷。

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

更新

我只是在这个问题上想到了一个“角度”（可以这么说）：可以通过反射将您的第三个八分圆映射到第一个八分圆。通过原点的一条线的反射，倾斜度为 theta 由下式给出

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

第 1 和第 3 八分圆之间的反射线有倾斜度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 个八分圆。因此，可以找到将每个八分圆映射到第一个八分圆的对合。(x,y)然而，这种映射有两个问题：1）它不是连续的，而维基百科文章中给出的映射是连续的（意味着当点围绕平面移动时，图像中没有突然的跳跃）；2）不清楚如何使用整数算术来影响映射。

连续性不仅仅是一个理论问题。当您考虑如何在两个八分圆之间的边界上映射一个点时，它变得很实用。如果你对不连续的地图不仔细地做这件事，你肯定会得到不正确的结果。

所以这个想法并不好，但我只是想为了完整起见我会提到它。

于 2015-07-11T15:35:40.800 回答
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]。

于 2015-07-11T10:51:43.447 回答