C-Code

/*******************************************
 * points.c  Einhüllende einer Punktwolke
 * gcc -Wall -o points points.c -lm -lcurses
 *******************************************/
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>
#include <math.h>
#include <curses.h>

#define MAX_POINTS 100
#define EPSILON  1.e-6


typedef struct _point {
	int x, y;
	bool isbp;
} point;

typedef struct _win_ {
	WINDOW *bord_win;
	WINDOW *draw_win;
	WINDOW *stat_win;
    int dww, dwh;          /* draw window dimensions */
} win_t;
win_t win;
point P[MAX_POINTS];

/* FUNCTIONS */

/* generate random point coorinates */
void create_points(win_t *pw, point pn[], int np) {
	int k, n, hk, hn;
	
	srand(time(NULL));
	n=0;
	while (n<np) {
		pn[n].x = (int)((long)pw->dww*rand()/RAND_MAX);
		pn[n].y = (int)((long)pw->dwh*rand()/RAND_MAX);
		pn[n].isbp = false;
	
	    /* check uniqueness */	
		hn = 1000*pn[n].y + pn[n].x;
		for (k=0; k<n; k++) {
			hk = 1000*pn[k].y + pn[k].x;
			if (hn == hk) {
			  --n;
			  break;
		    }
		}
		++n;
	}
}

/* angle between two vectors (x0,y0),(x1,y1) */
double angle(int x0, int y0, int x1, int y1) {
	double d,n;
	
	n = (double)(x1*x0 + y1*y0);
	d = sqrt((double)(x0*x0+y0*y0))*sqrt((double)(x1*x1+y1*y1));
	return (n==0.0)?M_PI_2:fabs(acos(n/((1.0+EPSILON)*d)));
}

/* prepare drawing */
int setup_screen(win_t *pw, bool winch) {
    int maxx, maxy;

    if (initscr() == NULL)
		return -2;
    nonl();
    intrflush(stdscr, false);
    erase();
    if (winch == true) refresh();

    /* set window geometry */
    getmaxyx(stdscr, maxy, maxx);
    if ((pw->bord_win = newwin(maxy-1, maxx, 0, 0)) == NULL)
		return -1;
    if ((pw->draw_win = newwin(maxy-5, maxx-6, 2, 3)) == NULL)
		return -1;
    if ((pw->stat_win = newwin(1, maxx-2, maxy-1, 1)) == NULL)
		return -1;
    
    pw->dww = maxx-6;
    pw->dwh = maxy-5;

    /* set cursor invisible */
    curs_set(0);
    return 0;
}

/* draw screen */
void repaint_frame(win_t *pw, point pn[], int np, int nph, bool closed) {
	char text[80];
	int n;

	refresh();
	
    /* draw border */
    wborder(pw->bord_win, 0, 0, 0, 0, 0, 0, 0, 0);
    wrefresh(pw->bord_win);

    /* draw status line */
	sprintf(text, "W=%d H=%d | %d Punkte | nächster Hüllpunkt: (%d,%d) | %s", 
	                pw->dww, pw->dwh, np, pn[nph].x, pn[nph].y, 
	                closed?"Hülle geschlossen":"Weiter mit Taste...");
	wclear(pw->stat_win);
    mvwaddstr(pw->stat_win, 0, 1, text);
    wrefresh(pw->stat_win);

    /* draw points */    
	for (n=0; n<np; n++)
        mvwaddch(pw->draw_win, pw->dwh-pn[n].y-1, pn[n].x, (pn[n].isbp)?'x':'o');
    wrefresh(pw->draw_win);
}

/* main */
int main(int argc, char **argv) {
	int x0, y0, x1, y1, x2, y2, ym;
	int n, n_max, n_first, n_this, n_next;
	bool found;
	double ang, ang_min;

	/* number of points */
	n_max = 0;
	if (argc > 1) n_max = atoi(argv[1]);
	if (n_max < 3) n_max = 3;
	if (n_max > MAX_POINTS)	n_max = MAX_POINTS;
		
    /* set up curses screen */
    if (setup_screen(&win, false) != 0)
		exit(EXIT_FAILURE);

	/* populate points array */ 
	create_points(&win, P, n_max);
	
    /* select first point of hull curve */	
	ym = 1000;
    for (n=0; n<n_max; n++)
		if (P[n].y < ym) {
			ym = P[n].y; 
			n_this = n;
		}
	P[n_this].isbp = true;	
    x1 = P[n_this].x;
    y1 = P[n_this].y;
    x0 = x1 - 1;
    y0 = y1;
    n_first=n_this;
	repaint_frame(&win, P, n_max, n_first, false);
    getch();

    for (;;) {
		ang_min = M_PI;
		n_next=-1;
		found=false;
		for (n=0; n<n_max; n++) {
			if (n==n_this) continue;
				
			x2 = P[n].x;
			y2 = P[n].y;
			ang = angle(x1-x0, y1-y0, x2-x1, y2-y1);
			if (ang < ang_min-EPSILON) {
				ang_min = ang;
				n_next = n;
				found=true;
			}
		}
		if (found) {
			P[n_next].isbp = true;
			x0 = x1;
			y0 = y1;
			x1 = P[n_next].x;
			y1 = P[n_next].y;
			n_this=n_next;
			repaint_frame(&win, P, n_max, n_next, (n_next==n_first));
			getch();
		}
		if (n_next==n_first) break;
	}
    endwin();

	for (n=0; n<n_max; n++)
		fprintf(stderr, "#%02d : %3d , %2d  %c\n", 
		        n, P[n].x, P[n].y, (P[n].isbp)?'x':' ');		
    return 0;
}