Skip to content

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;

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

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


    Last modified on Friday, 06 January 2012 13:14

    Author

    Leave a Reply

    Your email address will not be published. Required fields are marked *