Computational Geometry DATN09 Project

Computational Geometry DATN09 Project

Viswanathan Bhojan – 7806300419

Simulation of CG Algorithms – Convex Hull

This project is aimed at creating a simulation package for the CG algorithms taught in the course. Simulation of the algorithms is interesting from the Teachers perspective as a teaching aid and from the Students perspective as a learning aid.

The simulation code is in C++ and uses IT++, OpenGL on Cygwin. As an initiative, the Convex Hull Algorithm has been implemented first. Further algorithms from the course will be added later.

Convex Hull – Grahams Scan

The program allows inputting various points and then step through the Algorithm, running the Upper Hull first and then the Lower Hull. The handling of the degenerate cases has been deliberately left out so that the degenerate cases can be observed. The simulation can also be made to handle this case easily. The following steps are tracked:

.Adding Points to the Upper Convex Hull

.Checking if the new point makes a Concave segment.

.Backtrack until the segment is a Convex

.Do the Lower Convex Hull.

Running the Program

Mouse Click for adding Points

u – for stepping through the Upper Convex Hull

l – for stepping through the Lower Convex Hull

a – simulating the process again

s – starting with a new set of points

Some Snap shots from the program

1.  Points Added

2.  Upper Hull in progress.

3.  Upper hull formed and Lower Hull in progress

4.  Convex Hull formed.

#include <iostream>

#include <GL/glut.h>

#include <itpp/itbase.h>

/*

* Requires IT++,Open GL and Cygwin for Compiling

* Needs Cygwin1.dll for running.

*/

using namespace std;

using namespace itpp;

float windowWidth = 750;

float windowHeight = 500;

typedef struct CGPoint {

int x;

int y;

}CGPoint;

int currentPoint = 0;

VecCGPoint> points(100);

VecCGPoint> upperConvexHull(100);

VecCGPoint> lowerConvexHull(100);

int numUpperConvexPoints = 0;

int numLowerConvexPoints = 0;

int backTracking = 0;

int upperConvexRunPoint = 0;

int lowerConvexRunPoint = 0;

void print(const CGPoint & p)

{

float x,y;

x = (float)(p.x-windowWidth/2)*2/windowWidth;

y = (float)(windowHeight/2-p.y)*2/windowHeight;

cout < "[" < p.x < "," < p.y < "],";

}

void print_points(string str)

{

cout < str ;

for(int pts=0;pts<currentPoint;pts++)

print(points(pts));

cout < endl;

}

void print_u(string str)

{

cout < str ;

for(int pts=0;pts<=numUpperConvexPoints;pts++)

print(upperConvexHull(pts));

cout < endl;

}

void print_l(string str)

{

cout < str ;

for(int pts=0;pts<=numLowerConvexPoints;pts++)

print(lowerConvexHull(pts));

cout < endl;

}

void sortPoints(void)

{

CGPoint tmp;

int i,j;

for(i=0;i<currentPoint-1;i++)

{

for(j=i+1;j<currentPoint;j++)

{

if(points(j).x < points(i).x)

{

tmp = points(j);

points(j) = points(i);

points(i) = tmp;

}

}

}

}

void runLowerConvexHull(void)

{

int i = lowerConvexRunPoint;

if(numLowerConvexPoints == 0 & lowerConvexRunPoint == 0){

lowerConvexRunPoint = currentPoint-1;

lowerConvexHull(0) = points(lowerConvexRunPoint);

numLowerConvexPoints = 0;

backTracking = 0;

}

else

{

if(!backTracking)

{

numLowerConvexPoints++;

lowerConvexHull(numLowerConvexPoints) = points(i);

lowerConvexHull(numLowerConvexPoints+1) = points(i);

}

}

if(numLowerConvexPoints > 1)

{

CGPoint X,Y,Z;

Z = lowerConvexHull(numLowerConvexPoints);

Y = lowerConvexHull(numLowerConvexPoints-1);

X = lowerConvexHull(numLowerConvexPoints-2);

print(X);print(Y);print(Z);

cout < "Slope : XY " < (float)(Y.y-X.y)/(Y.x-X.x) < " Slope : YZ " < (float)(Y.y-Z.y)/(Y.x-Z.x) < endl;

if((float)(Y.y-X.y)/(Y.x-X.x) > (float)(Y.y-Z.y)/(Y.x-Z.x))

{

if(backTracking)

{

lowerConvexHull(numLowerConvexPoints-1) = lowerConvexHull(numLowerConvexPoints);

numLowerConvexPoints--;

if(numLowerConvexPoints == 1)

{

lowerConvexRunPoint--;

backTracking = 0;

}

}

else

{

backTracking++;

}

}

else

{

lowerConvexRunPoint--;

backTracking = 0;

}

}

else

lowerConvexRunPoint--;

}

void runUpperConvexHull(void)

{

int i = upperConvexRunPoint;

if(numUpperConvexPoints ==0 & upperConvexRunPoint == 0){

upperConvexHull(0) = points(0);

numUpperConvexPoints = 0;

}

else

{

if(!backTracking)

{

numUpperConvexPoints++;

upperConvexHull(numUpperConvexPoints) = points(i);

upperConvexHull(numUpperConvexPoints+1) = points(i);

}

}

if(numUpperConvexPoints > 1)

{

CGPoint X,Y,Z;

Z = upperConvexHull(numUpperConvexPoints);

Y = upperConvexHull(numUpperConvexPoints-1);

X = upperConvexHull(numUpperConvexPoints-2);

print(X);print(Y);print(Z);

cout < "Slope : XY " < (float)(Y.y-X.y)/(Y.x-X.x) < " Slope : YZ " < (float)(Y.y-Z.y)/(Y.x-Z.x) < endl;

if((float)(Y.y-X.y)/(Y.x-X.x) > (float)(Y.y-Z.y)/(Y.x-Z.x))

{

if(backTracking)

{

upperConvexHull(numUpperConvexPoints-1) = upperConvexHull(numUpperConvexPoints);

numUpperConvexPoints--;

if(numUpperConvexPoints == 1)

{

upperConvexRunPoint++;

backTracking = 0;

}

}

else

{

backTracking++;

}

}

else

{

upperConvexRunPoint++;

backTracking = 0;

}

}

else

upperConvexRunPoint++;

}

void keyboard( unsigned char key, int x, int y )

{

switch(key)

{

case 'q':

case 27:

exit(0);

break;

case 's':

currentPoint=0;

case 'a':

upperConvexRunPoint = lowerConvexRunPoint = 0;

numUpperConvexPoints = numLowerConvexPoints = 0;

backTracking = 0;

break;

case 'u':

if(upperConvexRunPoint < currentPoint || backTracking)

runUpperConvexHull();

break;

case 'l':

if (lowerConvexRunPoint >= 0 || backTracking)

runLowerConvexHull();

break;

case 'p':

print_points("");

break;

default:

break;

}

glutPostRedisplay();

}

void mouse( int button, int state, int x, int y )

{

if (state == GLUT_DOWN)

{

CGPoint p = {x,y};

points(currentPoint) = p;

currentPoint++;

sortPoints();

}

glutPostRedisplay();

}

void display(void)

{

float x,y;

glClear(GL_COLOR_BUFFER_BIT);

glColor3f(1.0, 1.0, 0.0);

glPointSize(5.0);

glBegin(GL_POINTS);

for(int vertex=0;vertex<currentPoint;vertex++)

{

x = (float)(points(vertex).x-windowWidth/2)*2/windowWidth;

y = (float)(windowHeight/2-points(vertex).y)*2/windowHeight;

glVertex2f(x,y);

}

glEnd();

glColor3f(0.0, 0.0, 1.0);

glBegin(GL_LINES);

for(int vertex=0;vertex<numUpperConvexPoints;vertex++)

{

x = (float)(upperConvexHull(vertex).x-windowWidth/2)*2/windowWidth;

y = (float)(windowHeight/2-upperConvexHull(vertex).y)*2/windowHeight;

glVertex2f(x,y);

x = (float)(upperConvexHull(vertex+1).x-windowWidth/2)*2/windowWidth;

y = (float)(windowHeight/2-upperConvexHull(vertex+1).y)*2/windowHeight;

glVertex2f(x,y);

}

glEnd();

glColor3f(0.0, 1, 0.0);

glBegin(GL_LINES);

for(int vertex=0;vertex<numLowerConvexPoints;vertex++)

{

x = (float)(lowerConvexHull(vertex).x-windowWidth/2)*2/windowWidth;

y = (float)(windowHeight/2-lowerConvexHull(vertex).y)*2/windowHeight;

glVertex2f(x,y);

x = (float)(lowerConvexHull(vertex+1).x-windowWidth/2)*2/windowWidth;

y = (float)(windowHeight/2-lowerConvexHull(vertex+1).y)*2/windowHeight;

glVertex2f(x,y);

}

glEnd();

glFlush();

}

void reshape( int w, int h )

{

glMatrixMode( GL_PROJECTION );

glLoadIdentity();

glOrtho(-1.0, 1.0, -1.0, 1.0, -1.0, 1.0);

glutPostRedisplay();

windowWidth = (float)w, windowHeight = (float)h;

}

void init()

{

glClearColor (0.0, 0.0, 0.0, 0.0);

glColor3f(1.0, 1.0, 0.0);

glMatrixMode (GL_PROJECTION);

glLoadIdentity ();

glOrtho(-1.0, 1.0, -1.0, 1.0, -1.0, 1.0);

}

int main(int argc, char** argv)

{

glutInit(&argc,argv);

glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);

glutInitWindowSize((int)windowWidth,(int)windowHeight);

glutInitWindowPosition(0,0);

glutCreateWindow("Computational Geometry - Convex Hull Algorithm Simulation");

glutDisplayFunc(display);

glutReshapeFunc( reshape );

glutKeyboardFunc( keyboard );

glutMouseFunc( mouse );

init();

glutMainLoop();

}