pelqhull.h

Gambit 是一个游戏库理论软件

/* ----------------------------------------------
-setT- a set of anything
*/

struct setT {
  unsigned int maxsize; /* maximum number of elements (except NULL) */
  void *e[1];           /* array of pointers, tail is NULL */
                        /* last slot (unless NULL) is actual size+1 
                           e[maxsize]==NULL or e[e[maxsize]-1]==NULL */
};


/* =========== -macros- ========================= */

/*-----------------------------------------------
-FOREACHsetelement_(type, set, variable)- define FOREACH iterator
    variable is NULL at end of loop
    assumes *variable and **variablep are declared
    variablep is one beyond variable.  
    to repeat an element,
          variablep--; / *repeat* /
    use FOREACHsetelement_i_() if need index or include NULLs
    WARNING: strange behavior if don't use braces when nested

-FOREACHsetelement_i_(type, set, variable)- define FOREACH iterator
    assumes *variable, variable_n, and variable_i are declared
    variable_i is index, variable_n is qh_setsize()
    variable may be NULL inside looop
    variable is NULL at end of loop
    variable_i--; variable_n-- repeats for deleted element

-FOREACHsetelementreverse_
    same as FOREACHsetelement but returns elements in reverse order
    uses 'int variabletemp'

-FOREACHsetelementreverse12_
    same as FOREACHsetelement but returns e[1], e[0], e[2], e[3],

-FOREACHelem_(set)- for each element in a set of elements
-FOREACHset_(sets)- for each set in a set of sets
-SETindex_(set,elem)- returns index for iterated elem in set
*/
#define FOREACHsetelement_(type, set, variable) \
        if (set || (variable= NULL)) for(\
          variable##p= (type **)&((set)->e[0]); \
	  (variable= *variable##p++);)
#define FOREACHsetelement_i_(type, set, variable) \
        if (set || (variable= NULL)) for (\
          variable##_i= 0, variable= (type *)((set)->e[0]), \
                   variable##_n= qh_setsize(set);\
          variable##_i < variable##_n;\
          variable= (type *)((set)->e[++variable##_i]) )
#define FOREACHsetelementreverse_(type, set, variable) \
        if (set || (variable= NULL)) for(\
	   variable##temp= qh_setsize(set)-1, variable= qh_setlast(set);\
	   variable; variable= \
	   ((--variable##temp >= 0) ? SETelem_(set, variable##temp) : NULL))
#define FOREACHsetelementreverse12_(type, set, variable) \
        if (set || (variable= NULL)) for(\
          variable##p= (type **)&((set)->e[1]); \
	  (variable= *variable##p); \
          variable##p == ((type **)&((set)->e[0]))?variable##p += 2: \
	      (variable##p == ((type **)&((set)->e[1]))?variable##p--:variable##p++))
#define FOREACHelem_(set) FOREACHsetelement_(void, set, elem)
#define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set)
#define SETindex_(set, elem) ((void **)elem##p - (void **)&(set)->e[1])

/*-----------------------------------------------
-SETelem_(set, n)- return the n'th element of set
      assumes that n is valid [0..size] and that set is defined
      may need a type cast
      
-SETelemaddr_(set, n, type)-return address of the n'th element of a set
      assumes that n is valid [0..size] and set is defined

-SETfirst_(set)- return first element of set
-SETsecond_(set)- return second element of set
-SETaddr_(set, type)-   return address of set's elements
*/
#define SETelem_(set, n)           ((set)->e[n])
#define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n])))
#define SETfirst_(set)             ((set)->e[0])
#define SETsecond_(set)            ((set)->e[1])
#define SETaddr_(set,type)	   ((type **)(&((set)->e[0])))

/*-----------------------------------------------
-SETreturnsize_(set, size) - return size of a set
      set must be defined
      use qh_setsize(set) unless speed is critical

-SETempty_(set) - return true (1) if set is empty
      set may be NULL
*/
#define SETreturnsize_(set, size) (((size)= (int)((set)->e[(set)->maxsize]))?(--(size)):((size)= (set)->maxsize))
#define SETempty_(set) 	          (!set || (SETfirst_(set) ? 0:1))

/* ======= -functions =========== 

   see set.c for function definitions

	Add functions
-setaddsorted	    adds an element to a sorted set
-setaddnth	    adds newelem as n'th element of sorted or unsorted set
-setappend	    appends an element to a set
-setappend_set      appends a set to a set
-setappend2ndlast   makes newelem the next to the last element in set
-setlarger	    returns a larger set that contains elements of *setp
-setreplace	    replaces oldelem in set with newelem
-setunique	    add an element if not already in set

	Access and predicate functions	
-setin		    returns 1 if setelem is in a set, 0 otherwise
-setindex	    returns the index of elem in set.   If none, returns -1
-setlast	    return last element of set or NULL
-setequal	    returns 1 if two sorted sets are equal, otherwise returns 0
-setequal_except    returns 1 if two sorted sets are equal except at element
-setequal_skip	    returns 1 if two sorted sets are equal except for skips

	Delete functions
-setdel		    deletes oldelem from unsorted set.
-setdelsorted	    deletes oldelem from sorted set
-setdelnth	    delete and return nth element from unsorted set
-setdelnthsorted    delete and return nth element from sorted set
-setdellast	    delete and return last element from set or NULL
-setnew_delnthsorted create a sorted set not containing nth element

	Allocation and deallocation functions
-setnew		    create a new set
-setfree	    free the space occupied by a sorted or unsorted set
-setfreelong	    frees a set only if it's in long memory

	Temporary set functions
-settemp	    return a stacked, temporary set
-settempfree	    free temporary set at top of qhmem.tempstack
-settemppop	    pop qhmem.tempstack (makes temporary set permanent)
-settemppush	    push temporary set unto qhmem.tempstack (makes it temporary)
-settempfree_all    free all temporary sets in qhmem.tempstack

	Other functions
-setsize	    returns the size of a set
-setcopy	    copies a sorted or unsorted set into another
-setcheck	    check set for validity
-setprint	    print set elements to fp
-settruncate        truncate set to size elements
-setzero            zero remainder of set and set to maximum size
*/

/*---------- -prototypes in alphabetical order -----------*/

void  qh_setaddsorted(setT **setp, void *elem);
void  qh_setaddnth(setT **setp, int nth, void *newelem);
void  qh_setappend(setT **setp, void *elem);
void  qh_setappend_set(setT **setp, setT *setA);
void  qh_setappend2ndlast(setT **setp, void *elem);
void  qh_setcheck(setT *set, char */* typename: GIVES ERROR */, int id);
setT *qh_setcopy(setT *set, int extra);
void *qh_setdel(setT *set, void *elem);
void *qh_setdellast(setT *set);
void *qh_setdelnth(setT *set, int nth);
void *qh_setdelnthsorted(setT *set, int nth);
void *qh_setdelsorted(setT *set, void *newelem);
int   qh_setequal(setT *setA, setT *setB);
int   qh_setequal_except (setT *setA, void *skipelemA, setT *setB, void *skipelemB);
int   qh_setequal_skip (setT *setA, int skipA, setT *setB, int skipB);
void  qh_setfree(setT **set);
void  qh_setfreelong(setT **set);
int   qh_setin(setT *set, void *setelem);
int   qh_setindex(setT *set, void *setelem);
void  qh_setlarger(setT **setp);
void *qh_setlast(setT *set);
setT *qh_setnew(int size);
setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend);
void  qh_setprint(FILE *fp, char* string, setT *set);
void  qh_setreplace(setT *set, void *oldelem, void *newelem);
int   qh_setsize(setT *set);
setT *qh_settemp(int setsize);
void qh_settempfree(setT **set);
void qh_settempfree_all(void);
setT *qh_settemppop(void);
void qh_settemppush(setT *set);
void qh_settruncate (setT *set, int size);
int qh_setunique (setT **set, void *elem);
void qh_setzero (setT *set, int index, int size);

/**** end set.h ****/

/**************************************************************************/
/************** definitions and signatures from geom.h ********************/
/**************************************************************************/

/* ============ -macros- ======================== */

/*----------------------------------------------
-fabs_(a)          returns the absolute value of a
-fmax_(a,b)        returns the maximum value of a and b
-fmin_(a,b)        returns the minimum value of a and b
-maximize_(maxval, val)  sets maxval to val if greater
-minimize_(minval, val)  sets minval to val if less
*/
#define fabs_(a) (((a) < 0) ? -(a):(a))
#define fmax_(a,b)  ( (a) < (b) ? (b) : (a) )
#define fmin_(a,b)  ( (a) > (b) ? (b) : (a) )
#define maximize_(maxval, val) {if ((maxval) < (val)) (maxval)= (val);}
#define minimize_(minval, val) {if ((minval) > (val)) (minval)= (val);}

/*-----------------------------------------------
-det2_(a1, a2, 		2-d determinate
       b1, b2)
-det3_(a1, a2, a3,      3-d determinate
       b1, b2, b3,
       c1, c2, c3)
*/
#define det2_(a1,a2,b1,b2) ((a1)*(b2) - (a2)*(b1))
#define det3_(a1,a2,a3,b1,b2,b3,c1,c2,c3) ( (a1)*det2_(b2,b3,c2,c3) \
		- (b1)*det2_(a2,a3,c2,c3) + (c1)*det2_(a2,a3,b2,b3) )  

/*-----------------------------------------------
-dX, dY, dZ- coordinate differences given row pointers rows[]
*/
#define dX(p1,p2)  (*(rows[p1]) - *(rows[p2]))
#define dY(p1,p2)  (*(rows[p1]+1) - *(rows[p2]+1))
#define dZ(p1,p2)  (*(rows[p1]+2) - *(rows[p2]+2))
#define dW(p1,p2)  (*(rows[p1]+3) - *(rows[p2]+3))

/* ======= -functions =========== 

   see geom.c for definitions

      	Geometric functions
-crossproduct   compute the cross product of 2 3-d vectors
-determinant    compute the determinant of a square matrix
-detsimplex     return determinate of a simplex of points
-divzero        divide by a number that's nearly zero
-gausselim      Gaussian elimination with partial pivoting
-getangle       return cosine of angle (dot product of two qh hull_dim vectors)
-gram_schmidt   implements Gram-Schmidt orthogonalization by rows
-inthresholds   return True if normal within qh lower_/upper_threshold
-maxabsval      return max absolute value of a vector
-maxsimplex	determines maximum simplex for a set of points 
-minabsval     return min absolute value of a dim vector
-normalize      normalize a vector
-pointdist      return distance between two points
-printmatrix    print matrix given by row vectors
-printpoints    print pointids for a set of points starting at index 
-projectpoints  project points along one or more dimensions
-randomfactor	return a random factor within qh RANDOMdistmax of 1.0
-randommatrix   generate a random dimXdim matrix in range (-1,1)
-rotatepoints   rotate numpoints points by a row matrix
-scalepoints    scale points to new lowbound and highbound
-sethyperplane_det return hyperplane for oriented simplex, uses determinates
-sethyperplane_gauss return hyperplane for oriented simplex, uses Gaussian elimination
-voronoi_center return Voronoi center for a set of points

      	Qhull's geometric functions
-backnormal     solve for normal x using back substitution over rows U
-distplane      return distance from point to facet (>0 if point is above facet)
-facetcenter    return Voronoi center for a facet's vertices
-findbest	find visible facet for a point starting at a facet
-findgooddist   find best good facet visible for point from facet
-getcenter      return arithmetic center of a set of vertices
-getcentrum     return centrum for a facet
-maxmin         return max/min points for each dim., sets max roundoff errors
-orientoutside  make facet outside oriented via qh interior_point
-projectinput   project input using qh DELAUNAY and qh low_bound/high_bound
-projectpoint   project point onto a facet by distance
-rotateinput    rotate input using row matrix
-scaleinput     scale input using qh low_bound/high_bound
-setfacetplane  sets the hyperplane for a facet
*/

/*---------- -prototypes in alphabetical order -----------*/


void    qh_backnormal (realT **rows, int numrow, int numcol, boolT sign, coordT *normal, boolT *nearzero);
void    qh_crossproduct (int dim, realT vecA[3], realT vecB[3], realT vecC[3]);
realT 	qh_determinant (realT **rows, int dim, boolT *nearzero);
realT   qh_detsimplex (pointT *apex, setT *points, int dimension, boolT *nearzero);
void	qh_distplane (pointT *point, facetT *facet, realT *dist);
realT   qh_divzero(realT numer, realT denom, realT mindenom1, boolT *zerodiv);
pointT *qh_facetcenter (setT *vertices);
facetT *qh_findbest (pointT *point, facetT *facet, boolT bestoutside,
		unsigned firstid, realT *dist, boolT *isoutside, int *numpart);
facetT *qh_findgooddist (pointT *point, facetT *facetA, realT *distp);
void 	qh_gausselim(realT **rows, int numrow, int numcol, boolT *sign, boolT *nearzero);
realT   qh_getangle(pointT *vect1, pointT *vect2);
pointT *qh_getcenter(setT *vertices);
pointT *qh_getcentrum(facetT *facet);
boolT   qh_gram_schmidt(int dim, realT **rows);