Simple Polygon
A. First Edition
The definition of simple polygon is a closed polygon consisted with a single polygonal chain which doesn't
intersect with itself.
At beginning it seems a trivial problem. However, before assignment 1 of comp6711 is issued I have no clue how to implement an algorithm. Suppose you are given a set of points, can you create a simple polygon from it? Is it simple? I feel not.
The algorithm is inspired by assignment from comp6711. It has a O(n*logn) time complexity. First we sort all points by its x value. Find the left-most and right-most point and use the line connected with them to separate all other points into "upper" part and "lower" part. Then for each point from left to right, if the point is at LHS of the testing line, connect it with upper point; If the point is at RHS of testing line, connect it with lower point.
In order to run in OpenGL, you need download "glut32.dll" and "glu32.dll" in your system folder.
i.e. c:\windows\system32
And to compile the code, you need to link with "openGL32.lib, glut32.lib, glu32.lib" in your vc6++.
E.Further improvement
Unexpectedly I am running into an OPENGL problem which takes me most of time in this evening. You see the
algorithm is trivial and I almost re-use all utility functions from my previous trivial program. However, the
openGL problem puzzled me for almost whole night! When I use GL_LINE_LOOP to draw my polygon, the right-most
point and nearby is always dimmed and sometimes omitted unless I force openGL to refresh. It must be my
stupid bug, however, I cannot find it.
F.File listing
1. ConvexHull.h
2. ConvexHull.cpp
3. main.cpp
file name: convexhull.h
#ifndef CONVEXHULL_H
#define CONVEXHULL_H
#include <vector>
#include <GL/glut.h>
using namespace std;
const int winPos_x=0, winPos_y=0;
const int winSize_width=600, winSize_height=600;
static const char* windowTitle="Convex Hull Demo";
const int MaxIntegerValue=winSize_width/2-30;
typedef GLfloat TColor[3];
static TColor red={1,0,0}, green={0,1,0}, blue={0,0,1};
struct TPoint
{
float x;
float y;
void display();
};
struct TPointContext
{
TPoint* pointPtr;
TColor pointColor;
};
float direction(TPoint* p, TPoint* q, TPoint* r);
float generateRandomValue();
void generatePoint(int pointNumber, TPoint*& ptrArray);
class TPointSet
{
public:
~TPointSet();
TPointSet();
int number;
TPoint* ptrArray;
void setArray(TPoint* inputArray, int inputNumber);
void display();
};
class Convex
{
private:
int number;
int* indexArray;
void sortPoint();
vector<int> upVector;
vector<int> downVector;
void collectVertex(vector<int>& intVector, bool upper);
void addPoint(vector<int>& intVector, int rIndex);
public:
static TPoint* ptrArray;
void generatePoint(int pointNumber);
Convex();
void display();
void convexHull(TPointSet& pointSet);
};
class TPolygon
{
private:
int number;
TPoint* leftMost;
TPoint* rightMost;
public:
TPoint* ptrArray;
TPolygon();
void createPolygon(int pointNumber, TPointSet& pointSet);
};
#endif
file name: convexhull.cpp
#include <iostream>
#include <cmath>
#include <vector>
#include "ConvexHull.h"
using namespace std;
TPoint* Convex::ptrArray=NULL;
//GLenum drawingMode = GL_POINTS;
vector<TPointContext> separateVector;
vector<TPointContext> connectVector;
vector<TPointContext> polygonVector;
TPolygon polygon;
Convex convex;
TPointSet pointSet;
int compPoint(const void* elem1, const void* elem2)
{
TPoint* ptr1, *ptr2;
ptr1=(TPoint*)elem1;
ptr2=(TPoint*)elem2;
return ptr1->x-ptr2->x;
}
void TPolygon::createPolygon(int pointNumber, TPointSet& pointSet)
{
int start=0, end=pointNumber-1;
number=pointNumber;
::generatePoint(pointNumber, ptrArray);
qsort(ptrArray, number, sizeof(TPoint), compPoint);
leftMost=ptrArray;
rightMost=ptrArray+number-1;
pointSet.number=number;
pointSet.ptrArray=new TPoint[number];
for (int i=0; i<number; i++)
{
if (direction(leftMost, rightMost, ptrArray+i)<=0)
{
pointSet.ptrArray[start]=ptrArray[i];
start++;
}
else
{
pointSet.ptrArray[end]=ptrArray[i];
end--;
}
}
}
TPolygon::TPolygon()
{
//createPolygon();
}
int pointComp(const void* elem1, const void* elem2)
{
TPoint *ptr1, *ptr2;
float result;
ptr1=Convex::ptrArray + *(const int*)(elem1);
ptr2=Convex::ptrArray + *(const int*)(elem2);
result= ptr1->x-ptr2->x;
if (result>0)
{
return 1;
}
else
{
if (result<0)
{
return -1;
}
else
{
return 0;
}
}
}
float direction(TPoint* p, TPoint* q, TPoint* r)
{
return q->x*r->y +p->x*q->y+p->y*r->x - p->y*q->x - q->y*r->x -p->x*r->y;
}
void TPoint::display()
{
printf("[x=%f,y=%f]\n", x, y);
}
TPointSet::TPointSet()
{
number=0;
ptrArray=NULL;
}
void TPointSet::display()
{
for (int i=0; i<number; i++)
{
ptrArray[i].display();
}
}
TPointSet::~TPointSet()
{
if (number!=0)
{
delete[]ptrArray;
}
}
void TPointSet::setArray(TPoint* inputArray, int inputNumber)
{
number=inputNumber;
ptrArray=new TPoint[number];
memcpy(ptrArray, inputArray, sizeof(TPoint)*number);
}
float generateRandomValue()
{
float intPart, floatPart;
intPart=rand()%MaxIntegerValue * (rand()%2==0?1 : (-1));
floatPart=(float)rand()/(float)RAND_MAX;
return intPart+floatPart;
}
void Convex::generatePoint(int pointNumber)
{
number=pointNumber;
::generatePoint(pointNumber, ptrArray);
}
void generatePoint(int pointNumber, TPoint*& ptrArray)
{
TPointContext pointContext;
ptrArray=new TPoint[pointNumber];
for (int i=0; i<pointNumber; i++)
{
ptrArray[i].x=generateRandomValue();
ptrArray[i].y=generateRandomValue();
pointContext.pointPtr=ptrArray+i;
memcpy(pointContext.pointColor, red, sizeof(TColor));
separateVector.push_back(pointContext);
//glutPostRedisplay();
glutSwapBuffers();
}
//glutPostRedisplay();
}
//randomly generating points
Convex::Convex()
{
number=0;
ptrArray=NULL;
}
void Convex::sortPoint()
{
indexArray=new int[number];
for (int i=0; i<number; i++)
{
indexArray[i]=i;
}
qsort(indexArray, number, sizeof(int), pointComp);
}
void Convex::addPoint(vector<int>& intVector, int rIndex)
{
int currentSize;
int pIndex, qIndex;
while (intVector.size()>=2)
{
currentSize=intVector.size();
pIndex=intVector[currentSize-2];
qIndex=intVector[currentSize-1];
if (direction(ptrArray+pIndex, ptrArray+qIndex, ptrArray+rIndex)>=0)
{
intVector.pop_back();
}
else
{
break;
}
}
intVector.push_back(rIndex);
}
void Convex::collectVertex(vector<int>& intVector, bool upper)
{
int index, offset, counter=number-2;
intVector.clear();
if (upper)
{
index=0;
offset=1;
}
else
{
index=number-1;
offset=-1;
}
intVector.push_back(indexArray[index]);
index+=offset;
intVector.push_back(indexArray[index]);
while (counter>0)
{
index+=offset;
addPoint(intVector, indexArray[index]);
counter--;
}
}
void Convex::display()
{
for (int i=0; i<number; i++)
{
ptrArray[i].display();
}
}
void Convex::convexHull(TPointSet& pointSet)
{
int i;
int upSize, downSize;
if (number<3)
{
pointSet.setArray(ptrArray, number);
}
else
{
sortPoint();
collectVertex(upVector, true);
collectVertex(downVector, false);
upSize=upVector.size();
//we need to remove the first and last
downSize=downVector.size()-2;
pointSet.number=upSize+downSize;
pointSet.ptrArray=new TPoint[pointSet.number];
for (i=0; i<pointSet.number; i++)
{
if (i<upSize)
{
pointSet.ptrArray[i]=ptrArray[upVector[i]];
}
else
{
//starting from second, so add 1
pointSet.ptrArray[i]=ptrArray[downVector[i-upSize+1]];
}
}
}
}
file name: main.cpp
#include "ConvexHull.h"
#include <GL/glut.h>
#include <ctime>
using namespace std;
extern vector<TPointContext> separateVector;
extern vector<TPointContext> connectVector;
extern Convex convex;
extern TPolygon polygon;
extern TPointSet pointSet;
void displayCallback()
{
int separateNumber, connectNumber, i;
glClearColor(1,1,0,1);
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);
//separateNumber=separateVector.size();
separateNumber=0;
connectNumber=connectVector.size();
//connectNumber=0;
glPointSize(10.0);
glLineWidth(5);
if (separateNumber>0)
{
glBegin(GL_POINTS);
for (i=0; i<separateNumber; i++)
{
glVertex2f(separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
glColor3fv(separateVector[i].pointColor);
//printf("x=%f, y=%f\n", separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
}
glEnd();
}
if (connectNumber>0)
{
glBegin(GL_LINE_LOOP);
for (i=0; i<connectNumber; i++)
{
glVertex2f(connectVector[i].pointPtr->x, connectVector[i].pointPtr->y);
//printf("x=%f, y=%f\n", connectVector[i].pointPtr->x,
// connectVector[i].pointPtr->y);
glColor3fv(connectVector[i].pointColor);
}
glEnd();
glBegin(GL_POINTS);
for (i=0; i<connectNumber; i++)
{
glVertex2f(connectVector[i].pointPtr->x, connectVector[i].pointPtr->y);
glColor3fv(connectVector[i].pointColor);
//printf("x=%f, y=%f\n", separateVector[i].pointPtr->x, separateVector[i].pointPtr->y);
}
glEnd();
}
glutSwapBuffers();
//glutPostRedisplay();
}
void keyboardCallback(unsigned char key, int x, int y)
{
int i;
TPointContext pointContext;
//float coord[4];
switch (key)
{
case 27:
exit(0);
break;
case 's':
convex.generatePoint(10);
break;
case 'c':
convex.convexHull(pointSet);
for (i=0; i<pointSet.number; i++)
{
memcpy(pointContext.pointColor, green, sizeof(TColor));
pointContext.pointPtr=pointSet.ptrArray+i;
connectVector.push_back(pointContext);
glutPostRedisplay();
}
break;
case 't':
//glutStrokeCharacter(GLUT_STROKE_ROMAN, 's');
glColor3fv(blue);
glPointSize(1.0);
glutBitmapCharacter(GLUT_BITMAP_9_BY_15 , 1);
/*
glGetFloatv(GL_CURRENT_RASTER_POSITION, coord);
for (i=0; i<4; i++)
{
printf("[%f],", coord[i]);
}
*/
break;
case 'p':
polygon.createPolygon(11, pointSet);
for (i=0; i<pointSet.number; i++)
{
memcpy(pointContext.pointColor, blue, sizeof(TColor));
pointContext.pointPtr=pointSet.ptrArray+i;
connectVector.push_back(pointContext);
//glutPostRedisplay();
}
break;
}
glutPostRedisplay();
}
void reshapeCallback(int width, int height)
{
glutPostRedisplay();
}
void init()
{
gluOrtho2D((float)winSize_width/2.0, (float)winSize_width/-2.0,
(float)winSize_height/-2.0, (float)winSize_height/2.0);
}
int main(int argc, char** argv)
{
srand(time(0));
glutInit(&argc, argv);
glutInitWindowPosition(winPos_x, winPos_y);
glutInitWindowSize(winSize_width, winSize_height);
glutInitDisplayMode(GLUT_RGBA|GLUT_ALPHA|GLUT_DOUBLE);
glutCreateWindow(windowTitle);
glutDisplayFunc(displayCallback);
glutKeyboardFunc(keyboardCallback);
glutReshapeFunc(reshapeCallback);
init();
//printf("before convex hull\n");
//convex.display();
//convex.convexHull(pointSet);
//printf("after convex hull\n");
//pointSet.display();
//glutPostRedisplay();
//glutShowWindow();
glutMainLoop();
return 0;
}