Code Blocks

Modelling Transformations in OpenGL

2015-01-11T06:59:00.000-08:00

#include<stdio.h>
#include<GL/glut.h>

/* This function is to draw a triangle  */
void draw_triangle()
{
  glBegin(GL_LINES);
  glVertex2f(-0.40, -0.25);
  glVertex2f(-0.60, -0.25);

  glVertex2f(-0.60, -0.25);
  glVertex2f(-0.50, 0.25);

  glVertex2f(-0.40, -0.25);
  glVertex2f(-0.50, 0.25);
  glEnd();
  glFlush();
}

void draw()
{
  glClear(GL_COLOR_BUFFER_BIT);

  /* Draw a triangle using solid lines */
  draw_triangle();                   /* solid lines */

  /* The same triangle is drawn again, but with a dashed  */
  /* line stipple and translated (to the left along the  */
  /* negative xaxis) */
  glEnable(GL_LINE_STIPPLE);         /* dashed lines */
  glLineStipple(1, 0xF0F0); 
  glLoadIdentity();
  glTranslatef(-0.30, 0.0, 0.0);
  draw_triangle();

  /* A triangle is drawn with a long dashed line stipple,  */
  /* with its height (yaxis) halved and its width (xaxis)  */
  /* increased by 50%  */
  glLineStipple(1, 0xF00F);          /*long dashed lines */
  glLoadIdentity();
  glScalef(1.5, 0.5, 1.0);
  draw_triangle();

  /* A rotated triangle(rotated at 90 degree w.r.t the z-axix), 
  made of dotted lines, is drawn */
  glLineStipple(1, 0x8888);          /* dotted lines */
  glLoadIdentity();
  glRotatef (90.0, 0.0, 0.0, 1.0);
  draw_triangle();
  glDisable (GL_LINE_STIPPLE);

  glFlush();
}

void Init()
{
  /* Set clear color to black */
  glClearColor(0.0f, 0.0f, 0.0f, 0.0f);
  /* Set fill color to white */
  glColor3f(1.0, 1.0, 1.0);
  gluOrtho2D(0.0 , 1.0 , 0.0 , 1.0);
  /* glViewport() command is used to define the rectangle of */
  /* the rendering area where the final image is mapped */
  glViewport(0.0, 0.0, 1.0, 1.0);
  /* glMatrixMode specifies the mode of transformation */
  glMatrixMode(GL_MODELVIEW);
  /* set the current matrix to the identity matrix */
  glLoadIdentity();
}

int main(int argc, char **argv)
{
  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  glutInitWindowPosition(0, 0);
  glutInitWindowSize(640, 480);
  glutCreateWindow("Transformation");
  Init();
  glutDisplayFunc(draw);
  glutMainLoop();
  return 0;
}

Output
======

Written by Munia Balayil

2D scaling Without Using OpenGL Function For Scaling

2014-12-23T00:22:00.000-08:00

Program to draw a square of side 100 units at the center of the screen and scale it such that it enlarges to a square of side 150 units without using OpenGL function for scaling



#include<stdio.h>
#include<GL/glut.h>

int i;
float scalex, scaley, a[10], b[10], x, y, square_side;

void line(float x, float y, float a, float b)
{
  glBegin(GL_LINES);
  glVertex2f(x, y);
  glVertex2f(a, b);
  glEnd();
}

void display_square()
{
  for(i = 0; i < 4; i++)
  {
    if(i != 3)
      line(a[i], b[i], a[i+1], b[i+1]);
    else
      line(a[i], b[i], a[0], b[0]);
  }
}

void Init()
{
  /* Set clear color to white */
  glClearColor(1.0, 1.0, 1.0, 0);
  /* Set fill color to black */
  glColor3f(0.0, 0.0, 0.0);
  gluOrtho2D(0.0 , 640.0 , 0.0 , 480.0);
}

void scale()
{
  // Find the translated rectangle vertices
  for(i = 0; i < 4; i++)
  {
    a[i] = a[i] * scalex; b[i] = b[i] * scaley;
  }
}

void draw()
{
 glClear(GL_COLOR_BUFFER_BIT);

  // Find the original square vertices
  // (x, y) represents the upper left point
  x = 270.0; y = 290.0;

  a[0] = x; b[0] = y;
  a[1] = x + square_side; b[1] = y;
  a[2] = x + square_side; b[2] = y - square_side;
  a[3] = x; b[3] = y - square_side;
  // Draw original square
  display_square();

  // Perform scaling
  scale();
  // Draw scaled square using dotted lines
  glEnable(GL_LINE_STIPPLE);
  glLineStipple(1, 0xF0F0);
  display_square();
  glDisable(GL_LINE_STIPPLE);

  glFlush();
}

void main(int argc, char **argv)
{
  square_side = 100;
  printf("\n************************************************\n");
  printf("Length of the side of the square: %f\n", square_side);

  scalex = 1.5;
  scaley = 1.5;
  printf("\n************************************************\n");
  printf("Scaling factor along both directions: %f\n", scalex);
  printf("\n************************************************\n");

  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  glutInitWindowPosition(0, 0);
  glutInitWindowSize(640, 480);
  glutCreateWindow("Scaling");
  Init();
  glutDisplayFunc(draw);
  glutMainLoop();
}

Written by Munia Balayil

2D Rotation Without Using OpenGL Function For Rotation

2014-12-23T00:16:00.000-08:00

Program to perform 2D rotation without using OpenGL function for rotation


#include<stdio.h>
#include<math.h>
#include<GL/glut.h>

int x, y, p, q, xa, ya, ra, i, a[10], b[10], da, db;
float dx, dy, theta;

void line(int x, int y, int a, int b)
{
  glVertex2d(x, y);
  glVertex2d(a, b);
}

void display_rectangle()
{
  for(i = 0; i < 4; i++)
  {
    if(i != 3)
      line(a[i], b[i], a[i+1], b[i+1]);
    else
      line(a[i], b[i], a[0], b[0]);
  }
}

void Init()
{
  /* Set clear color to white */
  glClearColor(1.0, 1.0, 1.0, 0);
  /* Set fill color to black */
  glColor3f(0.0, 0.0, 0.0);
  gluOrtho2D(0 , 640 , 0 , 480);
}

void rotate()
{
  // Find the vertices of the rotated rectangle
  theta = (float)(ra*(3.14/180));
  for(i = 0;i<4;i++)
  {
    a[i] = (xa + ((a[i] - xa)*cos(theta) - (b[i] - ya)*sin(theta)));
    b[i] = (ya + ((a[i] - xa)*sin(theta) + (b[i] - ya)*cos(theta)));
  }
}

void transform()
{
  glClear(GL_COLOR_BUFFER_BIT);

  glBegin(GL_LINES);
  // Find the original rectangle vertices
  da = p - x; db = q - y;
  a[0] = x; b[0] = y;
  a[1] = x + da; b[1] = y;
  a[2] = x + da; b[2] = y + db;
  a[3] = x; b[3] = y + db;

  // Draw original rectangle
  display_rectangle();

  rotate();
  
  // Draw rotated rectangle
  display_rectangle();
  
  glEnd();

  glFlush();

}

void main(int argc, char **argv)
{
  printf("\n**********************************************\n");
  printf("Enter the upper left corner of the rectangle:\n");
  scanf("%d%d", &x, &y);
  printf("\n**********************************************\n");
  printf("Enter the lower right corner of the rectangle:\n");
  scanf("%d%d", &p, &q);

  printf("\n********************Rotation********************\n");
  printf("Enter the value of fixed point and angle of rotation:\n");
  scanf("%d%d%d", &xa, &ya, &ra);

  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  glutInitWindowPosition(0, 0);
  glutInitWindowSize(640, 480);
  glutCreateWindow("Rotation");
  Init();
  glutDisplayFunc(transform);
  glutMainLoop();
}

Written by Munia Balayil

2D Translation Without Using OpenGL Function For Translation

2014-12-22T21:29:00.002-08:00

Program to draw a rectangle and translate it without using OpenGL function for translation


#include<stdio.h>
#include<GL/glut.h>

int x, y, p, q, a[10], b[10], da, db, i;
float dx, dy;

void line(int x, int y, int a, int b)
{
  glBegin(GL_LINES);
  glVertex2d(x, y);
  glVertex2d(a, b);
  glEnd();
}

void display_rectangle()
{
  for(i = 0; i < 4; i++)
  {
    if(i != 3)
      line(a[i], b[i], a[i+1], b[i+1]);
    else
      line(a[i], b[i], a[0], b[0]);
  }
}

void Init()
{
  /* Set clear color to white */
  glClearColor(1.0, 1.0, 1.0, 0);
  /* Set fill color to black */
  glColor3f(0.0, 0.0, 0.0);
  gluOrtho2D(0 , 640 , 0 , 480);
}

void translate()
{
  // Find the translated rectangle vertices
  for(i = 0; i < 4; i++)
  {
    a[i] = a[i] + dx; b[i] = b[i] + dy;
  }
}

void transform()
{
 glClear(GL_COLOR_BUFFER_BIT);

  // Find the original rectangle vertices
  da = p-x; db = q-y;
  a[0] = x; b[0] = y;
  a[1] = x + da; b[1] = y;
  a[2] = x + da; b[2] = y + db;
  a[3] = x; b[3] = y + db;
  // Draw original rectangle
  display_rectangle();

  // Perform translation
  translate();
  // Draw translated rectangle using dotted lines
  glEnable(GL_LINE_STIPPLE);
  glLineStipple(1, 0xF0F0);
  display_rectangle();
  glDisable(GL_LINE_STIPPLE);

  glFlush();
}

void main(int argc, char **argv)
{
  printf("\n************************************************\n");
  printf("Enter the upper left corner of the rectangle:\n");
  scanf("%d%d", &x, &y);
  printf("\n************************************************\n");
  printf("Enter the lower right corner of the rectangle:\n");
  scanf("%d%d", &p, &q);

  printf("\n******************Translation******************\n");
  printf("Enter the value of shift vector:\n");
  scanf("%f%f", &dx, &dy);

  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  glutInitWindowPosition(0, 0);
  glutInitWindowSize(640, 480);
  glutCreateWindow("Translation");
  Init();
  glutDisplayFunc(transform);
  glutMainLoop();
}

Written by Munia Balayil

Lexicographic sorting of strings

2014-12-19T00:49:00.000-08:00

/* Program to perform lexicographic sorting of strings */



#include<stdio.h>
#include<string.h>
#include<ctype.h>

void main()
{
  char str[50][50], temp[50], str1[50][50], n[1], temp1[50];
  int i, j, m, k;
  printf("\n##############################\n");
  printf("Enter the number of strings\n");
  gets(n);
  m = atoi(n);
  printf("\n##############################\n");
  printf("Enter the strings\n");
  for(i = 0; i < m; i++)
    gets(str[i]);

  // Convert all letters to lowercase
  for(i = 0; i < m; i++)
    for(j = 0; j < strlen(str[i]); j++)
      if(isupper(str[i][j]) != 0)
        str1[i][j] = tolower(str[i][j]);
      else
        str1[i][j] = str[i][j];

  for(i = 0; i < m; i++)
    for(j = i + 1; j < m; j++)
      if((strcmp(str1[i], str1[j])) > 0)
      {
        strcpy(temp, str[i]);strcpy(temp1, str1[i]);
        strcpy(str[i], str[j]);strcpy(str1[i], str1[j]);
        strcpy(str[j], temp);strcpy(str1[j], temp1);
      }

  printf("\n##############################\n");
  printf("Sorted list is \n");
  for(i = 0; i < m; i++)
    puts(str[i]);
  printf("##############################\n");
}

Written by Munia Balayil

Smiley using Bresenham's Circle Drawing in OpenGL

2014-12-14T22:31:00.001-08:00


#include <stdio.h>
#include <GL/glut.h>

// Center of the cicle = (320, 240)
int xc = 320, yc = 240;

// Plot two points on the lower quadrants 
// using circle's symmetrical property
void plot_point(int x, int y)
{
  glBegin(GL_POINTS);
  glVertex2i(xc+x, yc-y);
  glVertex2i(xc-x, yc-y);
  glEnd();
}

// Function to draw a circle using bresenham's
// circle drawing algorithm
void bresenham_circle(int r)
{
  int x=0,y=r;
  float pk=(5.0/4.0)-r;

  /* Plot the points */
  plot_point(x,y);
  int k;
  /* Find all vertices till x=y */
  while(x < y)
  {
    x = x + 1;
    if(pk < 0)
      pk = pk + 2*x+1;
    else
    {
      y = y - 1;
      pk = pk + 2*(x - y) + 1;
    }
    plot_point(x,y);
  }
}

// Function to draw a smiley
void smiley(void)
{
  /* Clears buffers to preset values */
  glClear(GL_COLOR_BUFFER_BIT);

  int radius = 100;
  // Draw an arc
  bresenham_circle(radius);

  // Draw a vertical line
  glBegin(GL_LINES);
  glVertex2i(xc, yc);
  glVertex2i(xc, yc-60);
  glEnd();

  // Draw 2 points on either side 
  // of the line
  glBegin(GL_POINTS);
  // A big dot made of 4 small dots
  // to the left of the line
  glVertex2i(xc-20, yc-20);
  glVertex2i(xc-19, yc-20);
  glVertex2i(xc-20, yc-19);
  glVertex2i(xc-19, yc-19);

  // A big dot made of 4 small dots
  // to the right of the line
  glVertex2i(xc+20, yc-20);
  glVertex2i(xc+21, yc-20);
  glVertex2i(xc+21, yc-19);
  glVertex2i(xc+20, yc-19);
  glEnd();
  glFlush();
}

void Init()
{
  /* Set clear color to black */
  glClearColor(0.0,0.0,0.0,0);
  /* Set fill color to white*/
  glColor3f(1.0,1.0,1.0);
  gluOrtho2D(0 , 640 , 0 , 480);
}

void main(int argc, char **argv)
{
  /* Initialise GLUT library */
  glutInit(&argc,argv);
  /* Set the initial display mode */
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  /* Set the initial window position and size */
  glutInitWindowPosition(0,0);
  glutInitWindowSize(640,480);
  /* Create the window with title "DDA_Line" */
  glutCreateWindow("Smiley :-)");
  /* Initialize drawing colors */
  Init();
  /* Call the displaying function */
  glutDisplayFunc(smiley);
  /* Keep displaying untill the program is closed */
  glutMainLoop();
}

Output
=====

Written by Munia Balayil

Static Clock using Bresenham's Circle Drawing in OpenGL

2014-12-12T01:41:00.003-08:00

/* To draw a static clock using Bresenham's circle drawing algorithm */
#include <stdio.h>
#include <GL/glut.h>

// Center of the cicle = (320, 240)
int xc = 320, yc = 240;

// Plot eight points using circle's symmetrical property
void plot_point(int x, int y)
{
  glBegin(GL_POINTS);
  glVertex2i(xc+x, yc+y);
  glVertex2i(xc+x, yc-y);
  glVertex2i(xc+y, yc+x);
  glVertex2i(xc+y, yc-x);
  glVertex2i(xc-x, yc-y);
  glVertex2i(xc-y, yc-x);
  glVertex2i(xc-x, yc+y);
  glVertex2i(xc-y, yc+x);
  glEnd();
}

// Function to draw a circle using bresenham's
// circle drawing algorithm
void bresenham_circle(int r)
{
  int x=0,y=r;
  float pk=(5.0/4.0)-r;

  /* Plot the points */
  /* Plot the first point */
  plot_point(x,y);
  int k;
  /* Find all vertices till x=y */
  while(x < y)
  {
    x = x + 1;
    if(pk < 0)
      pk = pk + 2*x+1;
    else
    {
      y = y - 1;
      pk = pk + 2*(x - y) + 1;
    }
    plot_point(x,y);
  }
}

// Function to draw a static clock
void static_clock(void)
{
  /* Clears buffers to preset values */
  glClear(GL_COLOR_BUFFER_BIT);

  int radius = 100;
  // Draw a circle
  bresenham_circle(radius);
  glBegin(GL_LINES);
  // Minute hand
  glVertex2i(xc, yc);
  glVertex2i(xc, yc+95);
  // Hour hand
  glVertex2i(xc, yc);
  glVertex2i(xc+30, yc+50);
  glEnd();
  glFlush();
}

void Init()
{
  /* Set clear color to black */
  glClearColor(0.0,0.0,0.0,0);
  /* Set fill color to white */
  glColor3f(1.0,1.0,1.0);
  gluOrtho2D(0 , 640 , 0 , 480);
}

void main(int argc, char **argv)
{
  /* Initialise GLUT library */
  glutInit(&argc,argv);
  /* Set the initial display mode */
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  /* Set the initial window position and size */
  glutInitWindowPosition(0,0);
  glutInitWindowSize(640,480);
  /* Create the window with title "DDA_Line" */
  glutCreateWindow("bresenham_circle");
  /* Initialize drawing colors */
  Init();
  /* Call the displaying function */
  glutDisplayFunc(static_clock);
  /* Keep displaying untill the program is closed */
  glutMainLoop();
}

Output

Written by Munia Balayil

Bresenham's Circle Drawing Algorithm using OpenGL

2014-12-10T20:44:00.000-08:00

This program is to draw two concentric circles using bresenham's circle drawing algorithm with center (320, 240) and radii of circles as 100 and 200.


#include <stdio.h>
#include <math.h>
#include <GL/glut.h>

// Center of the cicle = (320, 240)
int xc = 320, yc = 240;

// Plot eight points using circle's symmetrical property
void plot_point(int x, int y)
{
  glBegin(GL_POINTS);
  glVertex2i(xc+x, yc+y);
  glVertex2i(xc+x, yc-y);
  glVertex2i(xc+y, yc+x);
  glVertex2i(xc+y, yc-x);
  glVertex2i(xc-x, yc-y);
  glVertex2i(xc-y, yc-x);
  glVertex2i(xc-x, yc+y);
  glVertex2i(xc-y, yc+x);
  glEnd();
}

// Function to draw a circle using bresenham's
// circle drawing algorithm
void bresenham_circle(int r)
{
  int x=0,y=r;
  float pk=(5.0/4.0)-r;

  /* Plot the points */
  /* Plot the first point */
  plot_point(x,y);
  int k;
  /* Find all vertices till x=y */
  while(x < y)
  {
    x = x + 1;
    if(pk < 0)
      pk = pk + 2*x+1;
    else
    {
      y = y - 1;
      pk = pk + 2*(x - y) + 1;
    }
    plot_point(x,y);
  }
  glFlush();
}

// Function to draw two concentric circles
void concentric_circles(void)
{
  /* Clears buffers to preset values */
  glClear(GL_COLOR_BUFFER_BIT);

  int radius1 = 100, radius2 = 200;
  bresenham_circle(radius1);
  bresenham_circle(radius2);
}

void Init()
{
  /* Set clear color to white */
  glClearColor(1.0,1.0,1.0,0);
  /* Set fill color to black */
  glColor3f(0.0,0.0,0.0);
  /* glViewport(0 , 0 , 640 , 480); */
  /* glMatrixMode(GL_PROJECTION); */
  /* glLoadIdentity(); */
  gluOrtho2D(0 , 640 , 0 , 480);
}

void main(int argc, char **argv)
{
  /* Initialise GLUT library */
  glutInit(&argc,argv);
  /* Set the initial display mode */
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  /* Set the initial window position and size */
  glutInitWindowPosition(0,0);
  glutInitWindowSize(640,480);
  /* Create the window with title "DDA_Line" */
  glutCreateWindow("bresenham_circle");
  /* Initialize drawing colors */
  Init();
  /* Call the displaying function */
  glutDisplayFunc(concentric_circles);
  /* Keep displaying untill the program is closed */
  glutMainLoop();
}

Written by Munia Balayil

Generalized Bresenham's Line Drawing Algorithm using OpenGL

2014-12-10T20:21:00.001-08:00

Bresenham's line algorithm is an algorithm that determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures[source]. For more visit this website.

#include<stdio.h>
#include<GL/gl.h>
#include<GL/glut.h>

/* Function that returns -1,0,1 depending on whether x */
/* is <0, =0, >0 respectively */
#define sign(x) ((x>0)?1:((x<0)?-1:0))

/* Function to plot a point */
void setPixel(GLint x, GLint y) {
  glBegin(GL_POINTS);
  glVertex2i(x,y);
  glEnd();
}

/* Generalized Bresenham's Algorithm */
void bres_general(int x1, int y1, int x2, int y2)
{
  int dx, dy, x, y, d, s1, s2, swap=0, temp;

  dx = abs(x2 - x1);
  dy = abs(y2 - y1);
  s1 = sign(x2-x1);
  s2 = sign(y2-y1);

  /* Check if dx or dy has a greater range */
  /* if dy has a greater range than dx swap dx and dy */
  if(dy > dx){temp = dx; dx = dy; dy = temp; swap = 1;}

  /* Set the initial decision parameter and the initial point */
  d = 2 * dy - dx;
  x = x1;
  y = y1;

  int i;
  for(i = 1; i <= dx; i++)
  {
    setPixel(x,y);
    
    while(d >= 0) 
    {
      if(swap) x = x + s1;
      else 
      {
        y = y + s2;
        d = d - 2* dx;
      }
    }
    if(swap) y = y + s2;
    else x = x + s1;
    d = d + 2 * dy;
  }
  glFlush();
}

/* Function to draw a rhombus inscribed in a rectangle and roll */
/* number printed in it */
void draw(void)
{
  glClear(GL_COLOR_BUFFER_BIT);
 
  /* Draw rectangle */
  bres_general(20,40,620,40);
  bres_general(620,40,620,440);
  bres_general(620,440,20,440);
  bres_general(20,440,20,40);

  /* Draw rhombus */
  bres_general(320,440,20,240);
  bres_general(20,240,320,40);
  bres_general(320,40,620,240);
  bres_general(620,240,320,440);

  /* 1 */
  bres_general(250,150,250,250);
  /* 0 */
  bres_general(300,150,300,250);
  bres_general(300,250,400,250);
  bres_general(400,250,400,150);
  bres_general(400,150,300,150);

  glFlush();
}

void init() {  
  glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
  glutInitWindowPosition(0,0);
  glutInitWindowSize(640, 480);
  glutCreateWindow("Green Window");
  glClearColor(0.0,0.0,0.0,0);
  glColor3f(1.0,1.0,1.0);
  gluOrtho2D(0,640,0,480);
  
}

int main(int argc, char **argv) 
{
  glutInit(&argc, argv);
  init();
  glutDisplayFunc(draw);
  glutMainLoop();
  return 0;
}

Written by Munia Balayil

String replacement program in C

2014-12-01T04:04:00.000-08:00

A program to find a particular pattern in a string and replace all occurrences of that pattern with a new pattern to produce a modified string.



#include<stdio.h>
#include<string.h>

void main()
{
  char str[100], pattern[50], replace[50], new_str[100], temp[50];
  int l1, l2, l3, flag_eos = 0, pattern_found = 0;
  int i = 0, j, k, n;
  printf("\n###################################\n");
  printf("Enter any string\n");
  gets(str);
  printf("\n###################################\n");
  printf("Enter pattern to be replaced\n");
  gets(pattern);
  printf("\n###################################\n");
  printf("Enter new pattern\n");
  gets(replace);

  l1 = strlen(str);
  l2 = strlen(pattern);
  l3 = strlen(replace);
 
  while(flag_eos == 0)
  {
    for(; i < l1; i++)
      // if any character of str = first character of the pattern
      if((str[i] == pattern[0]) && (i + l2 - 1 < l1))
      {
        for(j = i, k = 0; j < i + l2; j++)
          temp[k++] = str[j];
        temp[k] = '\0';
        break;
      }
    if(i == l1)
    {
      flag_eos = 1;
      temp[0] = '\0';
    }
    if(strcmp(temp, pattern) == 0)
    {
      pattern_found = 1;
      n = 0;
      for(j = 0; j < i; j++)
        new_str[n++] = str[j];
      for(j = 0; j < l3; j++)
        new_str[n++] = replace[j];
      for(j = i + l2; j < l1; j++)
        new_str[n++] = str[j];
      new_str[n] = '\0';
      // Recompute the new string length and
      // continue to look for more occurrences
      strcpy(str, new_str);
      l1 = strlen(str);
    }
    else
      i = i + 1;
  }
  if(pattern_found == 1)
  {
    printf("\n###################################\n");
    printf("The modified string is \n");
    puts(str);
    printf("###################################\n");
  }
  else
  {
    printf("\n###################################\n");
    printf("Pattern not found in the string !!!\n");
    printf("###################################\n");
  }
}

Written by Munia Balayil

Implementation of DDA line drawing algorithm in OpenGL

2014-11-16T08:30:00.000-08:00

In computer graphics, a digital differential analyzer (DDA) is hardware or software used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. For more on DDA : Visit Digital Differential Analyzer - Wikipedia page. The following code is a DDA line drawing algorithm that draws a line between two given points.

#include <stdio.h>
#include <math.h>
#include <GL/glut.h>

double X1, Y1, X2, Y2;

float round_value(float v)
{
  return floor(v + 0.5);
}
void LineDDA(void)
{
  double dx=(X2-X1);
  double dy=(Y2-Y1);
  double steps;
  float xInc,yInc,x=X1,y=Y1;
  /* Find out whether to increment x or y */
  steps=(abs(dx)>abs(dy))?(abs(dx)):(abs(dy));
  xInc=dx/(float)steps;
  yInc=dy/(float)steps;

  /* Clears buffers to preset values */
  glClear(GL_COLOR_BUFFER_BIT);

  /* Plot the points */
  glBegin(GL_POINTS);
  /* Plot the first point */
  glVertex2d(x,y);
  int k;
  /* For every step, find an intermediate vertex */
  for(k=0;k<steps;k++)
  {
    x+=xInc;
    y+=yInc;
    /* printf("%0.6lf %0.6lf\n",floor(x), floor(y)); */
    glVertex2d(round_value(x), round_value(y));
  }
  glEnd();

  glFlush();
}
void Init()
{
  /* Set clear color to white */
  glClearColor(1.0,1.0,1.0,0);
  /* Set fill color to black */
  glColor3f(0.0,0.0,0.0);
  /* glViewport(0 , 0 , 640 , 480); */
  /* glMatrixMode(GL_PROJECTION); */
  /* glLoadIdentity(); */
  gluOrtho2D(0 , 640 , 0 , 480);
}
void main(int argc, char **argv)
{
  printf("Enter two end points of the line to be drawn:\n");
  printf("\n************************************");
  printf("\nEnter Point1( X1 , Y1):\n");
  scanf("%lf%lf",&X1,&Y1);
  printf("\n************************************");
  printf("\nEnter Point1( X2 , Y2):\n");
  scanf("%lf%lf",&X2,&Y2);
  
  /* Initialise GLUT library */
  glutInit(&argc,argv);
  /* Set the initial display mode */
  glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  /* Set the initial window position and size */
  glutInitWindowPosition(0,0);
  glutInitWindowSize(640,480);
  /* Create the window with title "DDA_Line" */
  glutCreateWindow("DDA_Line");
  /* Initialize drawing colors */
  Init();
  /* Call the displaying function */
  glutDisplayFunc(LineDDA);
  /* Keep displaying untill the program is closed */
  glutMainLoop();
}

Noise removal from foreground and background area in an image using opencv (python)

2013-08-29T01:11:00.000-07:00



import cv2
import numpy as np

# To display a single image in a window
# Window is destroyed on pressing any key
def display(windowName, image):
  cv2.namedWindow(windowName, 1)
  showtime(windowName, image)
  cv2.waitKey(0)
  cv2.destroyAllWindows()

# Read image
img = cv2.imread('imagename.jpg')
# Convert to grayscale image
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
display('gray', gray)
# Convert to binary image
ret,thresh = cv2.threshold(gray,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)
display('binary', thresh)

# noise removal
# to remove any small white noises use morphological opening
kernel = np.ones((3,3),np.uint8)
opening = cv2.morphologyEx(thresh,cv2.MORPH_OPEN,kernel, iterations = 2)
sure_bg = cv2.dilate(opening,kernel,iterations=3)
display('Sure Background', sure_bg)

dist_transform = cv2.distanceTransform(opening,cv.CV_DIST_L2,5)
ret, sure_fg = cv2.threshold(dist_transform,0.7*dist_transform.max(),255,0)
display('Sure Foreground', sure_fg)

# Finding unknown region
unknown = cv2.subtract(sure_bg,sure_fg)
display('unknown area', unknown)

For knowing more on morphological transformations using opening and closing refer Morphological Transformation

Written by Munia Balayil

Interview Question (Programming in C++)

2013-06-19T23:55:00.001-07:00

Give the output of the following program :


class Animal
{
  public :
  virtual void draw()
  {
    cout<<”Animal”;
  }
};
class Leopard : public Animal
{
  public :
  virtual void draw()
  {
    cout<<”Leopard”;
  }
};
main()
{
  Leopard l;
  Animal *a=&l;
  l.draw();
}

(A) Leopard (B) Animal (C) LeopardAnimal (D) AnimalLeopard

Answer :
(A) Leopard

Explanation :
The virtual keyword indicates to the compiler that it should choose the appropriate definition of the function draw not by the type of reference, but by the type of object that the reference refers to.
For more details on the use of virtual keyword : Reference

Written by Munia Balayil

Interview Question (Programming)

2013-06-19T22:55:00.000-07:00

What does the following function check?


bool f(unsigned int v)
{
  return ((v!=0)&&!(v & v-1));
}

(A) v is an odd number (B) v is a multiple of 2 (C) v is a power of 2 (D) v has a 0 bit

Answer :
(C) v is a power of 2

Explanation :
1) If v is a power of 2,

v is never 0 (even 2^0 = 1) and (v != 0) will always be 1(True).
(v & v-1) will always be 0(False) and hence their negation will always be 1(True).

2) If v is not a power of 2, either

v = 0, or
(v & v-1) is something other than 0 and their negation is 0(False)

Written by Munia Balayil

Cut the Gold Bar Twice and Pay for 7 Days - Puzzle#1

2013-06-05T23:22:00.000-07:00

Puzzle : You have a 7 inch gold bar with you. You need to pay the servant 1 inch gold per day of work. (At the end of first day, servant should have 1 inch gold; at the end of second day, he should have 2 inch gold and so on). You may take back some of the given pieces if needed. How will you do this with minimum number of cuts of the gold bar?

Answer : 2 cuts (i.e 3 pieces => a 4 inch piece, a 2 inch piece and a 1 inch piece)

Explanation : TB = Take back

Written by Munia Balayil

Convolution of Two Images (matrix form) - OpenCV - Python

2013-06-01T22:39:00.000-07:00

To perform convolution of two matrices


import cv2.cv as cv
import sys

if __name__ == '__main__':
  mat1 = cv.CreateMat(3, 3, 8)
  mat2 = cv.CreateMat(3, 3, 8)
  dst = cv.CreateImage(cv.GetSize(mat1), 8, 3)

  kernel = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
  matrix2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  for i in range(3):
    for j in range(3):
      mat1[i][j] = kernel[i][j]
  for i in range(3):
    for j in range(3):
      mat2[i][j] = matrix2[i][j]

  cv.NamedWindow("convolution", 1)
  cv.Filter2D(mat2, dst, mat1)
  cv.ShowImage('convolution', dst)

  print 'Press any key to quit'
  cv.WaitKey(0)
  print 'Exiting...'
  cv.DestroyAllWindows()
  sys.exit(0)

Written by Munia Balayil

Convolution of Two Images - OpenCV - Python

2013-06-01T22:36:00.000-07:00

# To convolute two images img1.bmp and img2.bmp

In mathematics and, in particular, functional analysis, convolution is a m-
athematical operation on two functions f and g, producing a third function
that is typically viewed as a modified version of one of the original func-
tions, giving the area overlap between the two functions as a function of 
the amount that one of the original functions is translated.
-Wikipedia


import cv2.cv as cv
import sys

if __name__ == "__main__":
 # Load two images
 im1 = cv.LoadImageM("img1.bmp")
 im2 = cv.LoadImageM("img2.bmp")
 # Create a destination image of the same size that of the source
 dst = cv.CreateImage(cv.GetSize(im1), 8, 3)

 # Create a window named "convolution(1 for colour)"
 cv.NamedWindow("convolution", 1)
 # Convolute the 2 images
 cv.Filter2D(im1, dst, im2)
 # Show the convoluted result
 cv.ShowImage('convolution', dst)

 # Wait for any key press to close the window
 print 'Press any key to quit'
 cv.WaitKey(0)
 # Destroy all created windows and exit
 print 'Exiting...'
 cv.DestroyAllWindows()
 sys.exit(0)

Written by Munia Balayil

GATE 2013 - Papers, Answer Keys and Solutions

2013-03-29T04:54:00.000-07:00

GATE 2013 Question papers and the corresponding answer keys are now available for download. These are the official questions papers and answer keys provided by IITB. They are also available from IITB GATE 2013 website.

Computer Science & Information Technology

Question Papers

Answer Key

Written by Code Blocks
Information courtesy: IITB GATE 2013 Website

GATE 2013 - CS/IT Question Papers, Answer Keys and Solutions

2013-03-29T04:46:00.001-07:00

GATE 2013 Computer Science and Information Technology Question Papers are available under 4 paper codes; A, B, C & D. All of them have the same questions (both in number and content) but presented in different order. You can view the questions papers here or download for offline use by clicking the corresponding "Download" button.

«Paper Code A» «Paper Code B» «Paper Code C» «Paper Code D» «Answer Keys»

Bellman-Ford Algorithm - Shortest Path Algorithm

2013-01-07T20:25:00.000-08:00

"The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr.

Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. However, if a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a shortest path. In such a case, the Bellman-Ford algorithm can detect negative cycles and report their existence, but it cannot produce a correct "shortest path" answer if a negative cycle is reachable from the source." - Wikipedia


INITIALISE_SINGLE_SOURCE(G, start)
{
  for each vertex v ∈ v(G)
    dist[v] <- ∞
    pred[v] <- NIL
  dist[start] <- 0
}
// dist[v] <- distance of vertex "v" from vertex "start"
// pred[v] <- predecessor of "v" in the shortest path 
//            from "start"

RELAX(u, v, cost)
{
  if dist[v] > dist[u] + cost[u, v]
    dist[v] <- dist[u] + cost[u, v]
    pred[v] <- u
} 

BELLMAN_FORD(G, cost, start)
{
  INITIALISE_SINGLE_SOURCE(G, start)
  for i <- 1 to |v(G)| - 1
    do for each edge (u, v) ∈ E[G]
      do RELAX(u, v, cost)
  for each edge (u, v) ∈ E[G]
    do if dist[v] > dist[u] + cost[u, v]
      then return FALSE
  return TRUE
}

Written by Munia Balayil
Image courtesy - ArsRout

Dijkstra's Algorithm - Shortest Path Algorithm

2013-01-05T00:32:00.000-08:00

"Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, producing a shortest path tree.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined." - Wikipedia


INITIALISE_SINGLE_SOURCE(G, start)
{
  for each vertex v ∈ v(G)
    dist[v] <- ∞
    pred[v] <- NIL
  dist[start] <- 0
}
// dist[v] <- distance of vertex "v" from vertex "start"
// pred[v] <- predecessor of "v" in the shortest path 
//            from "start"

RELAX(u, v, cost)
{
  if dist[v] > dist[u] + cost[u, v]
    dist[v] <- dist[u] + cost[u, v]
    pred[v] <- u
} 

DIJKSTRA(G, cost, start)
{
  INITIALISE_SINGLE_SOURCE(G, start)
  S <- φ
  Q <- V[G]
  while Q ≠ φ do
    u <- EXTRACT_MIN(Q)
    S <- S U {u}
    for each vertex v ∈ Adj[u]
      do RELAX(u, v, cost)
}
// S <- Set of vertices whose final shortest path weights
//      from the source (start) have already been determined
// Q <- min_priority queue of vertices, keyed by their 'dist'
//      values

Written by Munia Balayil

Cloud Computing - Characteristics, Service Models & Deployment Models

2012-12-04T08:31:00.002-08:00

Cloud computing is a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. This cloud model is composed of five essential characteristics, three service models, and four deployment models.

Visual Model of Cloud Computing

Essential Characteristics:

On-demand self-service: A consumer can unilaterally provision computing capabilities, such as server time and network storage, as needed automatically without requiring human interaction with each service provider.

Broad network access: Capabilities are available over the network and accessed through standard mechanisms that promote use by heterogeneous thin or thick client platforms (e.g., mobile phones, tablets, laptops, and workstations).

Resource pooling: The provider’s computing resources are pooled to serve multiple consumers using a multi-tenant model, with different physical and virtual resources dynamically assigned and reassigned according to consumer demand. There is a sense of location independence in that the customer generally has no control or knowledge over the exact location of the provided resources but may be able to specify location at a higher level of abstraction (e.g., country, state, or datacenter). Examples of resources include storage, processing, memory, and network bandwidth.

Rapid elasticity: Capabilities can be elastically provisioned and released, in some cases automatically, to scale rapidly outward and inward commensurate with demand. To the consumer, the capabilities available for provisioning often appear to be unlimited and can be appropriated in any quantity at any time.

Measured service: Cloud systems automatically control and optimize resource use by leveraging a metering capability at some level of abstraction appropriate to the type of service (e.g., storage, processing, bandwidth, and active user accounts). Resource usage can be monitored, controlled, and reported, providing transparency for both the provider and consumer of the utilized service.

Service Models:

Software as a Service (SaaS): The capability provided to the consumer is to use the provider’s applications running on a cloud infrastructure. The applications are accessible from various client devices through either a thin client interface, such as a web browser (e.g., web-based email), or a program interface. The consumer does not manage or control the underlying cloud infrastructure including network, servers, operating systems, storage, or even individual application capabilities, with the possible exception of limited userspecific application configuration settings.

Platform as a Service (PaaS): The capability provided to the consumer is to deploy onto the cloud infrastructure consumer-created or acquired applications created using programming languages, libraries, services, and tools supported by the provider. The consumer does not manage or control the underlying cloud infrastructure including network, servers, operating systems, or storage, but has control over the deployed applications and possibly configuration settings for the application-hosting environment.

Infrastructure as a Service (IaaS): The capability provided to the consumer is to provision processing, storage, networks, and other fundamental computing resources where the consumer is able to deploy and run arbitrary software, which can include operating systems and applications. The consumer does not manage or control the underlying cloud infrastructure but has control over operating systems, storage, and deployed applications; and possibly limited control of select networking components (e.g., host firewalls).

Deployment Models:

Private cloud: The cloud infrastructure is provisioned for exclusive use by a single organization comprising multiple consumers (e.g., business units). It may be owned, managed, and operated by the organization, a third party, or some combination of them, and it may exist on or off premises.

Community cloud: The cloud infrastructure is provisioned for exclusive use by a specific community of consumers from organizations that have shared concerns (e.g., mission, security requirements, policy, and compliance considerations). It may be owned, managed, and operated by one or more of the organizations in the community, a third party, or some combination of them, and it may exist on or off premises.

Public cloud: The cloud infrastructure is provisioned for open use by the general public. It may be owned, managed, and operated by a business, academic, or government organization, or some combination of them. It exists on the premises of the cloud provider.

Hybrid cloud: The cloud infrastructure is a composition of two or more distinct cloud infrastructures (private, community, or public) that remain unique entities, but are bound together by standardized or proprietary technology that enables data and application portability (e.g., cloud bursting for load balancing between clouds).

References:

Written by Munia Balayil

GATE 2013 Materials - Books, Solved Question Paper Banks & Guides

2012-11-17T01:12:00.001-08:00

Snapdeal has discounts running on GATE 2013 preparatory materials - Guides, 10 Years Solved Question Banks etc. It is available at the following location

Snapdeal - Competitive Exam Books: Buy Entrance Exams Preparation Books Online

Written by Code Blocks

Prim's Algorithm - Minimum Cost Spanning Tree problem

2012-11-13T07:39:00.000-08:00

"Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm." - Wikipedia


1. MST_PRIM(G, cost, root)
2.   for each vertex u ∈ V[G]
3.     do Key[u] <- ∞
4.        Pred[u] <- NIL
5.   Key[root] <- 0
6.   Q <- V[G] // create a priority queue of the vertices
7.   while Q ≠ φ
8.     do u <- EXTRACT_MIN(Q)
9.       for each v ∈ Adj[u]
10.        do if v ∈ Q & (cost(u,v) < Key[v])
11.          then Pred[v] <- u
12.               Key[v] <- cost(u,v)

Key[v] -> minimum weight of any edge connecting v to a vertex in the tree

Pred[v] -> parent of v in the tree

Q -> min priority queue of all the vertices that are not in the tree

Initially, A = { (v, Pred[v]) : v ∈ V - {root} - Q }
Finally, A = { (v, Pred[v] : v ∈ V - {root} } // Q is empty

References :

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil

Kruskal's Algorithm - Minimum Cost Spanning Tree Problem

2012-11-12T09:21:00.002-08:00

"Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component)." - Wikipedia


1. MST_KRUSKAL(G, cost)
2.   A -> φ
3.   for each vertex v ∈ V[G]
4.     do MAKE-SET(v)
5.   sort the edges of E into non-decreasing order by weight
6.   for each edge (u,v) ∈ E taken in non-decreasing order by weight
7.     do if FIND-SET(u) ≠ FIND-SET(v)
8.       then A <- A ∪ { (u,v) }
9.         UNION(u,v)
10.  return A

MAKE-SET(x) -> creates a new set (tree) whose only
member is x (creates disjoint sets)

UNION(x,y) -> unites the dynamic sets that contain x & y, 
say S_x & S_y into a new set that is the union of these two sets 
S_x & S_y are assumed to be disjoint prior to this operation

FIND-SET(x) -> return a pointer to the representative of the set
containing x (here the root of the tree to which it belongs to)

References :

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil