| 1 |
chuckv |
1138 |
/*<html><pre> -<a href="qh-geom.htm" |
| 2 |
|
|
>-------------------------------</a><a name="TOP">-</a> |
| 3 |
|
|
|
| 4 |
|
|
geom.h |
| 5 |
|
|
header file for geometric routines |
| 6 |
|
|
|
| 7 |
|
|
see qh-geom.htm and geom.c |
| 8 |
|
|
|
| 9 |
|
|
copyright (c) 1993-2003 The Geometry Center |
| 10 |
|
|
*/ |
| 11 |
|
|
|
| 12 |
|
|
#ifndef qhDEFgeom |
| 13 |
|
|
#define qhDEFgeom 1 |
| 14 |
|
|
|
| 15 |
|
|
/* ============ -macros- ======================== */ |
| 16 |
|
|
|
| 17 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 18 |
|
|
>--------------------------------</a><a name="fabs_">-</a> |
| 19 |
|
|
|
| 20 |
|
|
fabs_(a) |
| 21 |
|
|
returns the absolute value of a |
| 22 |
|
|
*/ |
| 23 |
|
|
#define fabs_( a ) ((( a ) < 0 ) ? -( a ):( a )) |
| 24 |
|
|
|
| 25 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 26 |
|
|
>--------------------------------</a><a name="fmax_">-</a> |
| 27 |
|
|
|
| 28 |
|
|
fmax_(a,b) |
| 29 |
|
|
returns the maximum value of a and b |
| 30 |
|
|
*/ |
| 31 |
|
|
#define fmax_( a,b ) ( ( a ) < ( b ) ? ( b ) : ( a ) ) |
| 32 |
|
|
|
| 33 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 34 |
|
|
>--------------------------------</a><a name="fmin_">-</a> |
| 35 |
|
|
|
| 36 |
|
|
fmin_(a,b) |
| 37 |
|
|
returns the minimum value of a and b |
| 38 |
|
|
*/ |
| 39 |
|
|
#define fmin_( a,b ) ( ( a ) > ( b ) ? ( b ) : ( a ) ) |
| 40 |
|
|
|
| 41 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 42 |
|
|
>--------------------------------</a><a name="maximize_">-</a> |
| 43 |
|
|
|
| 44 |
|
|
maximize_(maxval, val) |
| 45 |
|
|
set maxval to val if val is greater than maxval |
| 46 |
|
|
*/ |
| 47 |
|
|
#define maximize_( maxval, val ) {if (( maxval ) < ( val )) ( maxval )= ( val );} |
| 48 |
|
|
|
| 49 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 50 |
|
|
>--------------------------------</a><a name="minimize_">-</a> |
| 51 |
|
|
|
| 52 |
|
|
minimize_(minval, val) |
| 53 |
|
|
set minval to val if val is less than minval |
| 54 |
|
|
*/ |
| 55 |
|
|
#define minimize_( minval, val ) {if (( minval ) > ( val )) ( minval )= ( val );} |
| 56 |
|
|
|
| 57 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 58 |
|
|
>--------------------------------</a><a name="det2_">-</a> |
| 59 |
|
|
|
| 60 |
|
|
det2_(a1, a2, |
| 61 |
|
|
b1, b2) |
| 62 |
|
|
|
| 63 |
|
|
compute a 2-d determinate |
| 64 |
|
|
*/ |
| 65 |
|
|
#define det2_( a1,a2,b1,b2 ) (( a1 )*( b2 ) - ( a2 )*( b1 )) |
| 66 |
|
|
|
| 67 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 68 |
|
|
>--------------------------------</a><a name="det3_">-</a> |
| 69 |
|
|
|
| 70 |
|
|
det3_(a1, a2, a3, |
| 71 |
|
|
b1, b2, b3, |
| 72 |
|
|
c1, c2, c3) |
| 73 |
|
|
|
| 74 |
|
|
compute a 3-d determinate |
| 75 |
|
|
*/ |
| 76 |
|
|
#define det3_( a1,a2,a3,b1,b2,b3,c1,c2,c3 ) ( ( a1 )*det2_( b2,b3,c2,c3 ) \ |
| 77 |
|
|
- ( b1 )*det2_( a2,a3,c2,c3 ) + ( c1 )*det2_( a2,a3,b2,b3 ) ) |
| 78 |
|
|
|
| 79 |
|
|
/*-<a href="qh-geom.htm#TOC" |
| 80 |
|
|
>--------------------------------</a><a name="dX">-</a> |
| 81 |
|
|
|
| 82 |
|
|
dX( p1, p2 ) |
| 83 |
|
|
dY( p1, p2 ) |
| 84 |
|
|
dZ( p1, p2 ) |
| 85 |
|
|
|
| 86 |
|
|
given two indices into rows[], |
| 87 |
|
|
|
| 88 |
|
|
compute the difference between X, Y, or Z coordinates |
| 89 |
|
|
*/ |
| 90 |
|
|
#define dX( p1,p2 ) ( *( rows[p1] ) - *( rows[p2] )) |
| 91 |
|
|
#define dY( p1,p2 ) ( *( rows[p1]+1 ) - *( rows[p2]+1 )) |
| 92 |
|
|
#define dZ( p1,p2 ) ( *( rows[p1]+2 ) - *( rows[p2]+2 )) |
| 93 |
|
|
#define dW( p1,p2 ) ( *( rows[p1]+3 ) - *( rows[p2]+3 )) |
| 94 |
|
|
|
| 95 |
|
|
/*============= prototypes in alphabetical order, infrequent at end ======= */ |
| 96 |
|
|
|
| 97 |
|
|
void qh_backnormal (realT **rows, int numrow, int numcol, boolT sign, coordT *normal, boolT *nearzero); |
| 98 |
|
|
void qh_distplane (pointT *point, facetT *facet, realT *dist); |
| 99 |
|
|
facetT *qh_findbest (pointT *point, facetT *startfacet, |
| 100 |
|
|
boolT bestoutside, boolT isnewfacets, boolT noupper, |
| 101 |
|
|
realT *dist, boolT *isoutside, int *numpart); |
| 102 |
|
|
facetT *qh_findbesthorizon (boolT ischeckmax, pointT *point, |
| 103 |
|
|
facetT *startfacet, boolT noupper, realT *bestdist, int *numpart); |
| 104 |
|
|
facetT *qh_findbestnew (pointT *point, facetT *startfacet, realT *dist, |
| 105 |
|
|
boolT bestoutside, boolT *isoutside, int *numpart); |
| 106 |
|
|
void qh_gausselim(realT **rows, int numrow, int numcol, boolT *sign, boolT *nearzero); |
| 107 |
|
|
realT qh_getangle(pointT *vect1, pointT *vect2); |
| 108 |
|
|
pointT *qh_getcenter(setT *vertices); |
| 109 |
|
|
pointT *qh_getcentrum(facetT *facet); |
| 110 |
|
|
realT qh_getdistance(facetT *facet, facetT *neighbor, realT *mindist, realT *maxdist); |
| 111 |
|
|
void qh_normalize (coordT *normal, int dim, boolT toporient); |
| 112 |
|
|
void qh_normalize2 (coordT *normal, int dim, boolT toporient, |
| 113 |
|
|
realT *minnorm, boolT *ismin); |
| 114 |
|
|
pointT *qh_projectpoint(pointT *point, facetT *facet, realT dist); |
| 115 |
|
|
|
| 116 |
|
|
void qh_setfacetplane(facetT *newfacets); |
| 117 |
|
|
void qh_sethyperplane_det (int dim, coordT **rows, coordT *point0, |
| 118 |
|
|
boolT toporient, coordT *normal, realT *offset, boolT *nearzero); |
| 119 |
|
|
void qh_sethyperplane_gauss (int dim, coordT **rows, pointT *point0, |
| 120 |
|
|
boolT toporient, coordT *normal, coordT *offset, boolT *nearzero); |
| 121 |
|
|
boolT qh_sharpnewfacets (void); |
| 122 |
|
|
|
| 123 |
|
|
/*========= infrequently used code in geom2.c =============*/ |
| 124 |
|
|
|
| 125 |
|
|
|
| 126 |
|
|
coordT *qh_copypoints (coordT *points, int numpoints, int dimension); |
| 127 |
|
|
void qh_crossproduct (int dim, realT vecA[3], realT vecB[3], realT vecC[3]); |
| 128 |
|
|
realT qh_determinant (realT **rows, int dim, boolT *nearzero); |
| 129 |
|
|
realT qh_detjoggle (pointT *points, int numpoints, int dimension); |
| 130 |
|
|
void qh_detroundoff (void); |
| 131 |
|
|
realT qh_detsimplex(pointT *apex, setT *points, int dim, boolT *nearzero); |
| 132 |
|
|
realT qh_distnorm (int dim, pointT *point, pointT *normal, realT *offsetp); |
| 133 |
|
|
realT qh_distround (int dimension, realT maxabs, realT maxsumabs); |
| 134 |
|
|
realT qh_divzero(realT numer, realT denom, realT mindenom1, boolT *zerodiv); |
| 135 |
|
|
realT qh_facetarea (facetT *facet); |
| 136 |
|
|
realT qh_facetarea_simplex (int dim, coordT *apex, setT *vertices, |
| 137 |
|
|
vertexT *notvertex, boolT toporient, coordT *normal, realT *offset); |
| 138 |
|
|
pointT *qh_facetcenter (setT *vertices); |
| 139 |
|
|
facetT *qh_findgooddist (pointT *point, facetT *facetA, realT *distp, facetT **facetlist); |
| 140 |
|
|
void qh_getarea (facetT *facetlist); |
| 141 |
|
|
boolT qh_gram_schmidt(int dim, realT **rows); |
| 142 |
|
|
boolT qh_inthresholds (coordT *normal, realT *angle); |
| 143 |
|
|
void qh_joggleinput (void); |
| 144 |
|
|
realT *qh_maxabsval (realT *normal, int dim); |
| 145 |
|
|
setT *qh_maxmin(pointT *points, int numpoints, int dimension); |
| 146 |
|
|
realT qh_maxouter (void); |
| 147 |
|
|
void qh_maxsimplex (int dim, setT *maxpoints, pointT *points, int numpoints, setT **simplex); |
| 148 |
|
|
realT qh_minabsval (realT *normal, int dim); |
| 149 |
|
|
int qh_mindiff (realT *vecA, realT *vecB, int dim); |
| 150 |
|
|
boolT qh_orientoutside (facetT *facet); |
| 151 |
|
|
void qh_outerinner (facetT *facet, realT *outerplane, realT *innerplane); |
| 152 |
|
|
coordT qh_pointdist(pointT *point1, pointT *point2, int dim); |
| 153 |
|
|
void qh_printmatrix (FILE *fp, char *string, realT **rows, int numrow, int numcol); |
| 154 |
|
|
void qh_printpoints (FILE *fp, char *string, setT *points); |
| 155 |
|
|
void qh_projectinput (void); |
| 156 |
|
|
void qh_projectpoints (signed char *project, int n, realT *points, |
| 157 |
|
|
int numpoints, int dim, realT *newpoints, int newdim); |
| 158 |
|
|
int qh_rand( void); |
| 159 |
|
|
void qh_srand( int seed); |
| 160 |
|
|
realT qh_randomfactor (void); |
| 161 |
|
|
void qh_randommatrix (realT *buffer, int dim, realT **row); |
| 162 |
|
|
void qh_rotateinput (realT **rows); |
| 163 |
|
|
void qh_rotatepoints (realT *points, int numpoints, int dim, realT **rows); |
| 164 |
|
|
void qh_scaleinput (void); |
| 165 |
|
|
void qh_scalelast (coordT *points, int numpoints, int dim, coordT low, |
| 166 |
|
|
coordT high, coordT newhigh); |
| 167 |
|
|
void qh_scalepoints (pointT *points, int numpoints, int dim, |
| 168 |
|
|
realT *newlows, realT *newhighs); |
| 169 |
|
|
boolT qh_sethalfspace (int dim, coordT *coords, coordT **nextp, |
| 170 |
|
|
coordT *normal, coordT *offset, coordT *feasible); |
| 171 |
|
|
coordT *qh_sethalfspace_all (int dim, int count, coordT *halfspaces, pointT *feasible); |
| 172 |
|
|
pointT *qh_voronoi_center (int dim, setT *points); |
| 173 |
|
|
|
| 174 |
|
|
#endif /* qhDEFgeom */ |
| 175 |
|
|
|
| 176 |
|
|
|
| 177 |
|
|
|
