computing the convex hull of a bunch of points

[rockerjhr]

Ok so i have to create a program that computes the convex hull of a bunch of random points but i have no idea where to start i mean i know how the program is supposed to work since you can just easily look up the pseudo code but i really have no idea where to start I have to do it using graham scan's method using a stack pushing and poping points and i already created the interface functions for that but im just blank dont really know where to start

[rubberman]

That's why there are TA's (Teaching Assistants) - to help the clueless get one! Do some googling or visit the library or wikipedia. Also, since you can get access to pseudo code for this, writing the program should be pretty simple.

[rockerjhr]

if youre not going to help just shut up i swear this forum is full of people who think theyre too good to help others

[rubberman]

So, you want us to do your homework for you, and complain when we tell you to make some effort first on your own? What a maroon!

[rockerjhr]

dont want you to do my homework for me just wanted some advice if i wanted you to do my homework i would've said can you give me the code to compute the convex hull don't you think?

[rubberman]

Ok. Fair enough. Do you know the way to do it manually, with calculations and graph paper? We can start with that, develop pseudo code, and then convert that to program code. The first thing is that you need to know how to solve the problem in its most basic form.

[rockerjhr]

this is what i have so far

#define PUSH_XY(p_S , x , y) \
		if (push_xy(p_S , x , y ) == ERROR){ \
			printf(PUSH_ERR) ; \
			continue ; \
		}


#define INI_ERR "Error initializing the stack. Region not filled.\n"
#define PUSH_ERR "Error adding to stack . Region may not be totally filled.\n"



#define PI 3.14159265






#define PUSH_XY(p_S , x , y) \
		if (push_xy(p_S , x , y ) == ERROR){ \
			printf(PUSH_ERR) ; \
			continue ; \
		}


#define INI_ERR "Error initializing the stack. Region not filled.\n"
#define PUSH_ERR "Error adding to stack . Region may not be totally filled.\n"

#include<stdlib.h>
#include <stdio.h>
#include <math.h>


#define PI 3.14159265

typedef struct point point ;

struct point{


int x ;

int y ;

double t ;


};


typedef char byte ;

void memcopy( byte *to, byte *from, int count ) {

  while (count-- > 0 )  *to++ = *from++ ;

}




double compare_angle(  byte *a , byte *b ) {

  double aa ;
  double bb ;

   aa = ((point *)a) -> t ;
   bb = ((point *)b) -> t ;

  if (aa > bb) return 1 ;

  if (aa < bb) return -1 ;

  return 0 ;
}






double theta(double x1, double y1, double x2 , double y2) ;
double compare_angle(  byte *a , byte *b ) ;
void merge_sort(byte data[], int n , int elementsize , double (*p_cmp_f)() ) ;
int minimum_pos(point a[] ,int n);
 void Swap( point *nArray, int nFirst, int nSecond);
point minimum(point a[] ,int n);
void Swap( point *nArray, int nFirst, int nSecond);
int main( int argc, char *argv[] ) {

int i ;

int N = 20;

point *A ;

point s ;

A = (point *)malloc(sizeof(point)*N) ;
if ( A == NULL ) { printf(" Error mallocing \n" ); return -1 ; }




for(i=0 ; i < N ; i++ ){

  A[i].x = rand()%20 ;
  A[i].y = rand()%20 ;

} 

point z = minimum(A,20) ;

for(i = 0 ; i < N ; i++){

A[i].t = theta(A[i].x,A[i].y,z.x,z.y) ;



}


printf("Points are:\n\n") ;


for(i=0 ; i < N ; i++ ){

printf("(%d,%d)\n",A[i].x,A[i].y) ;


}




printf("Minimum point is (%d,%d)\n\n",z.x,z.y) ;



int y = minimum_pos(A,20) ;

Swap(A,1,y) ;







  merge_sort( (byte *) A, N , sizeof(point) , compare_angle ) ;


printf("SORTED points are:\n\n") ;


for(i=0 ; i < N ; i++ ){

printf("(%d,%d)\n",A[i].x,A[i].y) ;


}
















return 0 ;

}













double findAngle(double x1, double y1, double x2, double y2)
{
    double deltaX=x2-x1;
    double deltaY=y2-y1;

    if (deltaX==0 && deltaY==0)
        return 0;

    double angle=atan(deltaY/deltaX)*(180.0/3.141592);

    //TAKE INTO ACCOUNT QUADRANTS, VALUE: 0° - 360°
    if (deltaX>=0 && deltaY>=0)
        angle=90+angle;
    else if (deltaX>=0 && deltaY<0)
        angle=90+angle;
    else if (deltaX<0 && deltaY>0)
        angle=270+angle;
    else if (deltaX<0 && deltaY<=0)
        angle=270+angle;

    return angle;
}





point minimum(point a[] ,int n){

int i ;

point min ;

min  = a[0] ;


for(i = 0 ; i < n ; i++ ){


if(a[i].y == min.y ){
  if(a[i].x < min.x )

	min = a[i] ;


}


if(a[i].y < min.y )

	min = a[i] ;

}

return min ;


}


/* if ccw > 0  counter-clockwise   , if ccw < 0  clockwise , ccw = 0 colineR  */
int ccw(point p1,point p2,point p3){
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) ;


}



int minimum_pos(point a[] ,int n){

int position = 0  ;
int i ;

point min ;

min  = a[0] ;


for(i = 0 ; i < n ; i++ ){


if(a[i].y < min.y ){

	min = a[i] ;
     position = i ;

}



}

return position ;

}





void Swap( point *nArray, int nFirst, int nSecond){
  point nTemp = nArray[nFirst];
  nArray[nFirst] = nArray[nSecond];
  nArray[nSecond] = nTemp;
}




double theta(double x1, double y1, double x2 , double y2)
{



double deltay = y2 - y1 ;
double deltax = x2 - x1 ;


double tant = deltay/deltax ;

double angle = atan(tant);


if( deltax == 0)
return PI/2 ;





        return angle;









}



void merge_sort( byte data[], int n, int elementsize, double (*p_cmp_f)( ) )  {

byte *firsthalf ;
byte *endoffirsthalf ;
byte *secondhalf ;
byte *endofsecondhalf ;
byte *resultbuffer , *p_result ;
int halfsize ;

if(n <= 1)
return ;

halfsize = n/2 ;
firsthalf = data ;
secondhalf = data + halfsize * elementsize ;

merge_sort(firsthalf ,halfsize,elementsize, p_cmp_f) ;
merge_sort(secondhalf,n-halfsize,elementsize,p_cmp_f) ;

endoffirsthalf = secondhalf ;
endofsecondhalf = data + n * elementsize ;
resultbuffer = (byte *) malloc(n * elementsize);
 p_result = resultbuffer ;

while(firsthalf < endoffirsthalf && secondhalf < endofsecondhalf ){

if((*p_cmp_f)(firsthalf,secondhalf) < 0) {
memcopy(p_result , firsthalf , elementsize) ;
firsthalf += elementsize ;
} else{
memcopy(p_result , secondhalf , elementsize);
secondhalf += elementsize ;
}

p_result += elementsize ;

}
while(firsthalf < endoffirsthalf){
memcopy(p_result,firsthalf,elementsize) ;
firsthalf += elementsize ;
p_result += elementsize ;

}

while( secondhalf < endofsecondhalf){
memcopy(p_result , secondhalf , elementsize ) ;
secondhalf += elementsize ;
p_result += elementsize ;

}
memcopy(data,resultbuffer, n * elementsize) ;
free(resultbuffer) ;


}

first i make an array of 20 points then i find the minimum point and then find the angle of each point with respect to the minimum point and put in in the t field of each point then i try to sort them using merge sort by their angle but i don't know if its really sorting them correctly

[rubberman]

Ok. This is a start. Give me a bit of time to analyze your code, in light of the requirements. Dinner time for me now... :-)

[abhimanipal]

Can you print the Output of the merge sort ?
Also how many points are present in the input ?

[rockerjhr]

i can run it and the output is

Points are:

(3,6)
(17,15)
(13,15)
(6,12)
(9,1)
(2,7)
(10,19)
(3,6)
(0,6)
(12,16)
(11,8)
(7,9)
(2,10)
(2,3)
(7,15)
(9,2)
(2,18)
(9,7)
(13,16)
(11,2)
Minimum point is (9,1)

SORTED points are:

(7,15)
(7,9)
(6,12)
(2,18)
(2,10)
(2,7)
(3,6)
(3,6)
(0,6)
(2,3)
(11,2)
(17,15)
(11,8)
(13,15)
(13,16)
(12,16)
(10,19)
(9,7)
(9,2)
(9,1)

[rockerjhr]

help? im thinking of implementing the stack using a linked list the pushing and poping points should be easier

[rockerjhr]

nice i havent gotten any replies

[raptr_dflo]

Hey rockerjhr.

First of all, a little less attitude would be great. There are many experienced programmers on here, but not all of them are mathematicians. And they're all answering questions in their spare time, because they care.

I got as far as hand-plotting your sorted points, and they appear to be correctly ordered, except that if you consider your minimum point (which I'll call #0) is at the minimum Y (or somewhere near the "south pole" on a map of the world), then the rest of the points start near just off of "due north", proceeding counter-clockwise to "west", and picking up again at "east" before continuing to exactly "due north".

Your theta() algorithm, as posted, first divides by deltax, and then later checks whether it was zero. Might want to fix that! But also, think about where your points are: if you're starting from the minimum Y value (and minimum X within that), then other points can only be "due east", or farther north, around towards the west, but can't be "due west" or anywhere south. So a more useful value would be atan(-deltax/deltay), returning 0 if deltay is zero. Do you see why (considering various points on our "map of the earth")?

Your mergesort() seems to be working just fine, but it's designed to be completely generic and reusable in any context. Since you're including it in your own code (instead of, say, compiling it into a library and using it separately), if you understand how it works, why not code it so that it takes an array of your "point" types directly? If you don't understand how it works, that's fine, but maybe write a sort() method that you -do- understand.

After that, what do you think you need to do next?

As far "pushing and popping points should be easier", I suppose it depends on whether you grok which points to push and when to pop them! I'm not going to research Graham's algorithm (but found an apparently very-readable explanation here: http://en.wikipedia.org/wiki/Graham_scan), and it doesn't look as though a stack is necessary, but I can see how it could potentially be used.

Good luck, and I'll try to remember to check back sooner rather than later.

[rockerjhr]

"Your mergesort() seems to be working just fine, but it's designed to be completely generic and reusable in any context."

thats because last semester i was taking a course in data structures and we were learning about sorting and polymorphism and the polymorphic mergesort was one of the assignments so i thought what the heck might aswell use it here so yes i do know how it works was just too lazy and reused code i already had created.

im looking at the rest of your suggestions thank you for the reply i will use it to correct my errors.

I dont now what they have in wikipedia but this is the general algorithm :
normal graham scan results closed polygon:
GRAHAM-SCAN(Q)[CLRS]
let p0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie
let_p1, p2, . . . , pm_ be the remaining points in Q,
sorted by polar angle in counterclockwise order around p0 (if more than one point has the same angle, remove all but the one that is farthest from p0)
PUSH(p0, S)
PUSH(p1, S)
PUSH(p2, S)
for i ← 3 to m
do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and pi makes a nonleft turn
do POP(S)
PUSH(pi , S)
return S

[raptr_dflo]

Ah, well, if you've written your own polymorphic mergesort, that's different. By all means go ahead and use it! :)

"... sorted by polar angle in counterclockwise order around p0"

I think what I've given you should resolve the sorting issue. The stack operations are clear enough, so that just leaves the magic inherent in

"the angle formed by points NEXT-TO-TOP(S), TOP(S), and p_i makes a nonleft turn".

Give a yell here if I can be of more help.