3

Bresenham's algorithm is used to draw a line on a square grid as are pixels for example.

The algorithm is partly based on the subdivision of the plane into 8 parts called octants.

Octants

The trick is to use symmetries to generalize the algorithm regardless of where the second point is located: firstly we "move" it to the first octant, then the calculations are made, and finally the generated points are converted back to their original octant.

Wikipedia provides a basic function to perform 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)

Moreover, it is written that we just have to:

flip the co-ordinate system on the input and output

This is based on the fact that these transpositions are in fact involutions: f(f(x)) = x

Without paying much attention to it, I first thought it would work.

But for cases 3 and 7, it does not work because it is not an 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 once again:

Case 3: (-1, 5) => (5, 1) => (1, -5) => (-5, -1) => (-1, 5) // Good

So, did I misunderstand something?

Or is it in fact a lack of precision in the drafting of the article on Wikipedia and should someone improve it?

Is there not a better way to make these transitions without that I need to use two functions switchToOctant_onInput and switchToOctant_onOutput (the obvious solution to this problem that I see now)?

Delgan
  • 18,571
  • 11
  • 90
  • 141
  • Your octants don't match Wikipedia, and nowhere does it say the function is involute. – stark Jul 10 '15 at 19:39
  • *This is based on the fact that these transpositions are in fact involutions: `f(f(x)) = x`* How did you reach this conclusion? – But I'm Not A Wrapper Class Jul 10 '15 at 19:41
  • @stark Why do you said it does not match? Wikipedia start counting from 0, I start from 1, this is the only difference that I see. – Delgan Jul 10 '15 at 19:48
  • @CyberneticTwerkGuruOrc This may be a misnomer, but if it is written to apply the function on the input and the output, I understood the switch trick works this way: octant X => octant = 1> octant X (by applying the X case from the function). We can observe that generally it works, except for cases 2 and 6. – Delgan Jul 10 '15 at 19:53
  • 2
    It seems to me that what the description on wiki is supposed to convey is "move the coordinates to octant 0, do the calculations there, then reverse the move", and the inverses for the moves are not specified because they are easy to see - might that explain it? – G. Bach Jul 10 '15 at 20:21
  • @G.Bach If this is "easy to see", why do they give the function and say to use it on input and output, without specifying to pay attention to this little yet tricky detail? You may be right, so we must differentiate input and output cases. It might be good to add a few words about it in the Wikipedia page. – Delgan Jul 10 '15 at 21:29
  • I meant the inverses of the transpositions are easy to see, not that understanding what to do is easy to see from the description they give. – G. Bach Jul 10 '15 at 21:32
  • @G.Bach I better understand, the function from Wikipedia is called `switchToOctantZeroFrom` which implicitly means that we have to implement the other function `switchToOctantFromZero` by ourselves. I still think someone should clarify it on Wikipedia, as [I am not the only one to have been fooled](https://en.wikipedia.org/w/index.php?title=Bresenham%27s_line_algorithm&action=history), but this is off-topic now. – Delgan Jul 10 '15 at 23:19

2 Answers2

2

Octants 2, 4, 6, 8 are mapped to octant 1 by reflections which are involutive (self-inverse). Octant 5 is mapped to octant 1 by a 180 degree rotation which is also involutive. However, octants 7 and 3 are mapped to octant 1 by +-90 degree rotations which are not involutive. The mappings simply aren't involutive so there's nothing you can do about it. If you want an inverse function you have to write it.

The Wikipedia page is misleading because it says the function is a "flip" which suggests an involution.

There are three approaches I can think of to address the issue: 1) create an inverse function which is very similar except the cases for 3 and 7 are swapped (don't rename the existing function); 2) add cases for negative octants which represent the inverse function so that the inverse of switchOctant(3,x,y) is switchOctant(-3,x,y) which is the same as switchOctant(7,x,y) (however you have to think carefully about octant 0 if you do this); or 3) reduce or eliminate the need for the geometric transformation function by enhancing your line drawing function. In particular, if you enhance the line drawing function to handle any line in the first quadrant (not just first octant!) you can use a geometric transformation mapping any quadrant to the first quadrant which is involutive.

Update

I just thought of one more "angle" on this question (so to speak): it is possible to map your 3rd octant to 1st octant by a reflection. A reflection by a line through the origin with inclination 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 1st and 3rd octants has inclination 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 map the 7th octant to the 1st. So it is possible to find an involution which maps each octant to the first octant. However, there are two problems with this mapping: 1) it's not continuous whereas the mapping given in the Wikipedia article is continuous (meaning there are no sudden jumps in the image of (x,y) as the point moves around the plane); and 2) it's not clear how to use integer arithmetic to effect the mapping.

Continuity is not just a theoretical issue. It becomes practical when you consider how you're going to map a point on the boundary between two octants. If you don't do that very carefully with a discontinuous map, you will definitely get incorrect results.

So this idea is not good, but I just thought I'd mention it for the sake of completeness.

Edward Doolittle
  • 4,002
  • 2
  • 14
  • 27
  • Thank you. My mistake was to think that Wikipedia article implicitly said to apply the only one given function in input and ouput, but this is not the case. I like the different solutions you propose to me, however I do not understand why you are saying to not rename the existing function? – Delgan Jul 12 '15 at 06:10
  • It has nothing to do with functionality. Rather it's an issue of maintainability. If you change the name of a function, you'll have to change every function call in all code that uses the function. That may not be an issue now, but the habit is important. Another issue is that if someone (you, even) searches in the future for the function, you'll get more relevant hits if you use the name of the function as it appears online. Similarly, I would not start counting octants at 1 if Wikipedia starts at 0 unless you have a compelling reason. In general, I suggest a habit of making minimal changes. – Edward Doolittle Jul 13 '15 at 22:44
  • The update is interesting and good to know, thank you. I will keep using the easiest solution (create a inverse function) as it is safer. – Delgan Jul 14 '15 at 20:16
1

The octant discussion in the Bresenham algorithm is based on obvious axial symmetries with respect to the medians and diagonals. No involution property is required. (If you need the inverse of f, well, use... the inverse of f; but this is not explicitly required).

A simple variant is the digital version of the parametric equation of the line:

X = X0 + (k.(X1 - X0)) / D
Y = Y0 + (k.(Y1 - Y0)) / D

where

D = Max(|X1 - X0|, |Y1 - Y0|)

and k in range [0..D].