bresenham's line algorithm error
Question
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?
Solution
In the failure case, you're trying to go from y0 = 3
to y1 = 0
. So the step will be negative, sy = -1
. The condition for continuing in hasNext
should then depend on y >= y1
rather than what you wrote (y <= y1
).
hasNext
must be generalized to handle either direction. A clever way would be,
def hasNext = (sx*x <= sx*x1 && sy*y <= sy*y1)
which works because sx
and sy
are nonzero, and their sign determines the direction of the steps.
OTHER TIPS
A rather literal translation of wikipedia code would be:
def hasNext = (!(x==x1 && y==y1))