Drawing Straight Line using DDA Algorithm in C/C++

The digital differentia analyzer (DDA) is a scan-conversion line algorithm. In this algorithm, we sample the line at unit intervals in one coordinate and determine corresponding integer values nearest the line path of the other coordinate and plot those coordinate (pixel) in computer screen. Consider first a line with positive slope. If the slope is less than or equal to 1, we sample at unit x intervals (dx = 1) and computer each successive y value as y(k+1) = y(k) + m. Subscript k takes integer values starting from 1, for the first point, and increases by 1 until the final endpoint is reached. For lines with a positive slope greater than 1, we reverse the roles of x and y.That is, we sample at unit y intervals (dy = 1) and calculate each succeeding x value as x(k+1) = x(k) + (1/m)

The following section implements DDA Algorithm in C/C++. The source code is complied using gcc Compiler and Code::Blocks IDE. To print a pixel, SetPixel() function of windows.h is used.

Note

To run this code in your machine with Code::blocks IDE, add a link library libgdi32.a (it is usually inside MinGW\lib )  in linker setting and make the file extension .cpp but not .c. For C user, here is a link to download C file of this tutorial. Download

#include <windows.h>
#include <cmath>
#define ROUND(a) ((int) (a + 0.5))
/* set window handle */
static HWND sHwnd;
static COLORREF redColor=RGB(255,0,0);
static COLORREF blueColor=RGB(0,0,255);
static COLORREF greenColor=RGB(0,255,0);
void SetWindowHandle(HWND hwnd){
sHwnd=hwnd;
}
/* SetPixel */
void setPixel(int x,int y,COLORREF& color=redColor){
if(sHwnd==NULL){
MessageBox(NULL,"sHwnd was not initialized !","Error",MB_OK|MB_ICONERROR);
exit(0);
}
HDC hdc=GetDC(sHwnd);
SetPixel(hdc,x,y,color);
ReleaseDC(sHwnd,hdc);
return;
// NEVERREACH //
}
void drawLineDDA(int xa, int ya, int xb, int yb){
int dx = xb - xa, dy = yb - ya, steps, k;
float xIncrement, yIncrement, x = xa, y = ya;
if(abs(dx) > abs(dy)) steps = abs(dx);
else steps = abs(dy);
xIncrement = dx / (float) steps;
yIncrement = dy / (float) steps;
setPixel(ROUND(x), ROUND(y));
for(int k = 0; k < steps; k++){
x += xIncrement;
y += yIncrement;
setPixel(x, y);
}
}
/* Window Procedure WndProc */
LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam){
switch(message){
case WM_PAINT:
SetWindowHandle(hwnd);
drawLineDDA(10, 20, 250, 300);
break;
case WM_CLOSE: // FAIL THROUGH to call DefWindowProc
break;
case WM_DESTROY:
PostQuitMessage(0);
return 0;
default:
break; // FAIL to call DefWindowProc //
}
return DefWindowProc(hwnd,message,wParam,lParam);
}
int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int iCmdShow){
static TCHAR szAppName[] = TEXT("Straight Line");
WNDCLASS wndclass;
wndclass.style         = CS_HREDRAW|CS_VREDRAW ;
wndclass.lpfnWndProc   = WndProc ;
wndclass.cbClsExtra    = 0 ;
wndclass.cbWndExtra    = 0 ;
wndclass.hInstance     = hInstance ;
wndclass.hIcon         = LoadIcon (NULL, IDI_APPLICATION) ;
wndclass.hCursor       = LoadCursor (NULL, IDC_ARROW) ;
wndclass.hbrBackground = (HBRUSH) GetStockObject (WHITE_BRUSH) ;
wndclass.lpszMenuName  = NULL ;
wndclass.lpszClassName = szAppName ;
// Register the window //
if(!RegisterClass(&wndclass)){
MessageBox(NULL,"Registering the class failled","Error",MB_OK|MB_ICONERROR);
exit(0);
}
// CreateWindow //
HWND hwnd=CreateWindow(szAppName,"DDA - Programming Techniques",
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT,
CW_USEDEFAULT,
CW_USEDEFAULT,
CW_USEDEFAULT,
NULL,
NULL,
hInstance,
NULL);
if(!hwnd){
MessageBox(NULL,"Window Creation Failed!","Error",MB_OK);
exit(0);
}
// ShowWindow and UpdateWindow //
ShowWindow(hwnd,iCmdShow);
UpdateWindow(hwnd);
// Message Loop //
MSG msg;
while(GetMessage(&msg,NULL,0,0)){
TranslateMessage(&msg);
DispatchMessage(&msg);
}
/* return no error to the operating system */
return 0;
}

The output of this program is looks like

DDA algorithm is faster than the direct use of equation y = mx + c however, the rounding operations and floating-point arithmetic makes it still time consuming. To overcome this limitation of DDA Algorithm, Bresenham discovered Bresenham’s Line Drawing Algorithm.

Read more »

Conversion of infix string to postfix and evaluation of postfix string to make a simple calculator application in C++.

(A) Algorithm for converting an infix expression into postfix operation

1. Add “(“ at the beginning and “)” at the end of an 

infix expression Q.
2. Scan Q from left to right and repeat 

step 3 to step 6.
3  If an operand is encountered, add it into postfix P.
4. If a left parenthesis is encountered, 

push it onto the stack S
5. If and operator op is encountered then,
(a) Repeatedly pop from stack S and add 

it to postfix each operator which has 
same precedence as or higher precedence than op.
(b) Add op to Stack S.
6. If a right parenthesis is encountered, then
(a) Repeatedly pop from stack S and add 

it to postfix each operator until left parenthesis is encountered on stacks.
(b) Remove the left parenthesis.

(B) Algorithm for evaluation of postfix string

1. Scan postfix P from left to right and repeat 

step 2 and 3 for each elements of P until the

 NULL character or other symbol is encountered.
2. If an operand is encountered then push it on to the stack.
3. If an operator op is encountered, then
(a) Remove the top elements of stack S where A is the

 top element and B is next top element
(b) Evaluate B op A
(c) Place the result back onto the stack S
(d) Return top of the stack which is required

 result for our calculation

Source code for both infix to postfix and postfix evaluation

/****************************************************************

Program: Conversion of Infix to Postfix String and Evaluation

Language: C/C++

by Bibek Subedi

June 13, 2011

Operators Used

1. '+' For addition

2. '-' For Subtraction

3. '*' For Multiplication

4. '/' For Division

5. '^' For Exponentiation

Program Limitations

* This program Only process single digit operations

* Can't handle unary operation

* Only process left to right associativity

***************************************************/

#include<iostream>

#include<cmath>

#include<cstdlib>

#include<string>

#define MAX_SIZE 20

using namespace std;

template<class T>

class Stack{

private:

T item[MAX_SIZE];

int top;

public:

Stack(){

top = -1;

}

void push(T data){

if(!this->is_full())

item[++top] = data;

else{

cout<<"Stack Error"<<endl;

exit(10);

}

}

T pop(){

if(!this->is_empty())

return item[top--];

else{

cout<<"Stack is Empty"<<endl;

exit(11);

}

}

int size(){

return top+1;

}

bool is_empty(){

if(top==-1)

return true;

else

return false;

}

bool is_full(){

if(top==MAX_SIZE-1)

return true;

else

return false;

}

void display(){

for(int i=0; i<this->size(); i++){

cout<<item[i]<<" ";

}

cout<<endl;

}

T return_top(){

return item[top];

}

};

class Convert{

private:

bool num_flag;

bool two_digit_flag;

public:

Convert();

string return_with_bracket(string infix);

void to_Postfix(string infix,char postfix[]);

bool prcd(char op1, char op2);

int isOperand(char op);

int isOperator(char op);

bool return_flag(){

return num_flag;

}

};

Convert::Convert(){

this->num_flag = false;

this->two_digit_flag = false;

}

string Convert::return_with_bracket(string infix){

return("(" + infix + ")");

}

bool Convert::prcd(char op1, char op2){

if((op1=='+' || op1=='-' || op1=='*' || op1=='/') && op2=='('  )

return true;

if(op1=='+' && op2=='+')

return true;

if(op1=='-' && op2=='-')

return false;

if(op1=='-' && op2=='+')

return false;

if(op1=='+' && op2=='-')

return false;

if(op1=='/' && op2=='/')

return false;

if(op1=='/' && (op2=='-' || op2=='+'))

return true;

if(op1=='*' && (op2=='+' || op2=='-'))

return true;

if((op1 == '-' || op1 == '+') && (op2 =='*' || op2 == '/'))

return false;

if((op1 == '$' || op1 == '+') && (op2 =='*' || op2 == '/' || op2=='-'))

return true;

if((op1 == '-' || op1 == '+' || op1 =='*' || op1 == '/')&& op2=='^')

return false;

if(op1 == '^' && ( op2 == '+' || op2 =='*' || op2 == '/' || op2=='-'))

return false;

}

int Convert::isOperand(char op){

return(op>= '0' && op <= '9');

}

int Convert::isOperator(char op){

return(op=='+' || op=='-' || op == '/' || op=='*' || op=='^');

}

void Convert::to_Postfix(string infix, char postfix[]){

int position, outpos=0;

char c;

int count = 0;

char temp;

char stacktop ;

Stack<char> stack;

for(position = 0; (c = infix[position])!='\0'; position++){

if(this->isOperand(c)){

postfix[outpos++] = c;

this->num_flag = true;

count++;

if(count>=2){

this->two_digit_flag = true;

}

}else if(this->isOperator(c)){

count = 0;

if(isOperator(infix[position]) && isOperator(infix[position+1])){

cout<<"\aMissing argument in between "<<infix[position]<<" and "<<infix[position+1]

<<" in column "<< position+1<<endl;

exit(9);

}

if(this->prcd(c, stacktop)){

stacktop=stack.return_top();

stack.push(c);

stacktop = c;

}else{

while(true){

temp = stack.pop();

postfix[outpos++] =temp;

stacktop = stack.return_top();

if(prcd(c, stacktop) || stacktop=='(')

break;

}

stack.push(c);

stacktop = stack.return_top();

}

}

else if(c=='('){

count = 0;

stack.push(c);

stacktop = stack.return_top();

}else if(c==')'){

count = 0;

while(1){

if(stack.size()==0){

cout<<"Warning!! Number of ')' is greater than '('" <<endl;

exit(2);

}

temp = stack.pop();

if(temp!='('){

postfix[outpos++] = temp;

}else{

break;

}

}

stacktop =stack.return_top();

}

else{

cout<<"Invalid input";

exit(3);

}

if(infix[position]==')' && infix[position+1]=='('){

stack.push('*');

stacktop = stack.return_top();

}

}

if(stack.size()!=0){

cout<<"Warning!!Number of '(' is greater than ')'"<<endl;

// exit(6);

}

if(!this->return_flag()){

cout<<"You must Enter Numeric value for calculation"<<endl;

cout<<"This program cannot perform operations on variables";

exit(5);

}

if(this->two_digit_flag){

cout<<"Sory! Althoug u may  have entered right string"<<endl;

cout<<"this program is only for single digit operation"<<endl;

exit(8);

}

postfix[outpos] = '\0';

}

class Evaluate{

public:

double eval(char expr[], Convert &);

double oper(int symb, double op1, double op2);

};

double Evaluate::oper(int symb, double op1, double op2){

switch(symb){

case '+': return (op1 + op2);

case '-': return (op1 - op2);

case '*': return (op1 * op2);

case '/': return (op1 / op2);

case '^': return (pow(op1, op2));

}

}

double Evaluate::eval(char expr[],Convert &convert){

int c, position;

char temp1;

int count = 0;

double opnd1, opnd2, value;

Stack<double> stack;

for(position = 0; (c = expr[position])!='\0'; position++){

if(convert.isOperand(c)){

temp1 = double(c-'0');

stack.push(temp1);

}else{

opnd2 = stack.pop();

if(stack.size()==0){

cout<<"This program cannot process unary operation";

exit(1);

}

opnd1 = stack.pop();

value = oper(c, opnd1, opnd2);

stack.push(value);

}

}

if(stack.size()>=2){

cout<<"Sory! this program cannot calculate this"<<endl;

cout<<"Enter +, *, /, - or ^ between bracket"<<endl;

exit(4);

}

return (stack.pop());

}

int main(){

Convert convert;

Evaluate evaluate;

string bracketted_infix;

char infix[50], postfix[50];

char choice;

while(1){

cout<<"Enter string: ";

cin>>infix;

cout<<endl;

cout<<"Entered String: "<<infix<<endl;

bracketted_infix = convert.return_with_bracket(infix);

convert.to_Postfix(bracketted_infix, postfix);

cout<<"Equivalent Postfix string: "<<postfix<<endl;

cout<<"RESULT: ";

cout<<evaluate.eval(postfix, convert);

cout<<"\nCalculate another string?(y/n) ";

cin>>choice;

cout<<endl;

if(choice=='n')

break;

}

return 0;

}

Read more »

Data Structure: Implementation of Queue in C++

queue is an order collection of items from which items may be deleted at one end (called front or head of the queue) and into which items may be inserted at the other end (called the rear end  or tail of the queue). It is First-in-First-out (FIFO) type of data structure. Operations on queue are: Create Queue, insert items , remove items, display etc.

Algorithm for Implementation of Queue in C++

1. Declare and initialize neccessary variables, front = 0, rear = -1 etc.
2. For enque operation, 
        If rear >= MAXSIZE - 1
            print "Queue is full"
        Else
           - Increment rear by 1 i.e. rear = rear + 1;
           - queue[rear] = item;
3. For next enqueue operation, goto step 2.
4. For dequeue  operation
        If front > rear
            print "Queue is Empty"
        Else
             - item = queue[front]
             - increment front by 1 i.e. front = front + 1
5. For dequeue next data items, goto step 4.
6. Stop

Source Code:

#include<iostream>
#include<cstdlib>
#define MAX_SIZE 10
using namespace std;
class Queue{
    private:
        int item[MAX_SIZE];
        int rear;
        int front;
    public:
        Queue();
        void enqueue(int);
        int dequeue();
        int size();
        void display();
        bool isEmpty();
        bool isFull();
};
Queue::Queue(){
    rear = -1;
    front = 0;
}
void Queue::enqueue(int data){
        item[++rear] = data;
}
int Queue::dequeue(){
        return item[front++];
}
void Queue::display(){
    if(!this->isEmpty()){
        for(int i=front; i<=rear; i++)
            cout<<item[i]<<endl;
    }else{
        cout<<"Queue Underflow"<<endl;
    }
}
int Queue::size(){
    return (rear - front + 1);
}
bool Queue::isEmpty(){
    if(front>rear){
        return true;
    }else{
        return false;
    }
}
bool Queue::isFull(){
    if(this->size()>=MAX_SIZE){
        return true;
    }else{
        return false;
    }
}
int main(){
    Queue queue;
    int choice, data;
    while(1){
        cout<<"\n1. Enqueue\n2. Dequeue\n3. Size\n4. Display all element\n5. Quit";
        cout<<"\nEnter your choice: ";
        cin>>choice;
        switch(choice){
            case 1:
            if(!queue.isFull()){
                    cout<<"\nEnter data: ";
                    cin>>data;
                    queue.enqueue(data);
            }else{
                cout<<"Queue is Full"<<endl;
            }
            break;
            case 2:
            if(!queue.isEmpty()){
                cout<<"The data dequeued is :"<<queue.dequeue();
            }else{
                cout<<"Queue is Emtpy"<<endl;
            }
                break;
            case 3:
                cout<<"Size of Queue is "<<queue.size();
                break;
            case 4:
                queue.display();
                break;
            case 5:
                exit(0);
                break;
        }
    }
    return 0;
}

Read more »

Circular Queue Implementation in C++

In linear queue, when we delete any element, only front increment by one but position is not used later. So, when we perform more add and delete operations, memory wastage increases. But in circular queue, memory is utilized if we delete any element that position is used later due to its circular representation.

Algorithm for Circular Queue

1. Declare and initialize necessary variables such as head = 0, tail = 0 etc.
2. For enqueue operation,
If head = (tail+1)%MAXSIZE
print "Queue is Full"
Else
queue[tail] = item
tail = (tail+1)%MAXSIZE
3. For enqueue of next data item, goto step 2
4. For dequeue operation, 
If head = tail
print "Queue is Empty"
Else
Remove item i.e. item = queue[head]
Set head = (head + 1)%MAXSIZE
5. For next dequeue operation , goto step 4
6. Stop

Source Code for Circular Queue

#include<iostream>
#include<cstdlib>
#define MAX_SIZE 4

using namespace std;

class Queue{
    private:
        int item[MAX_SIZE];
        int head;
        int tail;
    public:
        Queue();
        void enqueue(int);
        int dequeue();
        int size();
        void display();
        bool isEmpty();
        bool isFull();
};

Queue::Queue(){
    head = 0;
    tail = 0;
}


void Queue::enqueue(int data){
    item[tail] = data;
    tail = (tail+1)%MAX_SIZE;
}


int Queue::dequeue(){
    int temp;
    temp = item[head];
    head = (head+1)%MAX_SIZE;
    return temp;
}


int Queue::size(){
    return (tail - head);
}

void Queue::display(){
    int i;
    if(!this->isEmpty()){
        for(i=head; i!=tail; i=(i+1)%MAX_SIZE){
            cout<<item[i]<<endl;
        }
    }else{
        cout<<"Queue Underflow"<<endl;
    }
}


bool Queue::isEmpty(){
    if(abs(head == tail)){
        return true;
    }else{
        return false;
    }
}

bool Queue::isFull(){
    if(head==(tail+1)%MAX_SIZE){
        return true;
    }else{
        return false;
    }
}


int main(){
    Queue queue;
    int choice, data;
    while(1){
        cout<<"\n1. Enqueue\n2. Dequeue\n3. Size\n4. Display all element\n5. Quit";
        cout<<"\nEnter your choice: ";
        cin>>choice;
        switch(choice){
            case 1:
            if(!queue.isFull()){
                cout<<"\nEnter data: ";
                cin>>data;
                queue.enqueue(data);
            }else{
                cout<<"Queue is Full"<<endl;
            }
            break;
            case 2:
            if(!queue.isEmpty()){
                cout<<"The data dequeued is :"<<queue.dequeue();
            }else{
                cout<<"Queue is Emtpy"<<endl;
            }
            break;
            case 3:
            cout<<"Size of Queue is "<<queue.size();
            break;
            case 4:
            queue.display();
            break;
            case 5:
            exit(0);
            break;
        }
    }
    return 0;
}

Read more »