Thursday, July 24, 2014

Opengl,C++ : 3D Rotation Cube


1.    Define the above cube using two separate lists: a vertex list and a face list.
2.    Rotate the given cube using the arrow keys.
 #include <windows.h>  
 #include <gl/Gl.h>  
 #include <gl/glut.h>  
 #include <cmath>   
 typedef struct{float x;float y;}Point2D;  
 float dx = 200, dy = 200, dz = 200;  
 /* Vertex indices for the 6 faces of a cube. */   
 GLint faces[6][4] = {  
      {0, 1, 2, 3}, {3, 2, 6, 7}, {7, 6, 5, 4},  
      {4, 5, 1, 0}, {5, 6, 2, 1}, {7, 4, 0, 3}   
 };  
 GLfloat v[8][3];  
 void init(void)  
 {  
      v[0][0] = v[1][0] = v[2][0] = v[3][0] = 100;  
      v[4][0] = v[5][0] = v[6][0] = v[7][0] = 300;  
      v[0][1] = v[1][1] = v[4][1] = v[5][1] = 100;  
      v[2][1] = v[3][1] = v[6][1] = v[7][1] = 300;  
      v[0][2] = v[3][2] = v[4][2] = v[7][2] = 300;  
      v[1][2] = v[2][2] = v[5][2] = v[6][2] = 100;  
 }  
 Point2D Project_ortho(float x, float y, float z){  
      Point2D p0;  
      p0.x = x ;  
      p0.y = y ;  
      return p0;  
 }  
 void drawBox(void)  
 {  
      Point2D p0,p1,p2,p3;  
      for (int f = 0; f < 6; f++) {  
           p0 = Project_ortho(v[ faces[f][0] ][0],v[ faces[f][0] ][1],v[ faces[f][0] ][2]);  
           p1 = Project_ortho(v[ faces[f][1] ][0],v[ faces[f][1] ][1],v[ faces[f][1] ][2]);  
           p2 = Project_ortho(v[ faces[f][2] ][0],v[ faces[f][2] ][1],v[ faces[f][2] ][2]);  
           p3 = Project_ortho(v[ faces[f][3] ][0],v[ faces[f][3] ][1],v[ faces[f][3] ][2]);  
           glBegin(GL_LINE_LOOP);  
                glVertex2f(p0.x,p0.y);  
                glVertex2f(p1.x,p1.y);  
                glVertex2f(p2.x,p2.y);  
                glVertex2f(p3.x,p3.y);  
           glEnd();  
           glFlush();       
      }  
 }  
 void translate(float* x, float* y, float* z, float dx, float dy, float dz){  
      float tx = *x, ty=*y, tz=*z;  
      *x = tx + dx;  
      *y = ty + dy;  
      *z = tz + dz;  
 }   
 void rotatex(float* x, float* y, float* z, float ang){  
      ang = ang * 3.14 / 180.0;                         //angle in radians   
      float tx = *x, ty=*y, tz=*z;  
      *y = ty * cos(ang) - tz * sin(ang);  
      *z = ty * sin(ang) + tz * cos(ang);  
      *x = tx;   
 }   
 void rotatey(float* x, float* y, float* z, float ang){  
      ang = ang * 3.14 / 180.0;                         //angle in radians   
      float tx = *x, ty=*y, tz=*z;  
      *x = tx * cos(ang) + tz * sin(ang);  
      *z = -tx * sin(ang) + tz * cos(ang);  
      *y = ty;  
 }   
 void rotatebox_x(float deg_x){  
      for (int i = 0; i < 8; i++) {  
           translate(&v[i][0],&v[i][1],&v[i][2], -dx,-dy,-dz);  
           rotatex(&v[i][0],&v[i][1],&v[i][2], deg_x);  
           translate(&v[i][0],&v[i][1],&v[i][2], dx,dy,dz);  
      }  
      glutPostRedisplay();  
 }  
 void rotatebox_y(float deg_y){  
      for (int i = 0; i < 8; i++) {  
           translate(&v[i][0],&v[i][1],&v[i][2], -dx,-dy,-dz);  
           rotatey(&v[i][0],&v[i][1],&v[i][2], deg_y);  
           translate(&v[i][0],&v[i][1],&v[i][2], dx,dy,dz);  
      }  
      glutPostRedisplay();  
 }  
 void keyboard(unsigned char key, int x, int y)  
 {  
      if (key == 'q' || key == 'Q')  
           exit(EXIT_SUCCESS);  
 }  
 void special(int key, int, int) {  
      switch (key) {  
      case GLUT_KEY_LEFT: rotatebox_y(-1); break;  
      case GLUT_KEY_RIGHT: rotatebox_y(1);break;  
      case GLUT_KEY_UP: rotatebox_x(-1);break;  
      case GLUT_KEY_DOWN: rotatebox_x(1);break;  
      default: return;  
      }  
 }  
 void myDisplay()  
 {  
      glClearColor(1.0f, 1.0f, 1.0f, 0.0f);   
      glClear(GL_COLOR_BUFFER_BIT);  
      glColor3f(0.0f, 0.0f, 0.0f);  
      drawBox();  
 }  
 int main( int argc, char ** argv ) {  
      glutInit( &argc, argv );  
      glutInitWindowPosition( 0, 0 );  
      glutInitWindowSize( 800, 600 );  
      glutCreateWindow( "3D Rotation Cube" );  
      glMatrixMode( GL_PROJECTION );   
      glLoadIdentity();  
      gluOrtho2D( 0, 800, 0, 600 );  
      glViewport(0, 0, 800, 600);  
      init();  
      glutKeyboardFunc(keyboard);   
      glutSpecialFunc(special);  
      glutDisplayFunc( myDisplay );  
      glutMainLoop();  
      return( 0 );  
 }  

Opengl,C++ : Standard perspective projection

1.    Project the cube on the XY plane with the COP is at (0,0,-200) and moves to the centre of the screen [i.e., move the system to (WinWidth/2, WinHeight/2)]
2.    3D Translation to project the cube with COP is at (100,100,-200).
 #include <windows.h>  
 #include <gl/Gl.h>  
 #include <gl/glut.h>  
 #include <cmath>   
 int WinWidth = 500, WinHeight = 500;  
 typedef struct{float x;float y;}Point2D;  
 typedef struct{float x;float y;float z;}Point3D;  
 Point3D COP = {0,0,-200};     // Centre Of Projection is at (0,0,-200)  
 Point3D COP1 = {100,100,-200};  
 Point3D A,B,C,D,E,F,G,H;     // Vertices of the cube  
 void InitCube(){  
      A.x = 0; A.y = 0; A.z = 0;               // A(0,0,0)  
      B.x = 200; B.y = 0; B.z = 0;          // B(200,0,0)  
      C.x = 200; C.y = 200; C.z = 0;          // C(200,200,0)  
      D.x = 0; D.y = 200; D.z = 0;          // D(0,200,0)  
      E.x = 0; E.y = 200; E.z = 200;          // E(0,200,200)  
      F.x = 0; F.y = 0; F.z = 200;          // F(0,0,200)  
      G.x = 200; G.y = 0; G.z = 200;          // G(200,0,200)  
      H.x = 200; H.y = 200; H.z = 200;     // H(200,200,200)  
 }  
 void DrawCube(Point2D A, Point2D B, Point2D C, Point2D D, Point2D E, Point2D F, Point2D G, Point2D H){  
      glPointSize(1.0);  
      glBegin(GL_LINE_LOOP);       
      //DRAWING FRONT FACE  
           glVertex2i(A.x, A.y); glVertex2i(B.x, B.y);     glVertex2i(C.x, C.y); glVertex2i(D.x, D.y);  
      glEnd();  
      glBegin(GL_LINE_LOOP);  
      //DRAWING BACK FACE  
           glVertex2i(E.x, E.y); glVertex2i(F.x, F.y);     glVertex2i(G.x, G.y); glVertex2i(H.x, H.y);  
      glEnd();  
      glBegin(GL_LINES);  
      //DRAWING OTHER LINES  
           glVertex2i(A.x, A.y); glVertex2i(F.x, F.y);  
           glVertex2i(B.x, B.y); glVertex2i(G.x, G.y);  
           glVertex2i(C.x, C.y); glVertex2i(H.x, H.y);  
           glVertex2i(D.x, D.y); glVertex2i(E.x, E.y);  
      glEnd();  
      glFlush();  
 }  
 Point2D Project_Perspective(Point3D p, Point3D CoP){  
      Point2D p2;  
      float d = abs(CoP.z);     // The distance between the COP and orign  
      p2.x=(d*p.x)/(p.z+d);  
      p2.y=(d*p.y)/(p.z+d);  
      //.....wite necessary equations here for perspective transformation  
      return p2;  
 }  
 Point2D translate2D(Point2D p, float tx, float ty){  
   Point2D tp2;  
      //.....wite the equations for 2D translation  
      tp2.x=p.x+tx;  
      tp2.y=p.y+ty;  
      return tp2;  
 }   
 Point3D translate3D(Point3D p, float tx, float ty, float tz){  
   Point3D tp3;  
      //.....wite the equations for 3D translation  
      tp3.x=p.x+tx;  
      tp3.y=p.y+ty;  
      tp3.z=p.z+tz;  
      return tp3;  
 }   
 void keyboard(unsigned char key, int x, int y)  
 {  
   if (key == 'q' || key == 'Q')  
     exit(EXIT_SUCCESS);  
 }  
 void myMouse(int button, int state, int x, int y) {  
      if(state == GLUT_DOWN)   
      {  
           if(button == GLUT_LEFT_BUTTON)   
           {  
                Point2D     Projected_A=Project_Perspective(A,COP);       
                Point2D     Projected_B=Project_Perspective(B,COP);  
                Point2D     Projected_C=Project_Perspective(C,COP);  
                Point2D     Projected_D=Project_Perspective(D,COP);  
                Point2D     Projected_E=Project_Perspective(E,COP);  
                Point2D     Projected_F=Project_Perspective(F,COP);  
                Point2D     Projected_G=Project_Perspective(G,COP);  
                Point2D     Projected_H=Project_Perspective(H,COP);  
                DrawCube(  
                // Calculate the following values  
                //Answer for Q1  
                translate2D(Projected_A,WinWidth/2, WinHeight/2),       
                translate2D(Projected_B,WinWidth/2, WinHeight/2),  
                translate2D(Projected_C,WinWidth/2, WinHeight/2),  
                translate2D(Projected_D,WinWidth/2, WinHeight/2),  
                translate2D(Projected_E,WinWidth/2, WinHeight/2),  
                translate2D(Projected_F,WinWidth/2, WinHeight/2),  
                translate2D(Projected_G,WinWidth/2, WinHeight/2),  
                translate2D(Projected_H,WinWidth/2, WinHeight/2));  
           }  
           else if (button == GLUT_RIGHT_BUTTON)   
           {  
                 DrawCube(  
           //Answer for Q2   
           translate2D(Project_Perspective(translate3D(A,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(B,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(C,-100,-100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(D,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(E,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(F,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(G,-100,-100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(H,-100, -100,0),COP1),WinWidth/2, WinHeight/2)  
                );  
           }  
      }  
 }  
 void myDisplay()  
 {  
      glClearColor(1.0f, 1.0f, 1.0f, 0.0f);   
      glClear(GL_COLOR_BUFFER_BIT);  
      glColor3f(0.0f, 0.0f, 0.0f);  
 }  
 int main( int argc, char ** argv ) {  
      glutInit( &argc, argv );  
      glutInitWindowPosition( 0, 0 );  
      glutInitWindowSize( WinWidth, WinHeight );  
      glutCreateWindow( "Projection of a Cube" );  
      glMatrixMode( GL_PROJECTION );   
      glLoadIdentity();  
      gluOrtho2D( 0, WinWidth, 0, WinHeight );  
      glViewport(0, 0, WinWidth, WinHeight);  
      InitCube();  
      glutKeyboardFunc(keyboard);   
      glutMouseFunc( myMouse );  
      glutDisplayFunc( myDisplay );  
      glutMainLoop();  
      return( 0 );  
 }  

Monday, July 21, 2014

Solve Three Missionaries and Three cannibals Problem Using Prolog

 % Main control block and printing  
   
 find :-  
   path([3,3,left],[0,0,right],[[3,3,left]],_).  
   
 output([]) :- nl, nl.  
 output([[A,B,String]|T]) :-  
 output(T),  
      write(B), write(' ~~ '), write(A), write(': '), write(String), nl.  
   
   
 % Base case  
 path([A,B,C],[A,B,C],_,MoveList):-  
 nl,nl,output(MoveList).  
   
   
 % Recursive call to solve the problem  
 path([A,B,C],[D,E,F],Traversed,Moves) :-  
   move([A,B,C],[I,J,K],Out),  
   legal([I,J,K]),  
 % Don't use this move unless it's safe.  
   
   not(member([I,J,K],Traversed)),  
   path([I,J,K],[D,E,F],[[I,J,K]|Traversed],[ [[I,J,K],[A,B,C],Out] | Moves ]).  
   
   
   
 % Move commands and descriptions of the move  
   
 move([A,B,left],[C,B,right],'One missionary crosses the river') :-  
   A > 0, C is A - 1.  
 move([A,B,left],[C,B,right],'Two missionaries cross the river') :-  
   A > 1, C is A - 2.  
 move([A,B,left],[C,D,right],'One missionary and One cannibal cross the river') :-  
   A > 0, B > 0, C is A - 1, D is B - 1.  
 move([A,B,left],[A,D,right],'One cannibal crosses the river') :-  
   B > 0, D is B - 1.  
 move([A,B,left],[A,D,right],'Two cannibals cross the river') :-  
   B > 1, D is B - 2.  
 move([A,B,right],[C,B,left],'One missionary returns from the other side') :-  
   A < 3, C is A + 1.  
 move([A,B,right],[C,B,left],'Two missionaries return from the other side') :-  
   A < 2, C is A + 2.  
 move([A,B,right],[C,D,left],'One missionary and One cannibal return from the other side') :-  
   A < 3, B < 3, C is A + 1, D is B + 1.  
 move([A,B,right],[A,D,left],'One cannibal returns from the other side') :-  
   B < 3, D is B + 1.  
 move([A,B,right],[A,D,left],'Two cannibals return from the other side') :-  
   B < 2, D is B + 2.  
   
 % Legal move definition where B is missionaries and A is cannibals:  
   
 legal([B,A,_]) :-  
   (A =< B ; B = 0),  
   C is 3-A, D is 3-B,  
   (C =< D; D = 0).  
   

Friday, July 18, 2014

Opengl,C++ : Scratch code for the standard perspective projection

 #include <windows.h>  
 #include <gl/Gl.h>  
 #include <gl/glut.h>  
 #include <cmath>   
   
 int WinWidth = 500, WinHeight = 500;  
   
 typedef struct{float x;float y;}Point2D;  
 typedef struct{float x;float y;float z;}Point3D;  
   
 Point3D COP = {0,0,-200};     // Centre Of Projection is at (0,0,-200)  
 Point3D COP1 = {100,100,-200};  
 Point3D A,B,C,D,E,F,G,H;     // Vertices of the cube  
   
 void InitCube(){  
      A.x = 0; A.y = 0; A.z = 0;               // A(0,0,0)  
      B.x = 200; B.y = 0; B.z = 0;          // B(200,0,0)  
      C.x = 200; C.y = 200; C.z = 0;          // C(200,200,0)  
      D.x = 0; D.y = 200; D.z = 0;          // D(0,200,0)  
   
      E.x = 0; E.y = 200; E.z = 200;          // E(0,200,200)  
      F.x = 0; F.y = 0; F.z = 200;          // F(0,0,200)  
      G.x = 200; G.y = 0; G.z = 200;          // G(200,0,200)  
      H.x = 200; H.y = 200; H.z = 200;     // H(200,200,200)  
 }  
   
 void DrawCube(Point2D A, Point2D B, Point2D C, Point2D D, Point2D E, Point2D F, Point2D G, Point2D H){  
      glPointSize(1.0);  
   
      glBegin(GL_LINE_LOOP);       
      //DRAWING FRONT FACE  
           glVertex2i(A.x, A.y); glVertex2i(B.x, B.y);     glVertex2i(C.x, C.y); glVertex2i(D.x, D.y);  
      glEnd();  
   
      glBegin(GL_LINE_LOOP);  
      //DRAWING BACK FACE  
           glVertex2i(E.x, E.y); glVertex2i(F.x, F.y);     glVertex2i(G.x, G.y); glVertex2i(H.x, H.y);  
      glEnd();  
        
      glBegin(GL_LINES);  
      //DRAWING OTHER LINES  
           glVertex2i(A.x, A.y); glVertex2i(F.x, F.y);  
   
           glVertex2i(B.x, B.y); glVertex2i(G.x, G.y);  
   
           glVertex2i(C.x, C.y); glVertex2i(H.x, H.y);  
   
           glVertex2i(D.x, D.y); glVertex2i(E.x, E.y);  
      glEnd();  
   
      glFlush();  
 }  
   
 Point2D Project_Perspective(Point3D p, Point3D CoP){  
      Point2D p2;  
      float d = abs(CoP.z);     // The distance between the COP and orign  
      p2.x=(d*p.x)/(p.z+d);  
      p2.y=(d*p.y)/(p.z+d);  
   
      //.....wite necessary equations here for perspective transformation  
        
      return p2;  
 }  
   
 Point2D translate2D(Point2D p, float tx, float ty){  
   Point2D tp2;  
      //.....wite the equations for 2D translation  
      tp2.x=p.x+tx;  
      tp2.y=p.y+ty;  
      return tp2;  
 }   
   
 Point3D translate3D(Point3D p, float tx, float ty, float tz){  
   Point3D tp3;  
      //.....wite the equations for 3D translation  
      tp3.x=p.x+tx;  
      tp3.y=p.y+ty;  
      tp3.z=p.z+tz;  
      return tp3;  
 }   
   
 void keyboard(unsigned char key, int x, int y)  
 {  
   if (key == 'q' || key == 'Q')  
     exit(EXIT_SUCCESS);  
 }  
   
 void myMouse(int button, int state, int x, int y) {  
      if(state == GLUT_DOWN)   
      {  
           if(button == GLUT_LEFT_BUTTON)   
           {  
           /*     Point2D translateA=translate2D(Projected_A,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_B,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_C,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_D,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_E,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_F,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_G,WinWidth/2, WinHeight/2);  
                Point2D translateA=translate2D(Projected_H,WinWidth/2, WinHeight/2);*/  
           }  
           else if (button == GLUT_RIGHT_BUTTON)   
           {  
                   
           }  
      }  
 }  
   
 void myDisplay()  
 {  
      glClearColor(1.0f, 1.0f, 1.0f, 0.0f);   
      glClear(GL_COLOR_BUFFER_BIT);  
      glColor3f(0.0f, 0.0f, 0.0f);  
        
      Point2D     Projected_A=Project_Perspective(A,COP);       
      Point2D     Projected_B=Project_Perspective(B,COP);  
      Point2D     Projected_C=Project_Perspective(C,COP);  
      Point2D     Projected_D=Project_Perspective(D,COP);  
      Point2D     Projected_E=Project_Perspective(E,COP);  
      Point2D     Projected_F=Project_Perspective(F,COP);  
      Point2D     Projected_G=Project_Perspective(G,COP);  
      Point2D     Projected_H=Project_Perspective(H,COP);  
   
      DrawCube(  
           // Calculate the following values  
           //Q1  
           /*translate2D(Projected_A,WinWidth/2, WinHeight/2),       
           translate2D(Projected_B,WinWidth/2, WinHeight/2),  
           translate2D(Projected_C,WinWidth/2, WinHeight/2),  
           translate2D(Projected_D,WinWidth/2, WinHeight/2),  
           translate2D(Projected_E,WinWidth/2, WinHeight/2),  
           translate2D(Projected_F,WinWidth/2, WinHeight/2),  
           translate2D(Projected_G,WinWidth/2, WinHeight/2),  
           translate2D(Projected_H,WinWidth/2, WinHeight/2)*/  
   
           //Q3  
           translate2D(Project_Perspective(translate3D(A,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(B,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(C,-100,-100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(D,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(E,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(F,-100, -100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(G,-100,-100,0),COP1),WinWidth/2, WinHeight/2),  
           translate2D(Project_Perspective(translate3D(H,-100, -100,0),COP1),WinWidth/2, WinHeight/2)  
      );  
 }  
   
   
 int main( int argc, char ** argv ) {  
      glutInit( &argc, argv );  
      glutInitWindowPosition( 0, 0 );  
      glutInitWindowSize( WinWidth, WinHeight );  
      glutCreateWindow( "Projection of a Cube" );  
   
      glMatrixMode( GL_PROJECTION );   
      glLoadIdentity();  
      gluOrtho2D( 0, WinWidth, 0, WinHeight );  
      glViewport(0, 0, WinWidth, WinHeight);  
   
      InitCube();  
   
      glutKeyboardFunc(keyboard);   
      glutMouseFunc( myMouse );  
      glutDisplayFunc( myDisplay );  
      glutMainLoop();  
   
      return( 0 );  
 }  

Opengl,C++ : Line_clipping scratch code using midpoint subdivision method

 #include <windows.h>  
 #include <gl/Gl.h>  
 #include <gl/glut.h>  
   
 int screenheight = 600;  
 int screenwidth = 800;  
 bool flag = true;  
   
 int x0 = 0,y0 =0 ,x1 =0 ,y1=0 ;  
 int xmin;int ymin;int xmax;int ymax;  
   
 void DrawRect(int x0, int y0, int x1, int y1)  
 {  
      glClear(GL_COLOR_BUFFER_BIT);  
      glRecti(x0,y0,x1,y1);  
      glFlush();  
 }  
   
 void DrawLineSegment(int x0, int y0, int x1, int y1){  
      glColor3d(1,0,0);  
      glBegin(GL_LINES);  
           glVertex2i(x0,y0);  
           glVertex2i(x1,y1);  
      glEnd();  
      glFlush();  
 }  
   
 typedef int OutCode;  
   
 const int INSIDE = 0; // 0000  
 const int BOTTOM = 1;  // 0001  
 const int RIGHT = 2; // 0010  
 const int TOP = 4; // 0100  
 const int LEFT = 8;  // 1000  
   
 OutCode ComputeOutCode(int x, int y)  
 {  
      OutCode code;  
   
      code = INSIDE;     // initialised as being inside of clip window  
   
      if (x < xmin)      // to the left of clip window  
           code |= LEFT;  
      else if (x > xmax)      // to the left of clip window  
           code |= RIGHT;  
      else if (y < ymin)      // to the left of clip window  
           code |= BOTTOM;// Complete the code segment here  
      else if (y > ymax)      // to the left of clip window  
           code |= TOP;  
 return(code);  
 }  
   
 void lineclip(int x0,int y0,int x1,int y1) {  
  OutCode code0,code1;  
  int midx,midy;  
   
  if(abs(x0-x1)==1 && abs(y0-y1)==1) /*Adjacent points */  
   return;  
    
  code0=ComputeOutCode(x0,y0);  
  code1=ComputeOutCode(x1,y1);  
  if( !(code0 | code1) ) { /*The two points are completely inside the window*/  
   DrawLineSegment(x0,y0,x1,y1);  
   return;  
  }  
  else if(code0 & code1) /*The two points are completely outside the window.*/  
           return ;  
   
  midx=(x0+x1)/2;  
  midy=(y0+y1)/2;  
  lineclip(midx,midy,x1,y1);  
  lineclip(x0,y0,midx,midy);  
 }  
   
 void myMouse(int button, int state, int x, int y) {  
      glPointSize(5.0);  
      if(state == GLUT_DOWN)   
      {  
           if(button == GLUT_LEFT_BUTTON)   
           {  
                if (flag){  
                     x0 = x;  
                     y0 = screenheight - y;  
                     flag = false;  
                } else {  
                     x1 = x;  
                     y1 = screenheight - y;  
                     lineclip(x0,y0,x1,y1);  
                     flag = true;  
                }  
           }  
           else if (button == GLUT_RIGHT_BUTTON)   
           {  
                if (flag){  
                     x0 = x;  
                     y0 = screenheight - y;  
                     flag = false;  
                } else {  
                     x1 = x;  
                     y1 = screenheight - y;  
                     glColor3d(1,1,0);  
                     DrawRect(x0,y0,x1,y1);  
                     xmin=x0;  
                     xmax=x1;  
                     ymin=y0;                      
                     ymax=y1;  
                     flag = true;  
                }  
           }  
      }  
 }  
   
   
 void myDisplay()  
 {  
      glClearColor(0.0f, 0.0f, 0.0f, 0.0f); //black  
      glClear(GL_COLOR_BUFFER_BIT);  
      glFlush();  
 }  
   
 int main( int argc, char ** argv ) {  
   
      glutInit( &argc, argv );  
      glutInitWindowPosition( 0, 0 );  
      glutInitWindowSize( 800, 600 );  
   
      // create window  
      glutCreateWindow( "midpoint subdivision method Clipping" );  
   
      // set the view frustum  
      glMatrixMode( GL_PROJECTION );   
      glLoadIdentity();  
      gluOrtho2D( 0, 800, 0, 600 );  
   
      // clear rendering surface  
      glViewport(0, 0, 800, 600);  
   
      glutMouseFunc( myMouse );  
      glutDisplayFunc( myDisplay );  
      glutMainLoop();  
   
      return( 0 );  
 }  

Opengl,C++ : Line_clipping scratch code using Cohen-Sutherland Line Clipping method

 #include <windows.h>  
 #include <gl/Gl.h>  
 #include <gl/glut.h>  
   
 int screenheight = 600;  
 int screenwidth = 800;  
 bool flag = true;  
   
 int x0 = 0,y0 =0 ,x1 =0 ,y1=0 ;  
 int xmin;int ymin;int xmax;int ymax;  
   
 void DrawRect(int x0, int y0, int x1, int y1)  
 {  
      glClear(GL_COLOR_BUFFER_BIT);  
      glRecti(x0,y0,x1,y1);  
      glFlush();  
 }  
   
 void DrawLineSegment(int x0, int y0, int x1, int y1){  
      glColor3d(1,0,0);  
      glBegin(GL_LINES);  
           glVertex2i(x0,y0);  
           glVertex2i(x1,y1);  
      glEnd();  
      glFlush();  
 }  
   
 typedef int OutCode;  
   
 const int INSIDE = 0; // 0000  
 const int BOTTOM = 1;  // 0001  
 const int RIGHT = 2; // 0010  
 const int TOP = 4; // 0100  
 const int LEFT = 8;  // 1000  
   
 OutCode ComputeOutCode(int x, int y)  
 {  
      OutCode code;  
   
      code = INSIDE;     // initialised as being inside of clip window  
   
      if (x < xmin)      // to the left of clip window  
           code |= LEFT;  
      else if (x > xmax)      // to the left of clip window  
           code |= RIGHT;  
      else if (y < ymin)      // to the left of clip window  
           code |= BOTTOM;// Complete the code segment here  
      else if (y > ymax)      // to the left of clip window  
           code |= TOP;  
 return(code);  
 }  
   
 void CohenSutherlandLineClip (int x0, int y0, int x1, int y1)  
 {  
      // Complete the code segment here  
      OutCode outcode0=ComputeOutCode(x0,y0);  
      OutCode outcode1=ComputeOutCode(x1,y1);  
   
      bool accept=false;  
   
      while (true) {  
           if (!(outcode0 | outcode1)) {//Bitwise OR is 0. Trivially accept  
                accept = true;  
                break;  
           } else if (outcode0 & outcode1) {  
           // Bitwise AND is not 0. Trivially reject  
                break;  
           } else {  
                // failed both tests, so calculate the line segment to clip  
                // from an outside point to an intersection with clip edge  
                double x, y;  
                // At least one endpoint is outside the clip rectangle; pick it.  
                OutCode outcodeOut = outcode0? outcode0 : outcode1;  
                // Now find the intersection point;  
                if (outcodeOut & TOP) {// point is above the window  
                     x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);  
                     y = ymax;  
                } else if (outcodeOut & BOTTOM) {// point is below the window  
                     x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);  
                     y = ymin;  
                } else if (outcodeOut & RIGHT) { // point is to the right of window  
                     y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);  
                     x = xmax;  
                } else { // point is to the left of window  
                     y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);  
                     x = xmin;  
                }  
                //Now move outside point to intersection point and get ready for next pass.  
                if (outcodeOut == outcode0) {  
                     x0 = x; y0 = y;  
                     outcode0 = ComputeOutCode(x0, y0);  
                } else {  
                     x1 = x; y1 = y;  
                     outcode1 = ComputeOutCode(x1, y1);  
                }  
           }  
           }  
           if (accept)  
                DrawLineSegment(x0, y0, x1, y1);  
 }  
   
 void myMouse(int button, int state, int x, int y) {  
      glPointSize(5.0);  
      if(state == GLUT_DOWN)   
      {  
           if(button == GLUT_LEFT_BUTTON)   
           {  
                if (flag){  
                     x0 = x;  
                     y0 = screenheight - y;  
                     flag = false;  
                } else {  
                     x1 = x;  
                     y1 = screenheight - y;  
                     CohenSutherlandLineClip(x0,y0,x1,y1);  
                     flag = true;  
                }  
           }  
           else if (button == GLUT_RIGHT_BUTTON)   
           {  
                if (flag){  
                     x0 = x;  
                     y0 = screenheight - y;  
                     flag = false;  
                } else {  
                     x1 = x;  
                     y1 = screenheight - y;  
                     glColor3d(1,1,0);  
                     DrawRect(x0,y0,x1,y1);  
                     xmin=x0;  
                     xmax=x1;  
                     ymin=y0;                      
                     ymax=y1;  
                     flag = true;  
                }  
           }  
      }  
 }  
   
   
 void myDisplay()  
 {  
      glClearColor(0.0f, 0.0f, 0.0f, 0.0f); //black  
      glClear(GL_COLOR_BUFFER_BIT);  
      glFlush();  
 }  
   
 int main( int argc, char ** argv ) {  
   
      glutInit( &argc, argv );  
      glutInitWindowPosition( 0, 0 );  
      glutInitWindowSize( 800, 600 );  
   
      // create window  
      glutCreateWindow( "Cohen-Sutherland Line Clipping" );  
   
      // set the view frustum  
      glMatrixMode( GL_PROJECTION );   
      glLoadIdentity();  
      gluOrtho2D( 0, 800, 0, 600 );  
   
      // clear rendering surface  
      glViewport(0, 0, 800, 600);  
   
      glutMouseFunc( myMouse );  
      glutDisplayFunc( myDisplay );  
      glutMainLoop();  
   
      return( 0 );  
 }  

Sunday, July 6, 2014

AO* ALGORITHM

1. Let G consists only to the node representing the initial state call this node INTT. Compute h' (INIT).

2. Until INIT is labeled SOLVED or hi (INIT) becomes greater than FUTILITY, repeat the following procedure.

(I) Trace the marked arcs from INIT and select an unbounded node NODE.

(II) Generate the successors of NODE . if there are no successors then assign FUTILITY as h' (NODE). This means that NODE is not solvable. If there are successors then for each one called SUCCESSOR, that is not also an ancester of NODE do the following

    (a) add SUCCESSOR to graph G

    (b) if successor is not a terminal node, mark it solved and assign zero to its h ' value.

    (c) If successor is not a terminal node, compute it h' value.

(III) propagate the newly discovered information up the graph by doing the following . let S be a set of nodes that have been marked SOLVED. Initialize S to NODE. Until S is empty repeat the following procedure;

   (a) select a node from S call if CURRENT and remove it from S.

    (b)compute h' of each of the arcs emerging from CURRENT , Assign minimum h' to CURRENT.

    (c) Mark the minimum cost path a s the best out of CURRENT.

    (d) Mark CURRENT SOLVED if all of the nodes connected to it through the new marked are have been labeled SOLVED.

    (e) If CURRENT has been marked SOLVED or its h ' has just changed, its new status must be propagate backwards up the graph . hence all the ancestors of CURRENT are added to S.

AO* Search Procedure

1. Place the start node on open.

2. Using the search tree, compute the most promising solution tree TP .

3. Select node n that is both on open and a part of tp, remove n from open and place it no closed.

4. If n is a goal node, label n as solved. If the start node is solved, exit with success where tp is the solution tree, remove all nodes from open with a solved ancestor.

5. If n is not solvable node, label n as unsolvable. If the start node is labeled as unsolvable, exit with failure. Remove all nodes from open ,with unsolvable ancestors.

6. Otherwise, expand node n generating all of its successor compute the cost of for each newly generated node and place all such nodes on open.

7. Go back to step(2)

Problem Reduction with AO* Algorithm

When a problem can be divided into a set of sub problems, where each sub problem can be solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR trees are used for representing the solution. The decomposition of the problem or problem reduction generates AND arcs. One AND are may point to any number of successor nodes. All these must be solved so that the arc will rise to many arcs, indicating several possible solutions. Hence the graph is known as AND - OR instead of AND. Figure shows an AND - OR graph.



An algorithm to find a solution in an AND - OR graph must handle AND area appropriately. A* algorithm cannot search AND - OR graphs efficiently. This can be understand from the give figure.

AND - OR graph



In figure (a) the top node A has been expanded producing two area one leading to B and leading to C-D . the numbers at each node represent the value of f ' at that node (cost of getting to the goal state from current state). For simplicity, it is assumed that every operation(i.e. applying a rule) has unit cost, i.e., each are with single successor will have a cost of 1 and each of its components. With the available information till now , it appears that C is the most promising node to expand since its f ' = 3 , the lowest but going through B would be better since to use C we must also use D' and the cost would be 9(3+4+1+1). Through B it would be 6(5+1).

Thus the choice of the next node to expand depends not only n a value but also on whether that node is part of the current best path form the initial mode. Figure (b) makes this clearer. In figure the node G appears to be the most promising node, with the least f ' value. But G is not on the current beat path, since to use G we must use GH with a cost of 9 and again this demands that arcs be used (with a cost of 27). The path from A through B, E-F is better with a total cost of (17+1=18). Thus we can see that to search an AND-OR graph, the following three things must be done.

1. traverse the graph starting at the initial node and following the current best path, and accumulate the set of nodes that are on the path and have not yet been expanded.

2. Pick one of these unexpanded nodes and expand it. Add its successors to the graph and computer f ' (cost of the remaining distance) for each of them.

3. Change the f ' estimate of the newly expanded node to reflect the new information produced by its successors. Propagate this change backward through the graph. Decide which of the current best path.

The propagation of revised cost estimation backward is in the tree is not necessary in A* algorithm. This is because in AO* algorithm expanded nodes are re-examined so that the current best path can be selected. The working of AO* algorithm is illustrated in figure as follows:



Referring the figure. The initial node is expanded and D is Marked initially as promising node. D is expanded producing an AND arc E-F. f ' value of D is updated to 10. Going backwards we can see that the AND arc B-C is better . it is now marked as current best path. B and C have to be expanded next. This process continues until a solution is found or all paths have led to dead ends, indicating that there is no solution. An A* algorithm the path from one node to the other is always that of the lowest cost and it is independent of the paths through other nodes.

The algorithm for performing a heuristic search of an AND - OR graph is given below. Unlike A* algorithm which used two lists OPEN and CLOSED, the AO* algorithm uses a single structure G. G represents the part of the search graph generated so far. Each node in G points down to its immediate successors and up to its immediate predecessors, and also has with it the value of h' cost of a path from itself to a set of solution nodes. The cost of getting from the start nodes to the current node "g" is not stored as in the A* algorithm. This is because it is not possible to compute a single such value since there may be many paths to the same state. In AO* algorithm serves as the estimate of goodness of a node. Also a there should value called FUTILITY is used. The estimated cost of a solution is greater than FUTILITY then the search is abandoned as too expensive to be practical. For representing above graphs AO* algorithm is as follows

A* Algorithm 2

A* algorithm: The best first search algorithm that was just presented is a simplification an algorithm called A* algorithm which was first presented by HART.

Algorithm:

Step 1: put the initial node on a list start

Step 2: if (start is empty) or (start = goal) terminate search.

Step 3: remove the first node from the start call this node a

Step 4: if (a= goal) terminate search with success.

Step 5: else if node has successors generate all of them estimate the fitness number of the successors by totaling the evaluation function value and the cost function value and sort the fitness number.

Step 6: name the new list as start 1.

Step 7: replace start with start 1.

Step 8: go to step 2.

Best First Seach Procedure with A* Algorithem



A is an initial node, which is expand to B,C and D. A heuristic function, say cost of reaching the goal , is applied to each of these nodes, since D is most promising, it is expanded next, producing two successor nodes E and F. Heuristic function is applied to them. Now out of the four remaining ( B,C and F) B looks more promising and hence it is expand generating nodes G and H . Again when evaluated E appears to be the next stop J has to be expanded giving rise to nodes I and J. In the next step J has to be expanded, since it is more promising . this process continues until a solution is found.

Above figure shows the best - first search tree. Since a search tree may generate duplicate nodes, usually a search graph is preferred.

The best - first search is implemented by an algorithm known as A* algorithm. The algorithm searches a directed graph in which each node represents a point in the problem space. Each node will contain a description of the problem state it represents and it will have links to its parent nodes and successor nodes. In addition it will also indicate how best it is for the search process. A* algorithm uses have been generated, heuristic functions applied to them, but successors not generated. The list CLOSED contains nodes which have been examined, i.e., their successors generated.

A heuristic function f estimates the merits of each generated node. This function f has two components g and h. the function g gives the cost of getting from the initial state to the current node. The function h is an estimate of the addition cost of getting from current node to a goal state. The function f (=g+h) gives the cost of getting from the initial state to a goal state via the current node.

THE A* ALGORITHM:-

1. Start with OPEN containing the initial node. Its g=0 and f ' = h ' Set CLOSED to empty list.

2. Repeat If OPEN is empty , stop and return failure Else pick the BESTNODE on OPEN with lowest f ' value and place it on CLOSED If BESTNODE is goal state return success and stop Else Generate the successors of BESTNODE.

   For each SUCCESSOR do the following:

  a. Set SUCCESSOR to point back to BESTNODE. (back links will help to recover the path)

  b. compute g(SUCCESSOR) = g(BESTNODE) + cost of getting from BESTNODE to SUCCESSOR.

  c. If SUCCESSOR is the same as any node on OPEN, call that node OLD and add OLD to BESTNODE 's successors. Check g(OLD) and g(SUCCESSOR). If g(SUCCESSOR) is cheaper then reset OLD 's parent link to point to BESTNODE. Update g(OLD) and f '(OLD).

  d. If SUCCESSOR was not on OPEN , see if it is on CLOSED . if so call the node CLOSED OLD , and better as earlier and set the parent link and g and f ' values appropriately.

  e. If SUCCESSOR was not already on earlier OPEN or CLOSED, then put it on OPEN and add it to the list of BESTNODE 's successors.

  Compute f ' (SUCCESSOR) = g(SUCCESSOR) + h ' (SUCCESSOR)

Best first searches will always find good paths to a goal after exploring the entire state space. All that is required is that a good measure of goal distance be used.

BreadthFirstSearch&DepthFirstSearchTrees for WaterJug Problem

What do you know about BFS??????????

Breadth First Search (BFS): This is also a brute force search procedure like DFS. We are searching progresses level by level. Unlike DFS which goes deep into the tree. An operator employed to generate all possible children of a node. BFS being a brute force search generates all the nodes for identifying the goal.

Algorithm:

Step 1: Put the initial node on a list “START”

Step 2: If START is empty or goal terminate the search.

Step 3: Remove the first node from the Start and call this node “a”

Step 4: If a =”GOAL” terminate search with success

Step 5: Else if node “a” has successors generate all of them and add them at the tail of “START”

Step 6: Go to step 2.

Advantages:

1. BFS will not get trapped exploring a blind alley.

2. If there is a solution then BFS is guaranteed to find it.

3. The amount of time needed to generate all the nodes is considerable because of the time complexity.

4. Memory constraint is also a major problem because of the space complexity.

5. The searching process remembers all unwanted nodes, which are not practical use for the search process.

What do you know about DFS?????

Depth first search: This is a very simple type of brute force searching techniques. The search begins by expanding the initial node i.e. by using an operator generate all successors of the initial node and test them.

This procedure finds whether the goal can be reached or not but the path it has to follow has not been mentioned. Diving downward into a tree as quickly as possible performs DFS searches.

Algorithm:

Step1: Put the initial node on a list START.

Step2: If START is empty or START = GOAL terminates search.

Step3: Remove the first node from START. Call this node a.

Step4: If (a= GOAL) terminates search with success.

Step5: Else if node a has successors, generate all of them and add them at the beginning Of START.

Step6: Go to Step 2.

The major drawback of the DFS is the determination of the depth citric with the search has to proceed this depth is called cut of depth.

The value of cutoff depth is essential because the search will go on and on. If the cutoff depth is smaller solution may not be found. And if cutoff depth is large time complexity will be more.

Advantages:

   DFS requires less memory since only the nodes on the current path are stored.

   By chance DFS may find a solution without examining much of the search space at all.

Depth First Search Procedure

Algorithm : Depth-First Search

   1. place the starting node in the queue.

   2. If the queue is empty, return failure and stop.

   3. If the first element on the queue is a goal node g , return succed and stop otherwise.

   4. Remove and expand the first element and place the children at the front of the queue.

   5.Go back to step 2.

Hill Climbing Procedure

This is a variety of depth-first (generate - and - test) search. A feedback is used here to decide on the direction of motion in the search space. In the depth-first search, the test function will merely accept or reject a solution. But in hill climbing the test function is provided with a heuristic function which provides an estimate of how close a given state is to goal state. The hill climbing test procedure is as follows :

1. General he first proposed solution as done in depth-first procedure. See if it is a solution. If so quit , else continue.

2. From this solution generate new set of solutions use , some application rules

3. For each element of this set

   (i) Apply test function. It is a solution quit.

   (ii) Else see whether it is closer to the goal state than the solution already generated. If yes, remember it else discard it.

4. Take the best element so far generated and use it as the next proposed solution. This step corresponds to move through the problem space in the direction Towards the goal state.

5.Go back to step 2.

Sometimes this procedure may lead to a position, which is not a solution, but from which there is no move that improves things. This will happen if we have reached one of the following three states.

   (a) A "local maximum " which is a state better than all its neighbors , but is not better than some other states farther away. Local maxim sometimes occur with insight of a solution. In such cases they are called " Foothills".

   (b) A "plateau" which is a flat area of the search space, in which neighboring states have the same value. On a plateau, it is not possible to determine the best direction in which to move by making local comparisons.

   (c) A "ridge" which is an area in the search that is higher than the surrounding areas, but can not be searched in a simple move.

To overcome theses problems we can

   (a) Back track to some earlier nodes and try a different direction. This is a good way of dealing with local maxim.

   (b) Make a big jump an some direction to a new area in the search. This can be done by applying two more rules of the same rule several times, before testing. This is a good strategy is dealing with plate and ridges.

Hill climbing becomes inefficient in large problem spaces, and when combinatorial explosion occurs. But it is a useful when combined with other methods.

Saturday, July 5, 2014

Generate and Test Procedure

Algorithm

This is the simplest search strategy. It consists of the following steps :

   1.   Generating a possible solution for some problems; this means generating a particular point in the problem space. For others it may be generating a path from a start state.

   2.   Test to see if this is actually a solution by comparing the chosen point at the end point of the chosen path to the set of acceptable goal states.

   3.   If a solution has been found, quit otherwise return to step 1.

The generate - and - Test algorithm is a depth first search procedure because complete possible solutions are generated before test. This can be implemented states are likely to appear often in a tree; it can be implemented on a search graph rather than a tree.

Heuristic Functions

A Heuristic technique helps in solving problems, even though there is no guarantee that it will never lead in the wrong direction. There are heuristics of every general applicability as well as domain specific. The strategies are general purpose heuristics. In order to use them in a specific domain they are coupler with some domain specific heuristics. There are two major ways in which domain - specific, heuristic information can be incorporated into rule-based search procedure.

   - In the rules themselves
   - As a heuristic function that evaluates individual problem states and determines how desired they are.

A heuristic function is a function that maps from problem state description to measures desirability, usually represented as number weights. The value of a heuristic function at a given node in the search process gives a good estimate of that node being on the desired path to solution. Well designed heuristic functions can provides a fairly good estimate of whether a path is good or not. ( " The sum of the distances traveled so far" is a simple heuristic function in the traveling salesman problem) . the purpose of a heuristic function is to guide the search process in the most profitable directions, by suggesting which path to follow first when more than one path is available. However in many problems, the cost of computing the value of a heuristic function would be more than the effort saved in the search process. Hence generally there is a trade-off between the cost of evaluating a heuristic function and the savings in search that the function provides.

Heuristic Search

Solve complex problems efficiently ,it is necessary to compromise the requirements of the movability and systematically. A control structure has to be constructed that no longer guarantees the best solution, but that will almost always find a very good answer. Such a technique is said to be heuristic (rule of thumb). A heuristic search improves the efficiently of the search process, but sacrifices the claims of completeness. But they improve the quality of the paths that are explored. Using good heuristics we can get good solutions to hard problems, such as the traveling salesman problem.

Applying it to the traveling salesman problem produces the following procedure.
1. Arbitrarily select a starting city.
2. To select the next city, look at all cities not yet visited. Select the one closet to the current city. Go to it next.
3. Repeat step 2 until all the cities have been visited.

Heuristic Search Techniques

Introduction:-
Many if the problems are too complex to be solvable by direct techniques. They have to be solved only by suitable heuristic search techniques. Though the heuristic techniques can be described independently, they are domain specific. They are called " Weak Methods", since they are vulnerable to combinatorial explosion. Even so, they provide the frame work into which domain specific knowledge can be placed.

Every search process can be viewed as a traversal of a directed graph, in which the nodes represent problem states and the arcs represent relationships between states. The search process must find a path through this graph, starting at an initial state and ending in one or more final states. The following issues have to be considered before going for a search.

Heuristic techniques are called weak methods, since they are vulnerable to combinatorial explosion. Even then these techniques continue to provide framework into which domain specific knowledge can be placed, either by hand or as a result of learning. The following are some general purpose control strategies (often called weak methods).

-Generate-and-test
-Hillclimbing
-Breadth-Firstsearch
-Depth-Firstsearch
-BestFirstSearch(A*search)
-Problemreduction(AO*search)
-Constraintsatisfaction
-Means-endsanalysis

A heuristic procedure, or heuristic, is defined as having the following properties.
1. It will usually find good, although not necessary optimum solutions.
2. It is faster and easier to implement than any known exact algorithm ( one which guarantees an optimum solution ).

In general, heuristic search improve the quality of the path that are exported. Using good heuristics we can hope to get good solutions to hard problems such as the traveling salesman problem in less than exponential time. There are some good general purpose heuristics that are useful in a wide variety of problems. It is also possible to construct special purpose heuristics to solve particular problems. For example, consider the traveling salesman problem.