qhull.c -- top-level functions and basic data types

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

qhull.c -- top-level functions and basic data types

Qhull implements the Quickhull algorithm for computing the convex hull. The Quickhull algorithm combines two well-known algorithms: the 2-d quickhull algorithm and the n-d beneath-beyond algorithm. See Description of Qhull.

This section provides an index to the top-level functions and base data types. The top-level header file, qhull.h, contains prototypes for these functions.

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

Index to qhull.c, qhull.h, and unix.c

qhull.h and unix.c data types and constants
qhull.h other macros
Quickhull routines in call order
Top-level routines for initializing and terminating Qhull
Top-level routines for reading and modifying the input
Top-level routines for calling Qhull
Top-level routines for returning results
Top-level routines for testing and debugging

»qhull.h and unix.c data types and constants

flagT Boolean flag as a bit
boolT boolean value, either True or False
CENTERtype to distinguish facet->center
qh_PRINT output formats for printing (qh.PRINTout)
qh_ALL argument flag for selecting everything
qh_ERR Qhull exit codes for indicating errors
qh_prompt version and long prompt for Qhull
qh_prompt2 synopsis for Qhull
qh_prompt3 concise prompt for Qhull
qh_version version stamp

»qhull.h other macros

traceN print trace message if qh.IStracing >= N.

»Quickhull routines in call order

main processes the command line, calls qhull() to do the work, and exits
qh_qhull construct the convex hull of a set of points
qh_build_withrestart allow restarts while calling qh_buildhull
qh_initbuild initialize hull and outside sets with point array
qh_partitionall partition all points into outside sets
qh_buildhull construct a convex hull by adding points one at a time
qh_nextfurthest return next furthest point for processing
qh_buildtracing trace an iteration of buildhull
qh_addpoint add a point to the convex hull
qh_findhorizon find the horizon and visible facets for a point
qh_partitionvisible partition points from facets in qh.visible_list to facets in qh.newfacet_list
qh_partitionpoint partition a point as inside, coplanar with, or outside a facet
qh_partitioncoplanar partition coplanar point into a facet
qh_precision restart on precision errors if not merging and if 'QJn'

»Top-level routines for initializing and terminating Qhull (in other modules)

qh_freebuild free memory used by qh_initbuild and qh_buildhull
qh_checkflags check flags for multiple frontends to qhull
qh_freeqhull free memory used by qhull
qh_init_A called before error handling initialized
qh_init_B called after points are defined
qh_initflags set flags and constants from command line
qh_restore_qhull restores a saved qhull
qh_save_qhull saves qhull for later restoring
qh_user_memsizes define additional quick allocation sizes

»Top-level routines for reading and modifying the input (in other modules)

qh_gram_schmidt implements Gram-Schmidt orthogonalization by rows
qh_projectinput project input along one or more dimensions + Delaunay projection
qh_randommatrix generate a random dimXdim matrix in range (-1,1)
qh_readpoints read points from input
qh_rotateinput rotate input points using row matrix
qh_scaleinput scale input points using qh low_bound/high_bound
qh_setdelaunay project points to paraboloid for Delaunay triangulation
qh_sethalfspace_all generate dual for halfspace intersection with interior point

»Top-level routines for calling Qhull (in other modules)

qh_addpoint add point to convex hull
qh_findbestfacet find facet that is furthest below a point
qh_findfacet_all exhaustive search for facet below a point
qh_qhull construct the convex hull of a set of points

»Top-level routines for returning results (in other modules)

qh_collectstatistics collect statistics for qh.facet_list
qh_nearvertex return nearest vertex to point
qh_point return point for a point ID
qh_pointfacet return temporary set of facets indexed by point ID
qh_pointid return ID for a point
qh_pointvertex return vertices (if any) for all points
qh_printallstatistics print all statistics
qh_printneighborhood print neighborhood of one or two facets
qh_printsummary print summary
qh_produce_output print the results of qh_qhull()
qh_setvoronoi_all compute Voronoi centers for all facets

»Top-level routines for testing and debugging (in other modules)

dfacet print facet by ID from debugger
dvertex print vertex by ID from debugger
qh_check_output check output
qh_check_points verify that all points are inside the convex hull
qh_errexit report error with a facet and a ridge
qh_errexit2 report error with two facets
qh_errprint print erroneous facets, ridge, and vertex
qh_printfacetlist print all fields for a list of facets

The Geometry Center Home Page

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