geom.c, geom2.c -- geometric and floating point routines

Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace
Up: Qhull internals: Table of Contents
To: Qhull functions, macros, and data structures
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

geom.c, geom2.c -- geometric and floating point routines

Geometrically, a vertex is a point with d coordinates and a facet is a halfspace. A halfspace is defined by an oriented hyperplane through the facet's vertices. A hyperplane is defined by d normalized coefficients and an offset. A point is above a facet if its distance to the facet is positive.

Qhull uses floating point coordinates for input points, vertices, halfspace equations, centrums, and an interior point.

Qhull may be configured for single precision or double precision floating point arithmetic (see realT ).

Each floating point operation may incur round-off error (see Merge). 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.

» Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

»geometric data types and constants

coordT coordinates and coefficients are stored as realT
pointT a point is an array of DIM3 coordinates

»mathematical macros

fabs_ returns the absolute value of a
fmax_ returns the maximum value of a and b
fmin_ returns the minimum value of a and b
maximize_ maximize a value
minimize_ minimize a value
det2_ compute a 2-d determinate
det3_ compute a 3-d determinate
dX, dY, dZ compute the difference between two coordinates

»mathematical functions

qh_backnormal solve for normal using back substitution
qh_crossproduct compute the cross product of two 3-d vectors
qh_determinant compute the determinant of a square matrix
qh_gausselim Gaussian elimination with partial pivoting
qh_gram_schmidt implements Gram-Schmidt orthogonalization by rows
qh_maxabsval return max absolute value of a vector
qh_minabsval return min absolute value of a dim vector
qh_mindiff return index of min absolute difference of two vectors
qh_normalize normalize a vector
qh_normalize2 normalize a vector and report if too small
qh_printmatrix print matrix given by row vectors
qh_rand/srand generate random numbers
qh_randomfactor return a random factor near 1.0
qh_randommatrix generate a random dimXdim matrix in range (-1,1)

»computational geometry functions

qh_detsimplex compute determinate of a simplex of points
qh_detvnorm determine normal for Voronoi ridge
qh_distnorm compute distance from point to hyperplane as defined by normal and offset
qh_facetarea_simplex return area of a simplex
qh_getangle return cosine of angle (i.e., dot product)
qh_getcenter return arithmetic center for a set of vertices
qh_pointdist return distance between two points
qh_rotatepoints rotate numpoints points by a row matrix
qh_sethalfspace set coords to dual of halfspace relative to an interior point
qh_sethyperplane_det return hyperplane for oriented simplex using determinates
qh_sethyperplane_gauss return hyperplane for oriented simplex using Gaussian elimination
qh_voronoi_center return Voronoi center for a set of points

»point array functions

qh_copypoints return malloc'd copy of points
qh_joggleinput joggle input points by qh.JOGGLEmax
qh_maxmin return max/min points for each dimension
qh_maxsimplex determines maximum simplex for a set of points
qh_printpoints print ids for a set of points
qh_projectinput project input using qh DELAUNAY and qh low_bound/high_bound
qh_projectpoints project points along one or more dimensions
qh_rotateinput rotate input points using row matrix
qh_scaleinput scale input points using qh low_bound/high_bound
qh_scalelast scale last coordinate to [0,m] for Delaunay triangulations
qh_scalepoints scale points to new lowbound and highbound
qh_setdelaunay project points to paraboloid for Delaunay triangulation
qh_sethalfspace_all generate dual for halfspace intersection with interior point

»geometric facet functions

qh_distplane return distance from point to facet
qh_facetarea return area of a facet
qh_facetcenter return Voronoi center for a facet's vertices
qh_findbest find visible facet or best facet for a point
qh_findbesthorizon update best new facet with horizon facets
qh_findbestnew find best new facet for point
qh_getarea get area of all facets in facetlist, collect statistics
qh_getcentrum return centrum for a facet
qh_getdistance returns the max and min distance of a facet's vertices to a neighboring facet
qh_findgooddist find best good facet visible for point from facet
qh_inthresholds return True if facet normal within 'Pdn' and 'PDn'
qh_orientoutside orient facet so that qh.interior_point is inside
qh_projectpoint project point onto a facet
qh_setfacetplane sets the hyperplane for a facet
qh_sharpnewfacets true if new facets contains a sharp corner

»geometric roundoff functions

qh_detjoggle determine default joggle for points and distance roundoff error
qh_detroundoff determine maximum roundoff error and other precision constants
qh_distround compute maximum roundoff error due to a distance computation to a normalized hyperplane
qh_divzero divide by a number that is nearly zero
qh_maxouter return maximum outer plane
qh_outerinner return actual outer and inner planes

The Geometry Center Home Page

Comments to: qhull@qhull.org
Created: May 2, 1997 --- Last modified: see top