A program to find the convex hull using Pakage wrapping algorithm

// A doubly circular linked list is very useful when dealing with the problem of finding the minimum point.
// Beuase in a doubly circular linked list, a pointer can move any direction through out the list whout any problem.
struct point
{
int pointId;
int isAns; // this attribute is specially used to check if the point has been taken as an answer. If so ignore that point.
double x;
double y;
struct point *next;
struct point *prev;
};

//Few essential global varibles are used
struct point *first_point;
struct point *curr_point = NULL;
struct point *ans_bag;
int idCount=1;

//point added in to the linked list.
void addPoint(double xCord,double yCord)
{
if(first_point==NULL) //if the list is empty
{
first_point = malloc(sizeof(struct point));
first_point->next = NULL;
first_point->prev = NULL;
first_point->pointId = idCount++;
first_point->x = xCord;
first_point->y = yCord;
first_point->isAns = 0;
}
else //if the list is not empty
{
struct point *itr = first_point;
struct point *tmp = malloc(sizeof(struct point));
while(itr->next!=NULL)
{
itr = itr->next;
}
tmp->next = NULL;
tmp->prev = itr; //always caring about setting the backward pointer
tmp->pointId = idCount++;
tmp->x = xCord;
tmp->y = yCord;
tmp->isAns = 0;
itr->next = tmp;
}

}

//Angle calculating function
double findAng(double p1x,double p1y,double p2x,double p2y)
{
double PI=atan(1.0)*4; //Creating the value of PI
double ans;
double deltaX= (double)(p2x–p1x);
double deltaY= (double)(p2y–p1y);
ans=atan2(deltaY,deltaX)*(180/PI); //using atan2 the arc tangent of the delta-y delta-x was calculated and it was converted from RAD in to DEG
if(ans<0) //If it is a minus angle, it was converted in to a angle that originates from positive direction of X-Axis by adding 2PI.
{
ans+=360;
}
return ans;
}

void pakageWrap() //The most important method of the program
{
struct point *tmp;
struct point *ans_point;
struct point *newAns;
struct point *ans_bag_itr;

double minAngl,minAnglTmp;

if(first_point==NULL) //if the point set is empty
{
printf(“The point set is empty or something unusual happened!.. Cannot continuen“);
exit(EXIT_SUCCESS);
}

if(curr_point==NULL) //is the currently selected point is empty?
{
curr_point=first_point;
}

do
{
ans_bag_itr = ans_bag;
tmp = curr_point->next;
minAngl = INITANG; //minimum angle is set to an impossible angle first. So that any real angle will overwrite that.

while(tmp!=curr_point)
{
if(tmp->isAns == 1) //checks the point whether it is already taken as an answer
tmp=tmp->next;

else
{
//avoid if there is any point overlapping. don’t consider that point again.
if(curr_point->x==tmp->x && curr_point->y == tmp->y)
{
tmp->isAns = 1;
tmp = tmp->next;
}

else
{
minAnglTmp = findAng(curr_point->x,curr_point->y,tmp->x,tmp->y);
printf(“Point: (%0.2lf,%0.2lf) with angle: %0.2lf degrees by X-Axisn“,tmp->x,tmp->y,minAnglTmp);
if(minAngl>minAnglTmp) //if found angle is smaller that minimum angle, get that angle and point as an answer point.
{
ans_point = tmp;
minAngl = minAnglTmp;
}
tmp=tmp->next;
}
}
}
printf(“# Selected point is (%0.2lf,%0.2lf) with angle of %0.2lf degrees by X-Axis #n“,ans_point->x,ans_point->y,minAngl);

//allocating memory to store new answer point in answer bag
newAns = malloc(sizeof(struct point));
newAns->next = NULL;
newAns->prev = NULL;
newAns->pointId = ans_point->pointId;
newAns->x = ans_point->x;
newAns->y = ans_point->y;
newAns->isAns = ans_point->isAns = 1;

if(ans_bag==NULL) //is answer bag is empty?
{
ans_bag = newAns;
}
else
{
while(ans_bag_itr->next!=NULL)
{
ans_bag_itr=ans_bag_itr->next;
}
ans_bag_itr->next = newAns;
newAns->prev = ans_bag_itr;
}
curr_point = ans_point; //answer point was set to current point.
}
while(curr_point!=first_point); //loop runs until the polygon completes
}

void initPakageWrap()
{
int i;
double xCord, yCord;
struct point *tmp;
char choice;

printf(“**** Find the Convex Hull ****nn“);

//Takes the 4 required points from the user.
printf(“You are about to enter the set of Co-ordinates to find the Convex Hulln“);
printf(“E[31m”);
printf(“Four points are taken from you as required points. So please enter the required points.nn“);
printf(“E[0m”);
for (i=1;i<=4;i++)
{
printf(“Enter required point %d detailsn“,i);
printf(“X Coordinate: “);
scanf(“%lf”,&xCord);
printf(“Y Coordinate: “);
scanf(“%lf”,&yCord);
addPoint(xCord,yCord);
printf(“nPOINT (%lf,%lf) WAS ADDED TO THE SET SUCCESSFULLYnn“,xCord,yCord);
getchar();
}
while(1)
{
//user can add more points as he/she want.
printf(“Do you want to enter another Coordinate(y/n)?”);
scanf(“%c”,&choice);

if(choice==‘y’||choice==‘Y’)
{
printf(“X Coordinate: “);
scanf(“%lf”,&xCord);
printf(“Y Coordinate: “);
scanf(“%lf”,&yCord);
addPoint(xCord,yCord);
printf(“nPOINT (%lf,%lf) WAS ADDED TO THE SET SUCCESSFULLYnn“,xCord,yCord);
}
else if(choice==‘n’||choice==‘N’)
{
break;
}
else
{
printf(“Wrong input! try againn“);
}
getchar();
}

//completes the doubly circular linked list.
tmp = first_point;
while(tmp->next!=NULL)
{
tmp=tmp->next;
}
tmp->next = first_point;
first_point->prev = tmp;
}

// prints the answer points which are in the answer bag
void printAns()
{
struct point *tmp = ans_bag;
printf(“n** The answers **n“);
while(tmp->next!=NULL)
{
printf(“Point ID: %d Coordinates: (%0.2lf,%0.2lf)n“,tmp->pointId,tmp->x,tmp->y);
tmp=tmp->next;
}

}

// finds the first point. First point is the point bearing smallest X coordinate
void findFirstPoint()
{
struct point *tmp = first_point;
struct point *first_point_tmp = first_point;
int minX = tmp->x;
while(tmp->next!=first_point_tmp)
{
tmp=tmp->next;
if(minX>tmp->x)
{
minX = tmp->x;
first_point = tmp;
}
}

//first point is already taken as an answer point.
ans_bag = malloc(sizeof(struct point));
ans_bag->next = NULL;
ans_bag->prev = NULL;
ans_bag->pointId = first_point->pointId;
ans_bag->x = first_point->x;
ans_bag->y = first_point->y;
ans_bag->isAns = first_point->isAns = 0;

struct point *tmp2 = first_point;
do
{
printf(“Point ID: %d Coordinates: (%0.2lf,%0.2lf)n“,tmp2->pointId,tmp2->x,tmp2->y);
tmp2=tmp2->next;
}
while(tmp2!=first_point);
}
void clearscreen()
{
if (system( “clear” )) system( “cls” );
}

//main will invoke all the methods
int main()
{
clearscreen();
initPakageWrap();
findFirstPoint();
pakageWrap();
printAns();
}