Home Programming A program to find the convex hull using Pakage wrapping algorithm

# A program to find the convex hull using Pakage wrapping algorithm

In this program, basically user is free to enter what ever the point coordinates he/she likes. But minimally there have to be 4 coordinates. Because triangle is always a convex hull. So this programs strictly tries get first 4 coordinates from the user. After that user can choose whether he/she wants to enter more coordinates or not. This program uses a very smart function named findAng(), which able to convert the -PI,+PI range of antan2() function in to positive degree angle according to the quadrant which the angle is in. So by that it finds the convex hull according to the given set of points. Comments are placed in relevant places of the source code where an explanation is needed.

Technical Details :
This progam was compiled using: GNU GCC Compiler version(Debian-Linux/Linaro 4.4.4-14deb5) 4.4.5
The program was ran and tested under: Debian-Linux 2.6.35-30-generic

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define INITANG 361 //An angle values more than 2PI in degrees

// 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;

{
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)(p2xp1x);
double deltaY= (double)(p2yp1y);
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);

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);
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);
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;
}

void printAns()
{
struct point *tmp = ans_bag;
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;
}
}

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();
}