Is there a bug in Bresenham's algorithm from Wikipedia?
Bresenham's algorithm is used to draw a line on a square grid, for example in pixels.
The algorithm is partially based on dividing the plane into 8 parts, called octants.
The trick is to use symmetries to generalize the algorithm no matter where the second point is: first, we "move" it to the first octant, then we do the computation, and finally the generated points are converted back to their original octant.
Wikipedia provides a basic function for doing the trick.
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)
In addition, it is written that we just need:
flip the input and output coordinate system
This is based on the fact that these transpositions are actually involutions :f(f(x)) = x
Ignoring it too much, at first I thought it would work.
But for cases 3 and 7 it doesn't work because it's not involution.
For example:
Case 4: (-5, 1) => (5, 1) => (-5, 1) // Good
Case 3: (-1, 5) => (5, 1) => (1, -5) // Not good
We have to do the trick again:
Case 3: (-1, 5) => (5, 1) => (1, -5) => (-5, -1) => (-1, 5) // Good
So I misunderstood something?
Or is it actually a lack of precision in the design of the Wikipedia article and someone needs to improve it?
Isn't there a better way to make these transitions without having to use two functions switchToOctant_onInput
and switchToOctant_onOutput
(the obvious solution to this problem I see now)?
source to share
Octants 2, 4, 6, 8 are mapped to octant 1 by reflections that are involutive (self-inverse). Octant 5 is mapped to octant 1 by 180 degrees rotation, which is also involutive. However octants 7 and 3 are mapped to octane 1 with +90 degree rotation, which are not involutive. The mappings are just not involutive, so there is nothing you can do about it. If you want a reverse function, you must write it.
The Wikipedia page is misleading as it says the function is a "flip" that suggests involution.
There are three approaches I can think of to solve the problem: 1) create an inverse function that is very similar, except for cases 3 and 7 are swapped (do not rename an existing function); 2) add cases for negative octants that represent the inverse of the function, so that the inverse of switchOctant(3,x,y)
is equal switchOctant(-3,x,y)
, which is the same as switchOctant(7,x,y)
(however, you should think carefully about the octant 0 if you do); or 3) reduce or eliminate the need for a geometric transformation function by improving the line drawing function. In particular, if you improve your line drawing function to handle any line in the first quadrant (not just the first octane!), You can use a geometric transformation that maps any quadrant to the first quadrant, which is involutive.
Update
I just thought about another "corner" of this question (so to speak): you can map your third octant to the 1st octant by reflection. Reflection by a line through the origin with the slope theta is given by
x' = x * cos(2*theta) + y * sin(2*theta)
y' = x * sin(2*theta) - y * cos(2*theta)
The line of reflection between the 1st and 3rd octants has a slope of theta = 45 + 45/2.0
degrees, so 2*theta = 135
degrees, and we have
x' = -sqrt(2)/2 * x + sqrt(2)/2 * y
y' = sqrt(2)/2 * x + sqrt(2)/2 * y
Similar formulas can be used to compare the 7th octant with the 1st. Thus, one can find an involution that maps each octant to the first octant. However, there are two problems with this display: 1) it is not continuous, whereas the display given in the Wikipedia article is continuous (which means there are (x,y)
no abrupt jumps in the image when the point moves around the plane); and 2) it is not clear how to use integer arithmetic to perform the mapping.
Continuity is not just a theoretical issue. This becomes practical when you consider how you are going to display a point on the border between two octants. If you don't do this very carefully with the intermittent card, you will definitely get incorrect results.
So this idea is not a good idea, but I just thought I mentioned it for the sake of completeness.
source to share
The discussion of octants in Bresenham's algorithm is based on obvious axial symmetries about medians and diagonals. The property of involution is not required. (If you want the inverse to f
, well, use ... inversion f
, but that is clearly not required).
A simple option is a digital version of the parametric line equation:
X = X0 + (k.(X1 - X0)) / D
Y = Y0 + (k.(Y1 - Y0)) / D
Where
D = Max(|X1 - X0|, |Y1 - Y0|)
and k
in the range [0..D]
.
source to share