www.pudn.com > hull.zip > hull.h

/* hull.h */
/*
 * Ken Clarkson wrote this.  Copyright (c) 1995 by AT&T..
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

#ifndef HDR
#define HDR 1

#include "points.h"
#include "stormacs.h"

#define MAXDIM 8
#define BLOCKSIZE 100000
#define MAXBLOCKS 1000
#define DEBUG -7
#define CHECK_OVERSHOOT 1

extern char tmpfilenam[L_tmpnam];

extern short check_overshoot_f;

FILE* efopen(char *, char *);



extern FILE *DFILE;

#define DEBS(qq)  {if (DEBUG>qq) {
#define EDEBS }}
#define DEBOUT DFILE
#define DEB(ll,mes)  DEBS(ll) fprintf(DEBOUT,#mes "\n");fflush(DEBOUT); EDEBS
#define DEBEXP(ll,exp) DEBS(ll) fprintf(DEBOUT,#exp "=%G\n", (double) exp); fflush(DEBOUT); EDEBS
#define DEBTR(ll) DEBS(ll) fprintf(DEBOUT, __FILE__ " line %d \n" ,__LINE__);fflush(DEBOUT); EDEBS
#define warning(lev, x) 					\
	{static int messcount;					\
		if (++messcount<=10) {DEB(lev,x) DEBTR(lev)}	\
		if (messcount==10) DEB(lev, consider yourself warned) \
	}							\


#define SBCHECK(s) /*								\
{double Sb_check=0;								\
int i;										\
	for (i=1;ineigh[i].basis)				\
					Sb_check+=s->neigh[i].basis->sqb;		\
	if ((float)(Sb_check - s->Sb) !=0.0)							\
	{DEBTR DEB(bad Sb); DEBEXP(s->Sb) DEBEXP(Sb_check);print_simplex(s); exit(1);}}*/\





typedef point site;

extern site p; 			/* the current site */

extern Coord hull_infinity[10];	/* point at infinity for Delaunay triang */

extern int
	rdim,	/* region dimension: (max) number of sites specifying region */
	cdim,	/* number of sites currently specifying region */
	site_size, /* size of malloc needed for a site */
	point_size;  /* size of malloc needed for a point */



typedef struct basis_s {
	struct basis_s *next; /* free list */
	int ref_count;	/* storage management */
	int lscale;    /* the log base 2 of total scaling of vector */
	Coord sqa, sqb; /* sums of squared norms of a part and b part */
	Coord vecs[1]; /* the actual vectors, extended by malloc'ing bigger */
} basis_s;
STORAGE_GLOBALS(basis_s)


typedef struct neighbor {
	site vert; /* vertex of simplex */
	struct simplex *simp; /* neighbor sharing all vertices but vert */
	basis_s *basis; /* derived vectors */
} neighbor;

typedef struct simplex {
	struct simplex *next;	/* free list */
	long visit;		/* number of last site visiting this simplex */
/*	float Sb; */
	short mark;
	basis_s* normal;	/* normal vector pointing inward */
	neighbor peak;		/* if null, remaining vertices give facet */
	neighbor neigh[1];	/* neighbors of simplex */
} simplex;
STORAGE_GLOBALS(simplex)



typedef struct fg_node fg;
typedef struct tree_node Tree;
struct tree_node {
    Tree *left, *right;
    site key;
    int size;   /* maintained to be the number of nodes rooted here */
    fg *fgs;
    Tree *next; /* freelist */
};

STORAGE_GLOBALS(Tree)


typedef struct fg_node {
	Tree *facets;
	double dist, vol;	/* of Voronoi face dual to this */
	fg *next;  		/* freelist */
	short mark;
	int ref_count;
} fg_node;
	
STORAGE_GLOBALS(fg)


typedef void* visit_func(simplex *, void *);
typedef int test_func(simplex *, int, void *);
typedef void out_func(point *, int, FILE*, int);


/* from driver, e.g., hullmain.c */

typedef site gsitef(void);

extern gsitef *get_site;	

typedef long site_n(site);
extern site_n *site_num;

extern double mult_up;

extern Coord mins[MAXDIM], maxs[MAXDIM];

typedef short zerovolf(simplex *);

extern double Huge;


/* from segt.c or ch.c */

simplex *build_convex_hull(gsitef*, site_n*, short, short);

void free_hull_storage(void);

int sees(site, simplex *);

void get_normal(simplex *s);

int out_of_flat(simplex*, site);

void set_ch_root(simplex*);

void print_site(site, FILE*);

void print_normal(simplex*);

visit_func check_marks;

double find_alpha(simplex*);
test_func alph_test;
void* visit_outside_ashape(simplex*, visit_func);

void get_basis_sede(simplex *);


	/* for debugging */
int check_perps(simplex*);

void find_volumes(fg*, FILE*);

#define MAXPOINTS 10000
extern short mi[MAXPOINTS], mo[MAXPOINTS];


/* from hull.c */


void *visit_triang_gen(simplex *, visit_func, test_func*);
void *visit_triang(simplex *, visit_func);
void* visit_hull(simplex *, visit_func);

neighbor *op_simp(simplex *a, simplex *b);

neighbor *op_vert(simplex *a, site b);

simplex *new_simp(void);

void buildhull(simplex *);


/* from io.c */

void panic(char *fmt, ...);

typedef void print_neighbor_f(FILE*, neighbor*);
extern print_neighbor_f
	print_neighbor_full,
	print_neighbor_snum;

void check_triang(simplex*);

void check_new_triangs(simplex *);

void print_extra_facets(void);

void *print_facet(FILE*, simplex*, print_neighbor_f*);

void print_basis(FILE*, basis_s*);

void *print_simplex_f(simplex*, FILE*, print_neighbor_f*);

void *print_simplex(simplex*, void*);

void print_triang(simplex*, FILE*, print_neighbor_f*);


out_func vlist_out, ps_out, cpr_out, mp_out, off_out;
	/* functions for different formats */

visit_func facets_print, afacets_print, ridges_print;
	/* to print facets, alpha facets, ridges */

void print_edge_dat(fg *, FILE *);


/* from pointops.c */

void print_point(FILE*, int, point);
void print_point_int(FILE*, int, point);
Coord maxdist(int,point p1, point p2);



/* from rand.c */

double double_rand(void);
void init_rand(long seed);


/* from fg.c, for face graphs */

fg *build_fg(simplex*);

void print_fg(fg*, FILE *);

void print_fg_alt(fg*, FILE *, int);

void print_hist_fg(simplex *, fg*, FILE *);

/*  void arena_check(void); */	/* from hobby's debugging malloc  */


#endif