/* 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 */