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 1,355 Nearly a Posting Virtuoso Featured Poster

rockerjhr -3 Junior Poster in Training

rubberman 1,355 Nearly a Posting Virtuoso Featured Poster

rockerjhr -3 Junior Poster in Training

rubberman 1,355 Nearly a Posting Virtuoso Featured Poster

rockerjhr -3 Junior Poster in Training

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

Edited by rockerjhr because:

*n/a* rubberman 1,355 Nearly a Posting Virtuoso Featured Poster

abhimanipal 91 Master Poster

Can you print the Output of the merge sort ?

Also how many points are present in the input ?

rockerjhr -3 Junior Poster in Training

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 -3 Junior Poster in Training

rockerjhr -3 Junior Poster in Training

nice i havent gotten any replies

raptr_dflo 48 Posting Pro

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 -3 Junior Poster in Training

"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

Edited by rockerjhr because:

*n/a* raptr_dflo 48 Posting Pro

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.