Best algorithm to plot lines

Question

Recently I had to write an algorithm to draw vertical, horizontal and 45 deg lines. I wanted that algorithm just to works as fast as possible so I extended all the possible cases :

if (x0 == x1){
    ...
  }
else if (y0 == y1)
  {
    ...
  }
else {
  if (distance(x0,x1) == distance(y0,y1)){
    ...
  }
}

and of course, this is not DRY nor clean...

What's the cleanest and better version of an algorithm like that?

Notice that if the line is not vertical, horizontal or 45deg the function should do nothing (so nothing like raster algorithm).

An example of declaration can be line(int x0, int y0, int x1, int y1);

Do the ellipses represent something that you have already written, or are you expecting us to write your algorithms for you? — Peter Abolins, May 21 '18 at 13:49
@PeterAbolins nono I just wanted to point out my approach to solve the problem and I just wrote the basic schema, all the code will be long and not interesting. I was looking for a better solution... even pseudocode — masi, May 21 '18 at 13:50
A better solution has to be based on an existing solution to start with. We can't provide a comparatively better solution if there is nothing in place to compare to. My point is that all you have provided is top-level logic to cover three possible scenarios. There is no algorithm to draw anything. — Peter Abolins, May 21 '18 at 13:53
@PeterAbolins basically, the problem with my code was that it does a lot of checks to find which is the minimum between the Xs and the Ys and set the for loop for each of these cases, which is not optimal i think — masi, May 21 '18 at 13:54
You may want to search the internet for "Bresenham line c++", I hear its an efficient algorithm. — Thomas Matthews, May 21 '18 at 14:17
@ThomasMatthews that was true a long long time ago [**DDA**](https://stackoverflow.com/a/24682318/2521214) (coded on integers without the division) is now faster then **Bresenham** due to changes in CPU architecture (IIRC i80386 was the treshold) — Spektre, May 22 '18 at 07:31

score 0 · Answer 1 · answered May 21 '18 at 13:53

Something like this:

x_delta = ...;
y_delta = ...;
for (x=x0,y=y0; x+=x_delta, y+=y_delta; x<=x1&&y<=y1) {
  point(x,y);
}

If you really need to avoid additions with zero probably what you have is OK. But then you can have a value templated function and use the same function optimized at compile-time.

Best algorithm to plot lines

1 Answers1