Up: Home page for Qhull (local)
Up: Qhull manual: contents
Up: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
Up: Qhull code
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

libqhull_r.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, libqhull_r.h, contains prototypes for these functions.

Copyright © 1995-2020 C.B. Barber

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

Index to libqhull_r.c, libqhull_r.h, and unix_r.c

• libqhull_r.h and unix_r.c data types and constants
• libqhull_r.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

»libqhull_r.h and unix_r.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 status codes for indicating errors
• qh_FILEstderr Fake stderr to distinguish error output from normal output [C++ only]
• qh_prompt version and long prompt for Qhull
• qh_prompt2 synopsis for Qhull
• qh_prompt3 concise prompt for Qhull
• qh_version version stamp

»libqhull_r.h other macros

• traceN print trace message if qh.IStracing >= N.
• QHULL_UNUSED declare an unused variable to avoid warnings.

»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_buildcone build cone of new facets from furthest to the horizon
• qh_premerge pre-merge non-convex facets
• 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_joggle_restart if joggle ('QJn') and not merging, restart on precision errors

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

• qh_freebuild free memory used by qh_initbuild and qh_buildhull
• 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_rboxpoints generate points for qhull
• 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

Up: Home page for Qhull (local)
Up: Qhull manual: contents
Up: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
Up: Qhull code
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

The Geometry Center Home Page

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