allegiance/qhull/geom.h

/* geom.h -- header file for geometric routines

   see README and geom.c
   
   copyright (c) 1993, 1997 The Geometry Center        
*/

#ifndef qhDEFgeom
#define qhDEFgeom 1

/* ============ -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
-facetarea_simplex return area for a simplex defined by an apex, base, orient, normal
-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
-mindiff        return index of min abs. difference of two vectors
-normalize      normalize a vector
-normalize2     normalize a vector and report if too small
-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
-rand/srand     generate random numbers
-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
-scalelast      scale last coordinate to [0,m] for Delaunay triangulations
-scalepoints    scale points to new lowbound and highbound
-sethalfspace_all generate dual for halfspace intersection with feasible point
-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)
-facetarea      return area for a facet
-facetcenter    return Voronoi center for a facet's vertices
-findbest	find visible facet for a point starting at a facet
-findbestnew    find best newfacet for point
-findgooddist   find best good facet visible for point from facet
-getarea        get area of all facets in facetlist, collect statistics
-getcenter      return arithmetic center of a set of vertices
-getcentrum     return centrum for a facet
-getdistance    returns the max and min distance of any vertex from neighbor
-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
-sethalfspace   set coords to dual of halfspace relative to feasible point
*/

/*---------- -prototypes in alphabetical order, infrequent at end -----------*/
void    qh_backnormal (realT **rows, int numrow, int numcol, boolT sign, coordT *normal, boolT *nearzero);
void	qh_distplane (pointT *point, facetT *facet, realT *dist);
facetT *qh_findbest (pointT *point, facetT *facet,
		     boolT bestoutside, boolT newfacets, boolT noupper,
		     realT *dist, boolT *isoutside, int *numpart);
facetT *qh_findbestnew (pointT *point, facetT *startfacet,
	   realT *dist, boolT *isoutside, int *numpart);
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);
realT   qh_getdistance(facetT *facet, facetT *neighbor, realT *mindist, realT *maxdist);
void    qh_normalize (coordT *normal, int dim, boolT toporient);
void    qh_normalize2 (coordT *normal, int dim, boolT toporient, 
            realT *minnorm, boolT *ismin);
pointT *qh_projectpoint(pointT *point, facetT *facet, realT dist);

void    qh_setfacetplane(facetT *newfacets);
void 	qh_sethyperplane_det (int dim, coordT **rows, coordT *point0, 
              boolT toporient, coordT *normal, realT *offset, boolT *nearzero);
void 	qh_sethyperplane_gauss (int dim, coordT **rows, pointT *point0, 
	     boolT toporient, coordT *normal, coordT *offset, boolT *nearzero);

  /* ======= infrequently used code in geom2.c =========== */
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 dim, boolT *nearzero);
realT   qh_divzero(realT numer, realT denom, realT mindenom1, boolT *zerodiv);
realT   qh_facetarea (facetT *facet);
realT   qh_facetarea_simplex (int dim, coordT *apex, setT *vertices, 
          vertexT *notvertex,  boolT toporient, coordT *normal, realT *offset);
pointT *qh_facetcenter (setT *vertices);
boolT   qh_findbestsharp (pointT *point, facetT **bestfacet, 
           realT *bestdist, int *numpart);
facetT *qh_findgooddist (pointT *point, facetT *facetA, realT *distp, facetT **facetlist);
void    qh_getarea (facetT *facetlist);
boolT   qh_gram_schmidt(int dim, realT **rows);
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);
int     qh_mindiff (realT *vecA, realT *vecB, int dim);
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);
void 	qh_projectpoints (signed char *project, int n, realT *points, 
             int numpoints, int dim, realT *newpoints, int newdim);
int     qh_rand( void);
void    qh_srand( int seed);
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_scalelast (coordT *points, int numpoints, int dim, coordT low,
		   coordT high, coordT newhigh);
void 	qh_scalepoints (pointT *points, int numpoints, int dim,
  		realT *newlows, realT *newhighs);
boolT   qh_sethalfspace (int dim, coordT *coords, coordT **nextp, 
              coordT *normal, coordT *offset, coordT *feasible);
coordT *qh_sethalfspace_all (int dim, int count, coordT *halfspaces, pointT *feasible);
pointT *qh_voronoi_center (int dim, setT *points);

#endif /* qhDEFgeom */