text: <!-- Do not edit with Front Page, it adds too many spaces -->
  <html>
  <head>
  <meta http-equiv="Content-Type"
  content="text/html; charset=iso-8859-1">
  <title>geom_r.c, geom2_r.c -- geometric and floating point routines</title>
  </head>
  
  <body>
  <!-- Navigation links -->
  <p><a name="TOP"><b>Up:</b></a> <a
  href="http://www.qhull.org">Home page</a> for Qhull (<a href="../index.htm">local</a>)<br>
  <b>Up:</b> <a href="../../html/index.htm#TOC">Qhull manual</a>: contents <br>
  <b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
  &#149; <a href="../../html/qh-quick.htm#options">Options</a>
  &#149; <a href="../../html/qh-opto.htm#output">Output</a>
  &#149; <a href="../../html/qh-optf.htm#format">Formats</a>
  &#149; <a href="../../html/qh-optg.htm#geomview">Geomview</a>
  &#149; <a href="../../html/qh-optp.htm#print">Print</a>
  &#149; <a href="../../html/qh-optq.htm#qhull">Qhull</a>
  &#149; <a href="../../html/qh-optc.htm#prec">Precision</a>
  &#149; <a href="../../html/qh-optt.htm#trace">Trace</a>
  &#149; <a href="http://www.qhull.org/src/libqhull_r/index.htm">Functions</a> (<a href="index.htm">local</a>)<br>
  <b>Up:</b> <a href="../../html/qh-code.htm">Qhull code</a><br>
  <b>To:</b> <a href="qh-geom_r.htm#TOC">Geom</a> &#149; <a href="qh-globa_r.htm">Global</a>
  &#149; <a href="qh-io_r.htm">Io</a> &#149; <a href="qh-mem_r.htm">Mem</a>
  &#149; <a href="qh-merge_r.htm">Merge</a> &#149; <a href="qh-poly_r.htm">Poly</a>
  &#149; <a href="qh-qhull_r.htm">Qhull</a> &#149; <a href="qh-set_r.htm">Set</a>
  &#149; <a href="qh-stat_r.htm">Stat</a> &#149; <a href="qh-user_r.htm">User</a>
  </p>
  
  <hr>
  <!-- Main text of document. -->
  
  <h2>geom_r.c, geom2_r.c, random_r.c -- geometric and floating point routines</h2>
  <blockquote>
  <p>Geometrically, a vertex is a point with <em>d</em> coordinates
  and a facet is a halfspace. A <em>halfspace</em> is defined by an
  oriented hyperplane through the facet's vertices. A <em>hyperplane</em>
  is defined by <em>d</em> normalized coefficients and an offset. A
  point is <em>above</em> a facet if its distance to the facet is
  positive.</p>
  
  <p>Qhull uses floating point coordinates for input points,
  vertices, halfspace equations, centrums, and an interior point.</p>
  
  <p>Qhull may be configured for single precision or double
  precision floating point arithmetic (see <a href="user_r.h#realT">realT</a>
  ). </p>
  
  <p>Each floating point operation may incur round-off error (see
  <a href="qh-merge_r.htm#TOC">Merge</a>). The maximum error for distance
  computations is determined at initialization. The roundoff error
  in halfspace computation is accounted for by computing the
  distance from vertices to the halfspace. </p>
  </blockquote>
  <p><b>Copyright &copy; 1995-2020 C.B. Barber</b></p>
  <hr>
  <p><a href="#TOP">&#187;</a> <b>Geom</b>
  <a name="TOC">&#149;</a> <a href="qh-globa_r.htm#TOC">Global</a> &#149;
  <a href="qh-io_r.htm#TOC">Io</a> &#149; <a href="qh-mem_r.htm#TOC">Mem</a> &#149;
  <a href="qh-merge_r.htm#TOC">Merge</a> &#149; <a href="qh-poly_r.htm#TOC">Poly</a> &#149;
  <a href="qh-qhull_r.htm#TOC">Qhull</a> &#149; <a href="qh-set_r.htm#TOC">Set</a> &#149;
  <a href="qh-stat_r.htm#TOC">Stat</a> &#149; <a href="qh-user_r.htm#TOC">User</a> </p>
  
  <h3>Index to <a href="geom_r.c">geom_r.c</a>,
  <a href="geom2_r.c">geom2_r.c</a>, <a href="geom_r.h">geom_r.h</a>,
  <a href="random_r.c">random_r.c</a>, <a href="random_r.h">random_r.h</a>
  </h3>
  
  <ul>
  <li><a href="#gtype">geometric data types and constants</a> </li>
  <li><a href="#gmacro">mathematical macros</a>
  </li>
  <li><a href="#gmath">mathematical functions</a> </li>
  <li><a href="#gcomp">computational geometry functions</a> </li>
  <li><a href="#gpoint">point array functions</a> </li>
  <li><a href="#gfacet">geometric facet functions</a> </li>
  <li><a href="#ground">geometric roundoff functions</a></li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="gtype">geometric data types
  and constants</a></h3>
  
  <ul>
  <li><a href="libqhull_r.h#coordT">coordT</a> coordinates and
  coefficients are stored as realT</li>
  <li><a href="libqhull_r.h#pointT">pointT</a> a point is an array
  of <tt>DIM3</tt> coordinates </li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="gmacro">mathematical macros</a></h3>
  
  <ul>
  <li><a href="geom_r.h#fabs_">fabs_</a> returns the absolute
  value of a </li>
  <li><a href="geom_r.h#fmax_">fmax_</a> returns the maximum
  value of a and b </li>
  <li><a href="geom_r.h#fmin_">fmin_</a> returns the minimum
  value of a and b </li>
  <li><a href="geom_r.h#maximize_">maximize_</a> maximize a value
  </li>
  <li><a href="geom_r.h#minimize_">minimize_</a> minimize a value
  </li>
  <li><a href="geom_r.h#det2_">det2_</a> compute a 2-d
  determinate </li>
  <li><a href="geom_r.h#det3_">det3_</a> compute a 3-d
  determinate </li>
  <li><a href="geom_r.h#dX">dX, dY, dZ</a> compute the difference
  between two coordinates </li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="gmath">mathematical functions</a></h3>
  
  <ul>
  <li><a href="geom_r.c#backnormal">qh_backnormal</a> solve for
  normal using back substitution </li>
  <li><a href="geom2_r.c#crossproduct">qh_crossproduct</a>
  compute the cross product of two 3-d vectors </li>
  <li><a href="geom2_r.c#determinant">qh_determinant</a> compute
  the determinant of a square matrix </li>
  <li><a href="geom_r.c#gausselim">qh_gausselim</a> Gaussian
  elimination with partial pivoting </li>
  <li><a href="geom2_r.c#gram_schmidt">qh_gram_schmidt</a>
  implements Gram-Schmidt orthogonalization by rows </li>
  <li><a href="geom2_r.c#maxabsval">qh_maxabsval</a> return max
  absolute value of a vector </li>
  <li><a href="geom2_r.c#minabsval">qh_minabsval</a> return min
  absolute value of a dim vector </li>
  <li><a href="geom2_r.c#mindiff">qh_mindiff</a> return index of
  min absolute difference of two vectors </li>
  <li><a href="geom_r.c#normalize">qh_normalize</a> normalize a
  vector </li>
  <li><a href="geom_r.c#normalize2">qh_normalize2</a> normalize a
  vector and report if too small </li>
  <li><a href="geom2_r.c#printmatrix">qh_printmatrix</a> print
  matrix given by row vectors </li>
  <li><a href="random_r.c#rand">qh_rand/srand</a> generate random
  numbers </li>
  <li><a href="random_r.c#randomfactor">qh_randomfactor</a> return
  a random factor near 1.0 </li>
  <li><a href="random_r.c#randommatrix">qh_randommatrix</a>
  generate a random dimXdim matrix in range (-1,1) </li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="gcomp">computational geometry functions</a></h3>
  
  <ul>
  <li><a href="geom2_r.c#detsimplex">qh_detsimplex</a> compute
  determinate of a simplex of points </li>
  <li><a href="io_r.c#detvnorm">qh_detvnorm</a> determine normal for Voronoi ridge </li>
  <li><a href="geom2_r.c#distnorm">qh_distnorm</a> compute
  distance from point to hyperplane as defined by normal and offset</li>
  <li><a href="geom2_r.c#facetarea_simplex">qh_facetarea_simplex</a>
  return area of a simplex</li>
  <li><a href="geom_r.c#getangle">qh_getangle</a> return cosine
  of angle (i.e., dot product) </li>
  <li><a href="geom_r.c#getcenter">qh_getcenter</a> return
  arithmetic center for a set of vertices </li>
  <li><a href="geom2_r.c#pointdist">qh_pointdist</a> return
  distance between two points </li>
  <li><a href="geom2_r.c#rotatepoints">qh_rotatepoints</a> rotate
  numpoints points by a row matrix </li>
  <li><a href="geom2_r.c#sethalfspace">qh_sethalfspace</a> set
  coords to dual of halfspace relative to an interior point </li>
  <li><a href="geom_r.c#sethyperplane_det">qh_sethyperplane_det</a>
  return hyperplane for oriented simplex using determinates
  </li>
  <li><a href="geom_r.c#sethyperplane_gauss">qh_sethyperplane_gauss</a>
  return hyperplane for oriented simplex using Gaussian
  elimination </li>
  <li><a href="geom2_r.c#voronoi_center">qh_voronoi_center</a>
  return Voronoi center for a set of points </li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="gpoint">point array functions</a></h3>
  <ul>
  <li><a href="geom2_r.c#copypoints">qh_copypoints</a> return
  malloc'd copy of points</li>
  <li><a href="geom2_r.c#joggleinput">qh_joggleinput</a> joggle
  input points by qh.JOGGLEmax </li>
  <li><a href="geom2_r.c#maxmin">qh_maxmin</a> return max/min
  points for each dimension</li>
  <li><a href="geom2_r.c#maxsimplex">qh_maxsimplex</a> determines
  maximum simplex for a set of points </li>
  <li><a href="geom2_r.c#printpoints">qh_printpoints</a> print ids for a
  set of points </li>
  <li><a href="geom2_r.c#projectinput">qh_projectinput</a> project
  input using qh DELAUNAY and qh low_bound/high_bound </li>
  <li><a href="geom2_r.c#projectpoints">qh_projectpoints</a>
  project points along one or more dimensions </li>
  <li><a href="geom2_r.c#rotateinput">qh_rotateinput</a> rotate
  input points using row matrix </li>
  <li><a href="geom2_r.c#scaleinput">qh_scaleinput</a> scale
  input points using qh low_bound/high_bound </li>
  <li><a href="geom2_r.c#scalelast">qh_scalelast</a> scale last
  coordinate to [0,m] for Delaunay triangulations </li>
  <li><a href="geom2_r.c#scalepoints">qh_scalepoints</a> scale
  points to new lowbound and highbound </li>
  <li><a href="geom2_r.c#setdelaunay">qh_setdelaunay</a> project
  points to paraboloid for Delaunay triangulation </li>
  <li><a href="geom2_r.c#sethalfspace_all">qh_sethalfspace_all</a>
  generate dual for halfspace intersection with interior
  point </li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="gfacet">geometric facet functions</a></h3>
  <ul>
  <li><a href="geom_r.c#distplane">qh_distplane</a> return
  distance from point to facet </li>
  <li><a href="geom2_r.c#facetarea">qh_facetarea</a> return area
  of a facet </li>
  <li><a href="geom2_r.c#facetcenter">qh_facetcenter</a> return
  Voronoi center for a facet's vertices </li>
  <li><a href="geom_r.c#findbest">qh_findbest</a> find visible
  facet or best facet for a point </li>
  <li><a href="geom_r.c#findbesthorizon">qh_findbesthorizon</a>
  update best new facet with horizon facets</li>
  <li><a href="geom_r.c#findbestnew">qh_findbestnew</a> find best
  new facet for point </li>
  <li><a href="geom2_r.c#furthestnewvertex">qh_furthestnewvertex</a> return
  furthest new vertex for facet </li>
  <li><a href="geom2_r.c#furthestvertex">qh_furthestvertex</a> return
  furthest vertex in facetA above facetB </li>
  <li><a href="geom2_r.c#getarea">qh_getarea</a> get area and volume of all
  facets in facetlist, collect statistics </li>
  <li><a href="geom_r.c#getcentrum">qh_getcentrum</a> return
  centrum for a facet </li>
  <li><a href="geom_r.c#getdistance">qh_getdistance</a> returns
  the max and min distance of a facet's vertices to a
  neighboring facet</li>
  <li><a href="geom2_r.c#findgooddist">qh_findgooddist</a> find
  best good facet visible for point from facet </li>
  <li><a href="geom2_r.c#inthresholds">qh_inthresholds</a> return
  True if facet normal within 'Pdn' and 'PDn'</li>
  <li><a href="geom2_r.c#orientoutside">qh_orientoutside</a>
  orient facet so that <tt>qh.interior_point</tt> is inside</li>
  <li><a href="geom_r.c#projectpoint">qh_projectpoint</a> project
  point onto a facet </li>
  <li><a href="geom_r.c#setfacetplane">qh_setfacetplane</a> sets
  the hyperplane for a facet </li>
  <li><a href="geom2_r.c#sharpnewfacets">qh_sharpnewfacets</a> true
  if new facets contains a sharp corner</li>
  <li><a href="geom2_r.c#vertex_bestdist">qh_vertex_bestdist</a>
  return nearest distance between vertices, except 'skip' </li>
  <li><a href="geom2_r.c#vertex_isbelow">qh_vertex_isbelow</a> true if
  vertexA is below vertexB's simplicial facets, or least above </li>
  </ul>
  
  <h3><a href="qh-geom_r.htm#TOC">&#187;</a><a name="ground">geometric roundoff functions</a></h3>
  <ul>
  <li><a href="geom2_r.c#detjoggle">qh_detjoggle</a> determine
  default joggle for points and distance roundoff error </li>
  <li><a href="geom2_r.c#detmaxoutside">qh_detmaxoutside</a>
  determine qh.MAXoutside target for qh_RATIO... tests </li>
  <li><a href="geom2_r.c#detroundoff">qh_detroundoff</a>
  determine maximum roundoff error and other precision constants </li>
  <li><a href="geom2_r.c#distround">qh_distround</a> compute
  maximum roundoff error due to a distance computation to a
  normalized hyperplane </li>
  <li><a href="geom2_r.c#divzero">qh_divzero</a> divide by a
  number that is nearly zero </li>
  <li><a href="geom2_r.c#maxouter">qh_maxouter</a> return maximum outer
  plane</li>
  <li><a href="geom2_r.c#outerinner">qh_outerinner</a> return actual
  outer and inner planes</li>
  </ul>
  
  <p><!-- Navigation links --> </p>
  <hr>
  <p><b>Up:</b>
  <a href="http://www.qhull.org">Home page</a> for
  Qhull (<a href="../index.htm">local</a>) <br>
  <b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: contents<br>
  <b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
  &#149; <a href="../../html/qh-quick.htm#options">Options</a>
  &#149; <a href="../../html/qh-opto.htm#output">Output</a>
  &#149; <a href="../../html/qh-optf.htm#format">Formats</a>
  &#149; <a href="../../html/qh-optg.htm#geomview">Geomview</a>
  &#149; <a href="../../html/qh-optp.htm#print">Print</a>
  &#149; <a href="../../html/qh-optq.htm#qhull">Qhull</a>
  &#149; <a href="../../html/qh-optc.htm#prec">Precision</a>
  &#149; <a href="../../html/qh-optt.htm#trace">Trace</a>
  &#149; <a href="http://www.qhull.org/src/libqhull_r/index.htm">Functions</a> (<a href="index.htm">local</a>)<br>
  <b>Up:</b> <a href="../../html/qh-code.htm">Qhull code</a> <br>
  <b>To:</b> <a href="qh-geom_r.htm">Geom</a> &#149;
  <a href="qh-globa_r.htm">Global</a> &#149; <a href="qh-io_r.htm">Io</a>
  &#149; <a href="qh-mem_r.htm">Mem</a> &#149; <a href="qh-merge_r.htm">Merge</a>
  &#149; <a href="qh-poly_r.htm">Poly</a> &#149; <a href="qh-qhull_r.htm#TOC">Qhull</a>
  &#149; <a href="qh-set_r.htm">Set</a> &#149; <a href="qh-stat_r.htm">Stat</a>
  &#149; <a href="qh-user_r.htm">User</a><br>
  
  
  <p><!-- GC common information --> </p>
  <hr>
  <p><a href="http://www.geom.uiuc.edu/"><img
  src="../../html/qh--geom.gif" align="middle" width="40" height="40"></a><i>The
  Geometry Center Home Page </i></p>
  <p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
  <br>
  Created: May 2, 1997 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
  </body>
  </html>
  