Bresenhams line algorithm optimization

Question

Based on these guidelines I optimised Bresenhams line algorithm, it now fits for all kinds of line cases like images a, b, c, d, e, f, g, h show in those guidelines.

This is my test.txt input file for all line cases:

x1 y1 x2 y2
10 10 50 10
10 20 50 20
60 10 60 50
70 60 70 10
80 30 100 50
100 60 80 40
110 60 130 40
130 50 110 70
140 30 200 10
140 10 200 30
210 10 230 60
240 60 260 10

My code:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include<windows.h>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
 //Get a console handle
 HWND myconsole = GetConsoleWindow();
 //Get a handle to device context
 HDC mydc = GetDC(myconsole);
 //color
 COLORREF COLOR = RGB(255, 255, 255);
 int x1, y1, x2, y2;
 ifstream fin("test.txt");
 string line;
 if (fin.is_open()) 
 {
 while (getline(fin, line)) 
 {
 stringstream S;
 S << line; //store the line just read into the string stream
 vector<int> thisLine(4, 0); //to save the numbers
 for (int c(0); c<4; c++) 
 {
 //use the string stream as a new input to put the data into a vector of int
 S >> thisLine[c];
 }
 for (int c(0); c<4; c++) //set value for each variable
 { 
 if (c == 0) { x1 = thisLine[c]; };
 if (c == 1) { y1 = thisLine[c]; };
 if (c == 2) { x2 = thisLine[c]; };
 if (c == 3) { y2 = thisLine[c]; };
 }
 if (y1 == y2) //horizontal line
 {
 if (x1 > x2) {int x = x2; x2 = x1; x1 = x;}
 for(x1; x1 <= x2; x1++)
 {
 SetPixel(mydc, x1, y1, COLOR);
 }
 }
 if(x1 == x2) //vertical line
 {
 if (y1>y2) { int y = y2; y2 = y1; y1 = y; }
 for (y1; y1 <= y2; y1++)
 {
 SetPixel(mydc, x1, y1, COLOR);
 }
 }
 else
 { //bresenham line algorythm
 int dx = abs(x2 - x1); 
 int dy = abs(y2 - y1);
 int D = 2 * dy - dx;
 int D1 = (2 * dy) - (2 * dx);
 int D2 = 2 * dy;
 double m = (double)(y2 - y1) / (x2 - x1); 
 if (x1 > x2) //switch numbers so line begin from left to right side
 {
 int x = x2;
 x2 = x1; 
 x1 = x; 
 int y = y2;
 y2 = y1;
 y1 = y;
 }
 if (m == -1)
 {
 for (x1; x1 <= x2; x1++)
 {
 SetPixel(mydc, x1, y1, COLOR);
 y1 = y1 - 1;
 }
 }
 if (m == 1)
 {
 for (x1; x1 <= x2; x1++)
 {
 SetPixel(mydc, x1, y1, COLOR);
 y1 = y1 + 1;
 }
 }
 if (m> -1 && m<0)
 {
 for (x1; x1 <= x2; x1++)
 {
 if (D>0){
 SetPixel(mydc, x1, y1, COLOR);
 y1 = y1 - 1;
 D = D + D1;
 }
 else{ SetPixel(mydc, x1, y1, COLOR); D = D + D2; }
 }
 }
 if (m>0 && m<1)
 {
 for (x1; x1 <= x2; x1++)
 {
 if (D>0){
 SetPixel(mydc, x1, y1, COLOR);
 y1 = y1 + 1;
 D = D + D1;
 }
 else{ SetPixel(mydc, x1, y1, COLOR); D = D + D2; }
 }
 }
 if (m > 1) //rotate 90 degrees
 {
 int x11 = y1;
 int x12 = y2;
 y1 = x1;
 y2 = x2;
 x1 = x11;
 x2 = x12;
 int dx = abs(x2 - x1);
 int dy = abs(y2 - y1);
 int D = 2 * dy - dx;
 int D1 = (2 * dy) - (2 * dx);
 int D2 = 2 * dy;
 for (x1; x1 <= x2; x1++)
 {
 if (D > 0) {
 SetPixel(mydc, y1, x1, COLOR);
 y1 = y1 + 1;
 D = D + D1;
 }
 else{ SetPixel(mydc, y1, x1, COLOR); D = D + D2; }
 }
 }
 if (m< -1) //rotate 90 degrees
 {
 int x11 = y1;
 int x12 = y2;
 y1 = x1;
 y2 = x2;
 x1 = x11;
 x2 = x12;
 int dx = abs(x2 - x1);
 int dy = abs(y2 - y1);
 int D = 2 * dy - dx;
 int D1 = (2 * dy) - (2 * dx);
 int D2 = 2 * dy;
 for (x1; x1 >= x2; x1--)
 {
 if (D>0) {
 SetPixel(mydc, y1, x1, COLOR);
 y1 = y1 + 1;
 D = D + D1;
 }
 else{ SetPixel(mydc, y1, x1, COLOR); D = D + D2; }
 }
 }
 }
 }
 ReleaseDC(myconsole, mydc);
 cin.ignore(); //nedrikst but cout
 }
 else
 {
 cout << "File could not be opened." << endl;
 }
 return 0;
}

But my question is: can I do this in a more effective way? If I had a million coordinates would it help to write my code differently? I mean like creating functions for all line cases not just an if with long case code or something like that.

I am hoping for suggestions that improve the performance. I am also interested in examples where code would execute slower (like in what case I could write code worse than this...).

Answer 1

Is there any reason you are storing temporary those values in vector on start?

 for (int c(0); c<4; c++) 
 {
 //use the string stream as a new input to put the data into a vector of int
 S >> thisLine[c];
 }
 for (int c(0); c<4; c++) //set value for each variable
 { 
 if (c == 0) { x1 = thisLine[c]; };
 if (c == 1) { y1 = thisLine[c]; };
 if (c == 2) { x2 = thisLine[c]; };
 if (c == 3) { y2 = thisLine[c]; };
 }

Can be simply replaced with

 S >> x1 >> y1 >> x2 >> y2;

You are also have in code

 if (y1 == y2) //horizontal line
 ...;
 if (x1 == x2) //vertical line

I would replace this with

 if (y1 == y2)
 ...;
 else if (x1 == x2)

The only case where whose 2 samples behaves differently is y1 == y1 && x1 == x2, which is simply point and will be handled by first if. And with if ...; if you're printing this point twice. Later on you also have if (m==-1) ...; if (m==1) ...; - same thing.

if (x1 > x2) {int x = x2; x2 = x1; x1 = x;}

Simply use std::swap - more readable.

• user3668051: i updated my code with your suggested changes and tested it with 3000 lines (i used visual studio intrumentation profiler) and from 8.1 second i got 7.8 seconds(small but still improvement :) ). also i found out that setPixel() function takes the most time to execute. Is there any faster function than this? or in this case it wouldnt make difference, since every point is being colored individually?
• Dawid: Try this function: msdn.microsoft.com/en-us/library/windows/desktop/…. As they write "SetPixelV is faster than SetPixel because it does not need to return the color value of the point actually painted."

Answer 2

In code with improbements:

line

vector<int> thisLine(4, 0); //to save the numbers

is never used.

Then in Bresenham(int,int,int,int):

COLORREF COLOR = RGB(255, 255, 255);

can be const (not sure if this will help, it may :) )

const COLORREF COLOR = RGB(255, 255, 255);

Also another variables (dx, dy, D, D1, D2) can be const.

You can also check if SetPixel is not called too often (count in runtime).