Contents

  1. hull.h
  2. hull.c
  3. tclhull.c
  4. hull.tcl

hull.h 1/4

[
top][prev][next]
#ifndef _HULL_H_
#define _HULL_H_

#ifdef __cplusplus
extern "C" {
#endif

typedef struct { 
    float x;
    float y;
    int id;
} point;

typedef struct {
    point **stack;
    int stack_pointer;
    int stack_cap;
} point_stack;

#define NEG(x)  (((x)<0)?1:0)
#define left_turn(p0,p1,p2) ( NEG(((p2)->x-(p0)->x)*((p1)->y-(p0)->y)- \
	    ((p2)->y-(p0)->y)*((p1)->x-(p0)->x)) )

#define POS(x)  ((x)>0?1:0)
#define clockwise(p0,p1,p2) ( (((p1)->x-(p0)->x)*((p2)->y-(p0)->y)- \
	    ((p1)->y-(p0)->y)*((p2)->x-(p0)->x)) )

#define ZERO(x) (!(x))
#define collinear(p0,p1,p2) ( ZERO(((p2)->x-(p0)->x)*((p1)->y-(p0)->y)- \
	    ((p2)->y-(p0)->y)*((p1)->x-(p0)->x)) )


point* pop(point_stack*);
void destroy_stack(point_stack *);
point_stack *graham_scan(point *q, int q_len);

#ifdef __cplusplus
}
#endif

#endif/*_HULL_H_*/


hull.c 2/4

[
top][prev][next]
#include <stdio.h>
#include <stdlib.h>
#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; i<q_len; ++i) {
	if(q[i].y < p0->y) {
	    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; i<q_len; ++i) {
	if(q+i != p0)
	    plist[j++] = q+i;
    }

    // sort remaining points by polar angle in counterclockwise order around p0
    qsort(plist, q_len-1, sizeof(point*), polar_angle);


    // if two points are collinear with p0, eliminate the nearer one
    j=0;
    for(i=0; i<q_len-2; ++i) {
	if(plist[i] && plist[i+1] && collinear(p0, plist[i], plist[i+1])) {
	    if((abs(plist[i]->x-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<q_len-1; ++i){
	    k = i+1;
	    while(plist[i] == NULL){
		plist[i] = plist[k];
		plist[k] = NULL;
		++k;
		if(k==q_len-2)
		    goto finish;
	    }
	}

finish:
	q_len = i;
    }

    push(s, p0);
    push(s, plist[0]);
    push(s, plist[1]);

    for(i=2; i<q_len; ++i) {

	//while the angle formed by points next_to_top,top and pi makes nonlefturn
	point *nt=next_to_top(s);
	point *t=top(s);
	while(!(left_turn(nt, t, plist[i]))){
	    pop(s);
	    nt = next_to_top(s);
	    t = top(s);
	}
	push(s, plist[i]);
    }

    free(plist);
    return s;
}


tclhull.c 3/4

[
top][prev][next]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <tcl.h>
#include "hull.h"

int ConvexHullObjCmd(ClientData data, Tcl_Interp *interp, int objc, Tcl_Obj *const objv[])
{
    Tcl_Obj *result;
    int num_points;

    int i;
    int list_ele_objc;
    Tcl_Obj **list_ele_obj;
    point *p;
    point_stack *s;

    Tcl_Obj *hull_obj = NULL;

    if(objc !=2 ) {
	Tcl_WrongNumArgs(interp, 1, objv, "?point_list?");
	return TCL_ERROR;
    }

    Tcl_ListObjLength(interp, objv[1], &num_points);

    list_ele_objc = num_points;
    if( Tcl_ListObjGetElements(interp, objv[1], &list_ele_objc, &(list_ele_obj))!=TCL_OK) {
	return TCL_ERROR;
    }


    num_points /= 2;
    p = (point*)ckalloc(sizeof(point)*num_points);
    for(i=0; i<num_points; i++) {
	double x, y;
	if(Tcl_GetDoubleFromObj(interp, list_ele_obj[2*i], &x) != TCL_OK) {
	    return TCL_ERROR;
	}
	if(Tcl_GetDoubleFromObj(interp, list_ele_obj[2*i+1], &y) != TCL_OK) {
	    return TCL_ERROR;
	}
		
	p[i].x = x;
	p[i].y = y;
    }
    
    s = graham_scan(p, num_points);

    i = 0;
    if(s) {
	hull_obj = Tcl_NewListObj(0, NULL);
	while(s->stack_pointer) {
	    point *q = pop(s);
	    double x, y;
	    x = q->x; y = q->y;
	    Tcl_ListObjAppendElement(interp, hull_obj, Tcl_NewDoubleObj(x));
	    Tcl_ListObjAppendElement(interp, hull_obj, Tcl_NewDoubleObj(y));
	}
	destroy_stack(s);
    }

    ckfree((char*)p);

    Tcl_SetObjResult(interp, hull_obj);

    return TCL_OK;
}

int Convexhull_Init(Tcl_Interp *interp)
{
    if (Tcl_InitStubs(interp, "8.3", 0) == NULL) {
	return TCL_ERROR;
    }

    Tcl_CreateObjCommand(interp, "convexhull", ConvexHullObjCmd, (ClientData)NULL, (Tcl_CmdDeleteProc *)NULL);

    Tcl_PkgProvide(interp, "tclhull", "1.0");
    return TCL_OK;
}


hull.tcl 4/4

[
top][prev][next]
#!/usr/bin/wish
#
#

load /u/bh/work/convexhull/tclhull.so convexhull

proc add_point { c x y } {
	global input_list

	set psize 2

	lappend input_list $x $y
	$c create rect [expr $x-$psize] [expr $y-$psize] [expr $x+$psize] [expr $y+$psize] -fill red

	if { [ llength $input_list ] >= 6 } {
	    set output_list [convexhull $input_list]
    	    lappend output_list [lindex $output_list 0] [lindex $output_list 1]
	    $c delete hull_line
    	    $c create line $output_list -tag hull_line
	}
}

proc clear_point { c } {
	global input_list

	$c delete all
	set input_list {}
}

set canv [canvas .c -height 400 -width 400]
button .b_exit -text exit -command exit
button .b_clear -text clear -command { clear_point $canv}
pack .c .b_clear .b_exit
bind .c <Button-1> {add_point %W %x %y}

Generated by GNU enscript 1.6.1.