Contents
- hull.h
- hull.c
- tclhull.c
- 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.