afl: geom.h Source File

00001 /*<html><pre>  -<a                             href="qh-geom.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004   geom.h 
00005     header file for geometric routines
00006 
00007    see qh-geom.htm and geom.c
00008 
00009    copyright (c) 1993-2003 The Geometry Center        
00010 */
00011 
00012 #ifndef qhDEFgeom
00013 #define qhDEFgeom 1
00014 
00015 /* ============ -macros- ======================== */
00016 
00017 /*-<a                             href="qh-geom.htm#TOC"
00018   >--------------------------------</a><a name="fabs_">-</a>
00019    
00020   fabs_(a)
00021     returns the absolute value of a
00022 */
00023 #define fabs_( a ) ((( a ) < 0 ) ? -( a ):( a ))
00024                
00025 /*-<a                             href="qh-geom.htm#TOC"
00026   >--------------------------------</a><a name="fmax_">-</a>
00027   
00028   fmax_(a,b)
00029     returns the maximum value of a and b
00030 */
00031 #define fmax_( a,b )  ( ( a ) < ( b ) ? ( b ) : ( a ) )
00032 
00033 /*-<a                             href="qh-geom.htm#TOC"
00034   >--------------------------------</a><a name="fmin_">-</a>
00035 
00036   fmin_(a,b)
00037     returns the minimum value of a and b
00038 */
00039 #define fmin_( a,b )  ( ( a ) > ( b ) ? ( b ) : ( a ) )
00040 
00041 /*-<a                             href="qh-geom.htm#TOC"
00042   >--------------------------------</a><a name="maximize_">-</a>
00043 
00044   maximize_(maxval, val)
00045     set maxval to val if val is greater than maxval
00046 */
00047 #define maximize_( maxval, val ) {if (( maxval ) < ( val )) ( maxval )= ( val );}
00048 
00049 /*-<a                             href="qh-geom.htm#TOC"
00050   >--------------------------------</a><a name="minimize_">-</a>
00051 
00052   minimize_(minval, val)
00053     set minval to val if val is less than minval
00054 */
00055 #define minimize_( minval, val ) {if (( minval ) > ( val )) ( minval )= ( val );}
00056 
00057 /*-<a                             href="qh-geom.htm#TOC"
00058   >--------------------------------</a><a name="det2_">-</a>
00059 
00060   det2_(a1, a2,     
00061         b1, b2)
00062   
00063     compute a 2-d determinate
00064 */
00065 #define det2_( a1,a2,b1,b2 ) (( a1 )*( b2 ) - ( a2 )*( b1 ))
00066 
00067 /*-<a                             href="qh-geom.htm#TOC"
00068   >--------------------------------</a><a name="det3_">-</a>
00069   
00070   det3_(a1, a2, a3,    
00071        b1, b2, b3,
00072        c1, c2, c3)
00073   
00074     compute a 3-d determinate
00075 */
00076 #define det3_( a1,a2,a3,b1,b2,b3,c1,c2,c3 ) ( ( a1 )*det2_( b2,b3,c2,c3 ) \
00077                 - ( b1 )*det2_( a2,a3,c2,c3 ) + ( c1 )*det2_( a2,a3,b2,b3 ) )
00078 
00079 /*-<a                             href="qh-geom.htm#TOC"
00080   >--------------------------------</a><a name="dX">-</a>
00081   
00082   dX( p1, p2 )
00083   dY( p1, p2 )
00084   dZ( p1, p2 )
00085   
00086     given two indices into rows[],
00087 
00088     compute the difference between X, Y, or Z coordinates
00089 */
00090 #define dX( p1,p2 )  ( *( rows[p1] ) - *( rows[p2] ))
00091 #define dY( p1,p2 )  ( *( rows[p1]+1 ) - *( rows[p2]+1 ))
00092 #define dZ( p1,p2 )  ( *( rows[p1]+2 ) - *( rows[p2]+2 ))
00093 #define dW( p1,p2 )  ( *( rows[p1]+3 ) - *( rows[p2]+3 ))
00094 
00095 /*============= prototypes in alphabetical order, infrequent at end ======= */
00096 
00097 void    qh_backnormal (realT **rows, int numrow, int numcol, boolT sign, coordT *normal, boolT *nearzero);
00098 void    qh_distplane (pointT *point, facetT *facet, realT *dist);
00099 facetT *qh_findbest (pointT *point, facetT *startfacet,
00100              boolT bestoutside, boolT isnewfacets, boolT noupper,
00101              realT *dist, boolT *isoutside, int *numpart);
00102 facetT *qh_findbesthorizon (boolT ischeckmax, pointT *point, 
00103                  facetT *startfacet, boolT noupper, realT *bestdist, int *numpart);
00104 facetT *qh_findbestnew (pointT *point, facetT *startfacet, realT *dist, 
00105              boolT bestoutside, boolT *isoutside, int *numpart);
00106 void    qh_gausselim(realT **rows, int numrow, int numcol, boolT *sign, boolT *nearzero);
00107 realT   qh_getangle(pointT *vect1, pointT *vect2);
00108 pointT *qh_getcenter(setT *vertices);
00109 pointT *qh_getcentrum(facetT *facet);
00110 realT   qh_getdistance(facetT *facet, facetT *neighbor, realT *mindist, realT *maxdist);
00111 void    qh_normalize (coordT *normal, int dim, boolT toporient);
00112 void    qh_normalize2 (coordT *normal, int dim, boolT toporient, 
00113             realT *minnorm, boolT *ismin);
00114 pointT *qh_projectpoint(pointT *point, facetT *facet, realT dist);
00115 
00116 void    qh_setfacetplane(facetT *newfacets);
00117 void    qh_sethyperplane_det (int dim, coordT **rows, coordT *point0, 
00118               boolT toporient, coordT *normal, realT *offset, boolT *nearzero);
00119 void    qh_sethyperplane_gauss (int dim, coordT **rows, pointT *point0, 
00120          boolT toporient, coordT *normal, coordT *offset, boolT *nearzero);
00121 boolT   qh_sharpnewfacets (void);
00122 
00123 /*========= infrequently used code in geom2.c =============*/
00124 
00125 
00126 coordT *qh_copypoints (coordT *points, int numpoints, int dimension);
00127 void    qh_crossproduct (int dim, realT vecA[3], realT vecB[3], realT vecC[3]);
00128 realT   qh_determinant (realT **rows, int dim, boolT *nearzero);
00129 realT   qh_detjoggle (pointT *points, int numpoints, int dimension);
00130 void    qh_detroundoff (void);
00131 realT   qh_detsimplex(pointT *apex, setT *points, int dim, boolT *nearzero);
00132 realT   qh_distnorm (int dim, pointT *point, pointT *normal, realT *offsetp);
00133 realT   qh_distround (int dimension, realT maxabs, realT maxsumabs);
00134 realT   qh_divzero(realT numer, realT denom, realT mindenom1, boolT *zerodiv);
00135 realT   qh_facetarea (facetT *facet);
00136 realT   qh_facetarea_simplex (int dim, coordT *apex, setT *vertices, 
00137           vertexT *notvertex,  boolT toporient, coordT *normal, realT *offset);
00138 pointT *qh_facetcenter (setT *vertices);
00139 facetT *qh_findgooddist (pointT *point, facetT *facetA, realT *distp, facetT **facetlist);
00140 void    qh_getarea (facetT *facetlist);
00141 boolT   qh_gram_schmidt(int dim, realT **rows);
00142 boolT   qh_inthresholds (coordT *normal, realT *angle);
00143 void    qh_joggleinput (void);
00144 realT  *qh_maxabsval (realT *normal, int dim);
00145 setT   *qh_maxmin(pointT *points, int numpoints, int dimension);
00146 realT   qh_maxouter (void);
00147 void    qh_maxsimplex (int dim, setT *maxpoints, pointT *points, int numpoints, setT **simplex);
00148 realT   qh_minabsval (realT *normal, int dim);
00149 int     qh_mindiff (realT *vecA, realT *vecB, int dim);
00150 boolT   qh_orientoutside (facetT *facet);
00151 void    qh_outerinner (facetT *facet, realT *outerplane, realT *innerplane);
00152 coordT  qh_pointdist(pointT *point1, pointT *point2, int dim);
00153 void    qh_printmatrix (FILE *fp, char *string, realT **rows, int numrow, int numcol);
00154 void    qh_printpoints (FILE *fp, char *string, setT *points);
00155 void    qh_projectinput (void);
00156 void    qh_projectpoints (signed char *project, int n, realT *points, 
00157              int numpoints, int dim, realT *newpoints, int newdim);
00158 int     qh_rand( void);
00159 void    qh_srand( int seed);
00160 realT   qh_randomfactor (void);
00161 void    qh_randommatrix (realT *buffer, int dim, realT **row);
00162 void    qh_rotateinput (realT **rows);
00163 void    qh_rotatepoints (realT *points, int numpoints, int dim, realT **rows);
00164 void    qh_scaleinput (void);
00165 void    qh_scalelast (coordT *points, int numpoints, int dim, coordT low,
00166            coordT high, coordT newhigh);
00167 void    qh_scalepoints (pointT *points, int numpoints, int dim,
00168         realT *newlows, realT *newhighs);
00169 boolT   qh_sethalfspace (int dim, coordT *coords, coordT **nextp, 
00170               coordT *normal, coordT *offset, coordT *feasible);
00171 coordT *qh_sethalfspace_all (int dim, int count, coordT *halfspaces, pointT *feasible);
00172 pointT *qh_voronoi_center (int dim, setT *points);
00173 
00174 #endif /* qhDEFgeom */
00175 
00176 
00177