qhull.h

这是一个新的用于图像处理的工具箱

/* qhull.h -- user-level header file for using qhull.a library
   
   see README, qhull_a.h
   
   see user.h for all user defineable constants

   copyright (c) 1993-1995, The Geometry Center

   defines qh_qh, global data structure for qhull.  
   
   NOTE: access to qh_qh is via the 'qh' macro.  This allows
   qh_qh to be either a pointer or a structure.  An example
   of using qh is "qh DROPdim" which accesses the DROPdim
   field of qh_qh.  Similarly, access to qh_qhstat is via
   the 'qhstat' macro.
   
   includes function prototypes for qhull.c, geom.c, global.c, io.c, user.c

   use mem.h for mem.c
   use set.h for set.c
   
   see unix.c for an example of using qhull.h
   
   recompile qhull if you change this file
*/

#ifndef qhDEFqhull
#define qhDEFqhull 1

/* =========================== -included files ============== */

#include <setjmp.h>
#include <float.h>
#include <time.h>

#if __MWERKS__
#include  <SIOUX.h>
#include  <Files.h>
#include	<Desk.h>
#endif

#include "user.h"      /* user defineable constants */

/* ============ -types- ==================== 

   Note: could use 'float' for data and 'double' for calculations (realT vs. coordT)
        This requires many type casts, and adjusted error bounds.
        Also C compilers may do expressions in double anyway.

*/


#define coordT realT  /* for stored coordinates and coefficients */
#define pointT coordT                 /* array of hull_dim coordinates */
#define flagT unsigned int            /* Boolean flag */
#define boolT unsigned int            /* Boolean value, nothing much is portable */
#ifdef False
#undef False
#endif
#ifdef True
#undef True
#endif
#define False 0
#define True 1

/* -CENTERtype to distinguish facet->center */
typedef enum {qh_ASnone= 0, qh_ASvoronoi, qh_AScentrum} qh_CENTER;

/* -output formats for printing (qh PRINTout).
notes:
  some of these names are similar to qh names.  The similar names are only
  used in switch statements in qh_printbegin() etc.
*/
typedef enum {qh_PRINTnone= 0, qh_PRINTarea, qh_PRINTaverage, 
  qh_PRINTcoplanars, qh_PRINTcentrums, 
  qh_PRINTfacets, qh_PRINTfacets_xridge, 
  qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors, 
  qh_PRINTnormals, qh_PRINTouter, qh_PRINTincidences, 
  qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff, 
  qh_PRINToptions, qh_PRINTpointintersect, qh_PRINTpointnearest,
  qh_PRINTpoints, qh_PRINTqhull,
  qh_PRINTsize, qh_PRINTsummary, qh_PRINTvertices, qh_PRINTvneighbors,
  qh_PRINTEND} qh_PRINT;

/*---------------------------
       arguments
*/
#define qh_ALL 	    True     /* argument for printall and checkall parameters*/


/*-------------------------------------------
-ERR - qhull exit codes, for indicating errors
*/
#define qh_ERRnone  0    /* no error occurred during qhull */
#define qh_ERRinput 1    /* input inconsistency */
#define qh_ERRsingular 2 /* singular input data */
#define qh_ERRprec  3    /* precision error */
#define qh_ERRmem   4    /* insufficient memory, matches mem.h */
#define qh_ERRqhull 5    /* internal error detected, matches mem.h */

/* ============ -structures- ====================
   each of the following structures is defined by a typedef
   all realT and coordT fields occur at the beginning of a structure
        (otherwise space may be wasted due to alignment)
   define all flags together and pack into 32-bit number
*/

typedef struct vertexT vertexT;
typedef struct ridgeT ridgeT;
typedef struct facetT facetT;
#ifndef DEFsetT
#define DEFsetT 1
typedef struct setT setT;          /* defined in set.h */
#endif

/* ----------------------------------------------
-facetT- specifies a facet. 

  qhull() generates the hull as a list of facets.  
*/

struct facetT {
#if !qh_COMPUTEfurthest
  coordT   furthestdist;/* distance to furthest point of outsideset */
#endif
#if qh_MAXoutside
  coordT   maxoutside;  /* max computed distance of point to facet
  			Before QHULLfinished this is an approximation
  			since maxdist not always set for mergefacet
			Actual outer plane is +DISTround and
			computed outer plane is +2*DISTround */
#endif
  coordT   offset;      /* exact offset of hyperplane from origin */ 
  coordT  *normal;      /* normal of hyperplane, hull_dim coefficients */
  union {               /* in order of testing */
   realT   area;        /* area of facet, only in io.c if  ->isarea */
   facetT *replace;	/*  replacement facet if ->visible and NEWfacets
  			     is NULL only if qh_mergedegen_redundant or interior */
   facetT *samecycle;   /*  cycle of facets from the same visible/horizon intersection,
   			     if ->newfacet */
   facetT *newcycle;    /*  in horizon facet, current samecycle of new facets */ 
  }f;
  coordT  *center;      /*  centrum for convexity, qh CENTERtype == qh_AScentrum */
      			/*  Voronoi center, qh CENTERtype == qh_ASvoronoi */
  facetT  *previous;    /* previous facet in the facet_list */
  facetT  *next;        /* next facet in the facet_list */
  setT    *vertices;    /* vertices for this facet, inverse sorted by id 
                           if simplicial, 1st vertex was apex/furthest */
  setT    *ridges;      /* explicit ridges for nonsimplicial facets.
  			   for simplicial facets, neighbors defines ridge */
  setT    *neighbors;   /* neighbors of the facet.  If simplicial, the kth 
			   neighbor is opposite the kth vertex, and the first
			   neighbor is the horizon facet for the first vertex*/
  setT    *outsideset;  /* set of points outside this facet
		           if non-empty, last point is furthest */
  setT    *coplanarset; /* set of points coplanar with this facet
  			   > min_vertex and <= facet->max_outside
                           a point is assigned to the furthest facet
		           if non-empty, last point is furthest away */
  unsigned visitid;     /* visit_id, for visiting all neighbors,
			   all uses are independent */
  unsigned id;	        /* unique identifier from qh facet_id */
  unsigned nummerge:9;  /* number of merges */
#define qh_MAXnummerge 511 /*     2^9-1 */
  flagT	   newfacet:1;  /* True if facet on qh newfacet_list (new or merged) */
  flagT	   visible:1;   /* True if visible facet (will be deleted) */
  flagT    toporient:1; /* True if created with top orientation
			   after merging, use ridge orientation */
  flagT    simplicial:1;/* True if simplicial facet, ->ridges may be implicit */
  flagT    seen:1;      /* used to perform operations only once, like visitid */
  flagT	   flipped:1;   /* True if facet is flipped */
  flagT    upperdelaunay:1; /* True if facet is upper envelope of Delaunay triangulation */
  		/* flags primarily for output */
  flagT	   good:1;      /* True if a facet marked good for output */
  flagT    isarea:1;    /* True if facet->f.area is defined */
		/* flags for merging */
  flagT    dupridge:1;  /* True if duplicate ridge in facet */
  flagT    mergeridge:1; /* True if facet or neighbor contains a qh_MERGEridge
                            ->normal defined (also defined for mergeridge2) */
  flagT    mergeridge2:1; /* True if neighbor contains a qh_MERGEridge (mark_dupridges */
  flagT    coplanar:1;  /* True if horizon facet is coplanar at last use */
  flagT     mergehorizon:1; /* True if will merge into horizon (->coplanar) */
  flagT	    cycledone:1;/* True if mergecycle_all already done */
  flagT    tested:1;    /* True if facet convexity has been tested (false after merge */
  flagT    keepcentrum:1; /* True if keep old centrum after a merge */
  flagT	   newmerge:1;  /* True if facet is newly merged for reducevertices */
  flagT	   degenerate:1; /* True if facet is degenerate (degen_mergeset) */
  flagT	   redundant:1;  /* True if facet is redundant (degen_mergeset) */
};


/*----------------------------------------------
-ridgeT- specifies a ridge

  a ridge is hull_dim-1 simplex between two neighboring facets.  If the
  facets are non-simplicial, there may be more than one ridge between
  two facets.  E.G. a 4-d hypercube has two triangles between each pair
  of neighboring facets.
*/

struct ridgeT {
  setT    *vertices;    /* vertices belonging to this ridge, inverse sorted by id 
                           NULL if a degen ridge (matchsame) */
  facetT  *top;         /* top facet this ridge is part of */
  facetT  *bottom;      /* bottom facet this ridge is part of */
  unsigned id:24;       /* unique identifier, =>room for 8 flags */
  flagT    seen:1;      /* used to perform operations only once */
  flagT    tested:1;    /* True when ridge is tested for convexity */
  flagT    nonconvex:1; /* True if getmergeset detected a non-convex neighbor 
			   only one ridge between neighbors may have nonconvex */
};

/* ----------------------------------------------
-vertexT- specifies a vertex
*/

struct vertexT {
  vertexT *next;        /* next vertex in vertex_list */
  vertexT *previous;    /* previous vertex in vertex_list */
  pointT  *point;       /* hull_dim coordinates (coordT) */
  setT    *neighbors;   /* neighboring facets of vertex, qh_vertexneighbors()
			   inits in io.c or after first merge */
  unsigned visitid;     /* for use with qh vertex_visit */
  unsigned id:24;       /* unique identifier, =>room for 8 flags */
  flagT    seen:1;      /* used to perform operations only once */
  flagT    seen2:1;     /* another seen flag */
  flagT    delridge:1;  /* vertex was part of a deleted ridge */
  flagT	   deleted:1;   /* true if vertex on qh del_vertices */
  flagT    newlist:1;   /* true if vertex on qh newvertex_list */
};

/* ======= -global variables -qh ============================ 

   all global variables for qhull are in qh, qhmem, and qhstat