pelqhull.h

Gambit 是一个游戏库理论软件

boolT   qh_inthresholds (coordT *normal, realT *angle);
realT  *qh_maxabsval (realT *normal, int dim);
setT   *qh_maxmin(pointT *points, int numpoints, int dimension);
void    qh_maxsimplex (int dim, setT *maxpoints, pointT *points, int numpoints, setT **simplex);
realT   qh_minabsval (realT *normal, int dim);
void    qh_normalize (coordT *normal, int dim, boolT toporient);
boolT   qh_orientoutside (facetT *facet);
coordT  qh_pointdist(pointT *point1, pointT *point2, int dim);
void    qh_printmatrix (FILE *fp, char *string, realT **rows, int numrow, int numcol);
void    qh_printpoints (FILE *fp, char *string, setT *points);
void    qh_projectinput (void);
pointT *qh_projectpoint(pointT *point, facetT *facet, realT dist);
void 	qh_projectpoints (signed char *project, int n, realT *points, 
             int numpoints, int dim, realT *newpoints, int newdim);
realT   qh_randomfactor (void);
void    qh_randommatrix (realT *buffer, int dim, realT **row);
void    qh_rotateinput (realT **rows);
void    qh_rotatepoints (realT *points, int numpoints, int dim, realT **rows);
void    qh_scaleinput (void);
void 	qh_scalepoints (pointT *points, int numpoints, int dim,
  		realT *newlows, realT *newhighs);
void    qh_setfacetplane(facetT *newfacets);
void 	qh_sethyperplane_det (int dim, coordT **rows, coordT *point0, 
         	boolT toporient, coordT *normal, realT *offset);
void 	qh_sethyperplane_gauss (int dim, coordT **rows, pointT *point0, 
	     boolT toporient, coordT *normal, coordT *offset, boolT *nearzero);
pointT *qh_voronoi_center (int dim, setT *points);

/**** end geom.h ****/


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

/* ============ -constants- ====================
-BESTcentrum     if > dim+n vertices, findbestneighbor tests centrums (faster)
                 else, findbestneighbor test all vertices (much better merges)

-BESTnonconvex   if > dim*n neighbors, findbestneighbor tests nonconvex ridges
                   needed because findbestneighbor is slow for large facets
		   
-MAXnewmerges    if >n newmerges, merge_nonconvex calls reducevertices_centrums
                   needed because postmerge can merge many facets at once

-MAXnewcentrum   if <= dim+n vertices (n approximates the number of merges),
                    reset the centrum in reducevertices_centrum 
                  needed to reduce cost and because centrums may move
		        too much if many vertices in high-d

*/
#define qh_BESTcentrum 20   /* findbestneighbor tests centrum or vertices */
#define qh_BESTnonconvex 5    /*findbestneighbor only tests nonconvex */
#define qh_MAXnewmerges 2   /*merge_nonconvex calls reducevertices_centrums*/
#define qh_MAXnewcentrum 5    /*reducevertices_centrums resets centrum */

#define qh_ANGLEredundant 6.0 /* angle for redundant merge in mergeT */
#define qh_ANGLEdegen     5.0 /* angle for degenerate facet in mergeT */
#define qh_ANGLEconcave  1.5  /* [2,4] for angle of concave facets in mergeT,
                                 may be <2 or >4 due to roundoff */

/* ============ -structures- ====================
*/

/* ----------------------------------------------
-mergeT- structure used to merge facets
*/

typedef struct mergeT mergeT;

struct mergeT {
  realT   angle;          /* angle between normals of facet1 and facet2 */
  facetT *facet1; 
  facetT *facet2;
  flagT   mergeridge:1;   /* set if merge due to qh_MERGEridge */
  flagT   newmerge:1;     /* set if new merge, for forcedmerges() */
  flagT   anglecoplanar:1; /* set if merge due to qh cos_max */
};


/* =========== -macros- =========================
-FOREACHmerge-  if qh_mergefacet() then must restart since facet_mergeset
                may change.
*/
#define FOREACHmerge_(merges) FOREACHsetelement_(mergeT, merges, merge)

/* ======= -functions and procedures- =========== 

	top-level merge functions
-merge_nonconvex   merges all nonconvex facets
-flippedmerges	   merge flipped facets into best neighbor
-forcedmerges	   merge across duplicated ridges and mutually flipped facets
-tracemerging      print trace message during post merging

	mergeset functions for identifying merges
-getmergeset_initial  initial mergeset for facets
-getmergeset	   returns facet_mergeset of facet-neighbor pairs to be merged
-degen_redundant_neighbors  append degen. and redundant neighbors to facet_mergeset
-test_appendmerge   facet/neighbor and appends to mergeset if nonconvex
-appendmergeset	   appends an entry to facet_mergeset, angle is optional
-facetdegen	   true if facet already in mergeset as a degenerate

	functions for determining the best merge
-findbest_test	   test neighbor for findbestneighbor()
-findbestneighbor  finds best neighbor (least dist) of a facet for merging
-getdistance	   returns the max and min distance of any vertex from neighbor

	functions for merging facets
-merge_degenredundant  merge degenerate and redundant facets
-mergefacet	   merges facet1 into facet2
-makeridges	   creates explicit ridges between simplicial facets
-mergeneighbors	   merges the neighbors of facet1 into facet2
-mergeridges	   merges the ridge set of facet1 into facet2
-mergevertex_neighbors merge the vertex neighbors of facet1 to facet2
-mergevertices	   merges the vertex set of facet1 into facet2
-mergevertices2d   merges vertices1 into vertices2 in 2-d case

	functions for renaming a vertex
-reducevertices_centrums reduce vertex sets and reset centrums
-rename_sharedvertex  detect and rename if shared vertex in facet
-redundant_vertex   returns true if detect and rename redundant vertex
-renamevertex	   renames oldvertex as newvertex in ridges 
-renameridgevertex renames oldvertex as newvertex in ridge
-maydropneighbor   drop neighbor relationship if no ridge between facet and neighbor
-remove_extravertices remove extra vertices in non-simplicial facets
-copynonconvex- copy non-convex flag to all ridges between same neighbors

	functions for identifying vertices for renaming
-find_newvertex    locate new vertex for renaming old vertex
-neighbor_intersections	 return intersection for vertex->neighbors
-vertexridges	   return temporary set of ridges adjacent to a vertex
-vertexridges_facet add adjacent ridges for vertex in facet
-hashridge	   add ridge to hashtable without oldvertex
-hashridge_find	   returns matching ridge in hashtable without oldvertex

	check functions
-checkridge_boundary  checks that ridges of a facet are boundaryless
*/

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

mergeT *qh_appendmergeset(facetT *facet, facetT *neighbor, realT *angle);
void 	qh_checkridge_boundary(facetT *facet);
void    qh_copynonconvex (ridgeT *atridge);
void 	qh_degen_redundant_neighbors (facetT *facet);
boolT   qh_facetdegen (facetT *facet);
vertexT *qh_find_newvertex (vertexT *oldvertex, setT *vertices, setT *ridges);
void    qh_findbest_test (boolT testcentrum, facetT *facet, facetT *neighbor,
           facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp);
facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp);
void 	qh_flippedmerges(facetT *facetlist);
void 	qh_forcedmerges(facetT *facetlist);
realT   qh_getdistance(facetT *facet, facetT *neighbor, realT *mindist, realT *maxdist);
void	qh_getmergeset(facetT *facetlist);
void 	qh_getmergeset_initial (facetT *facetlist);
void    qh_hashridge (setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex);
ridgeT *qh_hashridge_find (setT *hashtable, int hashsize, ridgeT *ridge, 
              vertexT *vertex, vertexT *oldvertex, int *hashslot);
void 	qh_makeridges(facetT *facet);
void    qh_maydropneighbor (facetT *facet);
boolT   qh_merge_degenredundant (facetT *facet1, facetT *facet2, realT *angle);
void 	qh_merge_nonconvex(void /*newfacet_list*/);
void 	qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, realT *angle);
void 	qh_mergeneighbors(facetT *facet1, facetT *facet2);
void 	qh_mergeridges(facetT *facet1, facetT *facet2);
void    qh_mergevertex_neighbors(facetT *facet1, facetT *facet2);
void	qh_mergevertices(setT *vertices1, setT **vertices);
void 	qh_mergevertices2d(setT *vertices1, setT *vertices2);
setT   *qh_neighbor_intersections (vertexT *vertex);
boolT   qh_reducevertices_centrums (void);
vertexT *qh_redundant_vertex (vertexT *vertex);
boolT   qh_remove_extravertices (facetT *facet);
vertexT *qh_rename_sharedvertex (vertexT *vertex, facetT *facet);
void	qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex);
void    qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges,
			facetT *oldfacet, facetT *neighborA);
boolT 	qh_test_appendmerge (facetT *facet, facetT *neighbor);
void    qh_tracemerging (char *string);
setT   *qh_vertexridges (vertexT *vertex);
void    qh_vertexridges_facet (vertexT *vertex, facetT *facet, setT **ridges);

/**** end merge.h ****/


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

/*-----------------------------------------------
-constants-

	for calling checkconvex()
-ALGORITHMfault   flag for checkconvex for error during buildhull
-DATAfault        flag for checkconvex for error during initialhull

	set by matchneighbor, used by matchmatch and forcedmerges
-DUPLICATEridge   flag in facet->neighbors to indicate duplicated ridge
-MERGEridge       flag in facet->neighbors to indicate merged ridge
*/

#define qh_ALGORITHMfault 0
#define qh_DATAfault 1

#define qh_DUPLICATEridge (facetT *) 1
#define qh_MERGEridge (facetT *) 2


/* ============ -structures- ====================
*/

/* ----------------------------------------------
-hashentryT- hash table entry for matching sub-ridges in makecone()
*/

typedef struct hashentryT hashentryT;

struct hashentryT {
  facetT     *facet;        /* facet */
  hashentryT *next;         /* next hash table entry for this bucket */
  unsigned    skipindex;    /* skipped vertex in facet, for orientation */
};

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

/* ----------------------------------------------
-FOREACH... and FORALL... -- standard for loops
  see qhull.h for notes
*/
#define FORALLfacet_(facetlist) if (facetlist) for(facet=(facetlist);facet && facet->next;facet=facet->next)
#define FORALLnew_facets for(newfacet=qh newfacet_list;newfacet && newfacet->next;newfacet=newfacet->next)
#define FORALLvertex_(vertexlist) for (vertex=(vertexlist);vertex && vertex->next;vertex= vertex->next)
#define FORALLvisible_facets for (visible=qh visible_list; visible && visible->visible; visible= visible->next)

#define FOREACHentry_(entries) FOREACHsetelement_(hashentryT, entries, entry)
#define FOREACHvisible_(facets) FOREACHsetelement_(facetT, facets, visible)
#define FOREACHnewfacet_(facets) FOREACHsetelement_(facetT, facets, newfacet)
#define FOREACHvertexA_(vertices) FOREACHsetelement_(vertexT, vertices, vertexA)
#define FOREACHvertexreverse12_(vertices) FOREACHsetelementreverse12_(vertexT, vertices, vertex)

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

see poly.c for definitions

	Facetlist functions
-appendfacet	    appends facet to end of qh facet_list,
-prependfacet	    prepends facet to start of facetlist
-removefacet	    unlinks facet from qh facet_list,
-clearvisible       clear facets from visible list

	Facet functions
-createsimplex	    creates a simplex of facets from a set of vertices
-makenewfacet	    creates a toporient? facet from vertices and apex
-makenewfacets	    make new facets from point, horizon facets, and visible facets
-makenew_nonsimplicial make new facets for ridges of visible facets
-makenew_simplicial make new facets for horizon neighbors
-attachnewfacets    attach new facets in qh newfacet_list to the horizon
-makeadjacencies    make adjacencies for non-simplicial facets

	Vertex, ridge, and point functions
-appendvertex	    appends vertex to end of qh vertex_list,
-removevertex	    unlinks vertex from qh vertex_list,
-clearnewvertices   clear vertices from qh newvertex_list
-point              return point for a point id, or NULL if unknown
-pointid            return id for a point, or -1 if not known
-vertexintersect    intersects two vertex sets
-vertexintersect_new intersects two vertex sets
-facetintersect	    intersect simplicial facets
-isvertex	    true if point is in the vertex set
-vertexsubset	    returns True if vertexsetA is a subset of vertexsetB
-nextridge3d	    iterate each ridge and vertex for a 3d facet
-facet3vertex	    return oriented vertex set for 3-d facet
-vertexneighhbors   for each vertex in hull, determine facet neighbors
-pointfacet	    return temporary set of facets indexed by point id
-pointvertex	    return temporary set of vertices indexed by point id

	Hashtable functions
-newhashtable	    allocates a new qh hash_table
-gethash	    return hashvalue for a set with firstindex
-matchnewfacets	    match newfacets in to their newfacet neighbors
-matchneighbor      try to match subridge of newfacet with a neighbor
-matchduplicate     try to match an unmatched duplicate ridge
-matchmatch         try to match duplicate matching pair and newfacet
-matchvertices	    tests whether a facet and hashentry match at a ridge
-printhashtable		print hash table

	Allocation and deallocation functions
-newfacet	    creates and allocates space for a facet
-newridge	    creates and a