我有一个像素 电话 在网格上。我想知道该像素是否会出现在 bresenham 上之间生成的线P0 和 P1 没有实际生成线。这有可能提出这样的决定因素吗？
最佳答案
我正在写这个作为答案，即使它只是一个非常部分的答案。
我相信答案是肯定的。然而，编写它的证明需要一些工作，并且至少需要 TeX 支持才能被理解。相反，这里是开发证明的关键思想。
考虑一个介于 0 和 1 之间的斜率 m。这已经足够通用了，您可以通过反射获得其他三个部分。 Brensenham 的算法为您提供了一系列水平运行，每个增加 1。这些运行的长度总是 n 或 n+1，其中 n <= 1/m <= n+1。因此，您可以将 Brensenham 线视为 0 和 1 的二进制序列。这是基本的。
不太明显的是，这个序列受 m 的连分数展开式支配。考虑上述不等式中的误差项 m - 1/(n+1)。这通过用斜率 1/(n+1) 从下方逼近斜率 m 产生第一个“校正斜率”。迭代此过程以获得收敛到 m 的一系列校正斜率。很明显，这些校正斜率只是连分数序列的变换。您还可以看到上面的 0/1 序列是一组越来越大的准子周期，其层次结构是连分数展开式的另一个变换。
检查你对此的理解，这些关系的一个结果是，如果 m 是有理数，那么它的连分数展开是有限的，那么 Brensenham 序列是周期性的。
这为您提供了比谓词测试更强大的东西。您可以使用校正斜率序列来计算任意 x 坐标的 y 坐标。只需将所有校正斜率乘以 x。将足够的它们相加，直到误差界限区间(您得到交替的上下限)完全具有整数范围，即 n <= a < b < n+1。
关于geometry - 是否可以在不生成线的情况下测试像素是否在 bresenham 生成的线上？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34351372/