布雷森汉姆线算法错误
我有以下bresenham算法的代码，它代表适应Scala Java 代码。
def bresenham(x0: Int, y0: Int, x1: Int, y1: Int) = {
import scala.math.abs
val dx = abs(x1 - x0)
val dy = abs(y1 - y0)
val sx = if (x0 < x1) 1 else -1
val sy = if (y0 < y1) 1 else -1
new Iterator[(Int, Int)] {
var (x, y) = (x0, y0)
var err = dx - dy
def next = {
val omitted = (x, y)
val e2 = 2 * err
if (e2 > -dy) {
err -= dy
x += sx
}
if (e2 < dx) {
err += dx
y += sy
}
omitted
}
def hasNext = (x <= x1 && y <= y1)
}
}
对于几乎所有的线，一切都很好，但是当我尝试从上到下计算垂直线时（即 (0,3) -> (0,0) ），我什么也得不到.
我觉得自己很愚蠢，因为问题并不那么难，并且存在于 hasNext 中，对于上述情况，它说 不）。
我已经通过交换点来解决这个问题，但这显然是一个糟糕的解决方案。 有人可以帮我概括算法吗？
I had the following code of bresenham's algorithm which represents adapted to Scala Java code.
def bresenham(x0: Int, y0: Int, x1: Int, y1: Int) = {
import scala.math.abs
val dx = abs(x1 - x0)
val dy = abs(y1 - y0)
val sx = if (x0 < x1) 1 else -1
val sy = if (y0 < y1) 1 else -1
new Iterator[(Int, Int)] {
var (x, y) = (x0, y0)
var err = dx - dy
def next = {
val omitted = (x, y)
val e2 = 2 * err
if (e2 > -dy) {
err -= dy
x += sx
}
if (e2 < dx) {
err += dx
y += sy
}
omitted
}
def hasNext = (x <= x1 && y <= y1)
}
}
For almost all lines all goes fine, but when I'm trying to compute vertical lines from top to bottom (i.e. (0,3) -> (0,0) ) I'm getting nothing.
I feel stupid about myself, because problem is not so hard and lies in hasNext which says nope for a case above).
I've dealt with that by swapping points, but that's obviously a bad solution.
Can anybody help me to generalize algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在失败的情况下，您尝试从
y0 = 3转到y1 = 0。因此步长将为负，sy = -1。然后，在hasNext中继续的条件应取决于y >= y1而不是您编写的内容 (y <= y1)。hasNext必须泛化以处理任一方向。一个聪明的方法是，它有效，因为 sx 和 sy 不为零，并且它们的符号决定了步骤的方向。
In the failure case, you're trying to go from
y0 = 3toy1 = 0. So the step will be negative,sy = -1. The condition for continuing inhasNextshould then depend ony >= y1rather than what you wrote (y <= y1).hasNextmust be generalized to handle either direction. A clever way would be,which works because
sxandsyare nonzero, and their sign determines the direction of the steps.维基百科代码的直译是：
A rather literal translation of wikipedia code would be: