#include #include #include "hull.h" /** * Stack operations */ point_stack *init_stack(int stack_depth) { point_stack *s = (point_stack*)malloc(sizeof(point_stack)); if(!s) { return NULL; } s->stack_pointer = 0; s->stack_cap = stack_depth; s->stack = (point**)malloc(sizeof(point*)*stack_depth); if(!(s->stack)) { free(s); return NULL; } return s; } void destroy_stack(point_stack *s) { free(s->stack); s->stack = NULL; s->stack_cap = -1; s->stack_pointer = -1; free(s); } void push(point_stack *s, point *p) { if(s->stack_pointer == s->stack_cap) { fprintf(stderr, "Stack overflow.\n"); exit(1); } s->stack[s->stack_pointer++] = p; } point *pop(point_stack *s) { if(s->stack_pointer <= 0) { fprintf(stderr, "Stack underflow.\n"); abort(); } return s->stack[--(s->stack_pointer)]; } point *top(point_stack *s) { if(s->stack_pointer <= 0) { fprintf(stderr, "Stack underflow.\n"); abort(); } return s->stack[s->stack_pointer-1]; } point *next_to_top(point_stack *s) { if(s->stack_pointer <= 1) { fprintf(stderr, "Stack underflow.\n"); abort(); } return s->stack[s->stack_pointer-2]; } static point *origin=NULL; int polar_angle(const void *a, const void *b) { const point *p1 = *(point**)a; const point *p2 = *(point**)b; float sign = clockwise(origin, p1, p2); if(sign > 0) return -1; else if(sign < 0) return 1; else return 0; } point_stack *graham_scan(point *q, int q_len) { point_stack *s; point **plist; int i, j; if(q_len <= 2) return NULL; s = init_stack(q_len); if(!s) return NULL; //find p0 with minimum y-coord point *p0 = q; for(i=1; iy) { p0 = q+i; }else if(q[i].y == p0->y) { if(q[i].x < p0->x) p0 = q+i; } } // used by the sorting routine origin = p0; plist = (point**)malloc((q_len-1)*sizeof(point*)); j=0; for(i=0; ix-p0->x)+abs(plist[i]->y-p0->y))> (abs(plist[i+1]->x-p0->x)+abs(plist[i+1]->y-p0->y))){ plist[i+1] = plist[i]; plist[i] = NULL; j++; }else{ plist[i] = NULL; j++; } } } // remove NULL pointers if(j>0) { int k; for(i=0; i