Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Qhull options: Table of Contents
Up: Qhull internals: Table of Contents

To: Qhull files (please wait while loading)
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

Qhull functions, macros, and data structures

The following sections provide an overview and index to Qhull's functions, macros, and data structures.

Each section starts with an introduction.

Qhull uses the following conventions:

• in code, global variables start with "qh "
• in documentation, global variables start with 'qh.'
• constants start with an upper case word
• important globals include an '_'
• functions, macros, and constants start with "qh_"
• data types end in "T"
• macros with arguments end in "_"
• iterators are macros that use local variables
• iterators for sets start with "FOREACH"
• iterators for lists start with "FORALL"
• qhull options are in single quotes (e.g., 'Pdn')
• lists are sorted alphabetically
• preprocessor directives on left margin for older compilers

When reading the code, please note that the global data structure, 'qh', is a macro. It either expands to "qh_qh." or to "qh_qh->". The later is used for applications which run concurrent calls to qh_qhull().

When reading code with an editor, a search for "procedure will locate the header of qh_procedure. A search for * procedure will locate the tail of qh_procedure.

If your web browser loads .c and .h files with an external application, change the MIME type of .c and .h files to "text/html". Do not use the Opera browser (it treats all '<' characters as HTML tags).

Please report documentation and link errors to qhull-bug@geom.umn.edu. If you have a program that checks internal links ("#..."), please send the results of running the program on qhull.

Brad Barber, Cambridge MA, August 3, 1998

Copyright © 1997-1998 The Geometry Center, Minneapolis MN

»Qhull files

This sections lists the .c and .h files for Qhull. Please refer to these files for detailed information.

qhull.h

Include file for the Qhull library, qhull.a. Data structures are documented under Poly. Global variables are documented under Global. Other data structures and variables are documented under Qhull or Geom.

 

Geom, geom.h, geom.c, geom2.c

Geometric routines. These routines implement mathematical functions such as Gaussian elimination and geometric routines needed for Qhull. Frequently used routines are in geom.c while infrequent ones are in geom2.c.

 

Global, global.c, qhull.h

Global routines. Qhull uses a global data structure, qh, to store globally defined constants, lists, sets, and variables. global.c initializes and frees these structures.

 

Io, io.h, io.c

Input and output routines. Qhull provides a wide range of input and output options.

 

Mem, mem.h, mem.c

Memory routines. Qhull provides memory allocation and deallocation. It uses quick-fit allocation.

 

Merge, merge.h, merge.c

Merge routines. Qhull handles precision problems by merging facets. These routines merge simplicial facets, merge non-simplicial facets, merge cycles of facets, and rename redundant vertices.

 

Poly, poly.h, poly.c, poly2.c, qhull.h

Polyhedral routines. Qhull produces a polyhedron as a list of facets with vertices, neighbors, ridges, and geometric information. Qhull.h defines the main data structures. Frequently used routines are in poly.c while infrequent ones are in poly2.c.

 

Qhull, qhull.c, qhull.h, qhull_a.h, unix.c

Top-level routines. The Quickhull algorithm is implemented by qhull.c. qhull_a.h includes all header files.

 

Set, qset.h, qset.c

Set routines. Qhull implements its data structures as sets. A set is an array of pointers that is expanded as needed. This is a separate package that may be used in other applications.

 

Stat, stat.h, stat.c

Statistical routines. Qhull maintains statistics about its implementation.

 

User, user.h, user.c, user_eg.c

User-defined routines. Qhull allows the user to configure the code with defined constants and specialized routines.

» 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

Index to geom.c, geom2.c, and geom.h

• geometric data types and constants
• mathematical macros
• mathematical functions
• computational geometry functions
• point array functions
• geometric facet functions
• geometric roundoff functions

»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_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_findbestnew find best new facet for point
• qh_findbestsharp find best new facet for point and detect sharp corners
• 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

»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
constants
• qh_maxouter return maximum outer plane
• qh_outerinner return actual outer and inner planes

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

global.c -- global variables and their functions

Qhull uses a global data structure, qh, to store globally defined constants, lists, sets, and variables. This allows multiple instances of Qhull to execute at the same time. The structure may be statically allocated or dynamically allocated with malloc(). See QHpointer.

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

Index to global.c and qhull.h

• Qhull's global variables
• Global variable and initialization routines

»Qhull's global variables

• qh all global variables for qhull are in qh,qhmem, and qhstat
• qh constants configuration flags and constants for Qhull
• qh precision constants precision constants for Qhull
• qh internal constants internal constants for Qhull
• qh facet and vertex lists lists of facets and vertices
• qh global variables minimum and maximum distances, next visit ids, several flags, and other global variables.
• qh global sets global sets for merging, hashing, input, etc.
• qh global buffers buffers for matrix operations and input
• qh static variables static variables for individual functions

»Global variable and initialization routines

• qh_appendprint append output format to qh.PRINTout
• qh_freebuffers free global memory buffers
• qh_freeqhull free memory used by qhull
• qh_init_A called before error handling initialized
• qh_init_B called after points are defined
• qh_init_qhull_command build qh.qhull_command from argc/argv
• qh_initflags set flags and constants from command line
• qh_initqhull_buffers initialize global memory buffers
• qh_initqhull_globals initialize global variables
• qh_initqhull_mem initialize Qhull memory management
• qh_initqhull_start initialize default values at Qhull startup
• qh_initthresholds initialize 'Pdn' and 'PDn' thresholds
• qh_option append option description to qh.global_options
• qh_restore_qhull restores a previously saved qhull
• qh_save_qhull saves qhull for a later qh_restore_qhull()
• qh_strtol duplicates strtod() and strtol()

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

io.c -- input and output operations

Qhull provides a wide range of input and output options. To organize the code, most output formats use the same driver:

    qh_printbegin( fp, format, facetlist, facets, printall );

    FORALLfacet_( facetlist )
      qh_printafacet( fp, format, facet, printall );

    FOREACHfacet_( facets )
      qh_printafacet( fp, format, facet, printall );

    qh_printend( fp, format );

Note the 'printall' flag. It selects whether or not qh_skipfacet() is tested.

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

Index to io.c and io.h

• io.h constants and types
• User level functions
• Print functions for all output formats
• Text output functions
• Text utility functions
• Geomview output functions
• Geomview utility functions

»io.h constants and types

• qh_MAXfirst maximum length of first two lines of stdin
• qh_WHITESPACE possible values of white space
• printvridgeT function to print results of qh_printvdiagram or qh_eachvoronoi

»User level functions

• qh_eachvoronoi_all visit each Voronoi ridge of the Voronoi diagram
• qh_printhelp_degenerate prints descriptive message for precision error
• qh_printhelp_singular print help message for singular data
• qh_printsummary print summary ('s')
• qh_produce_output prints out the result of qhull()
• qh_readfeasible read interior point from remainder and qh fin ('H')
• qh_readpoints read input points
• qh_setfeasible set interior point from qh feasible_string ('Hn,n,n')

»Print functions for all output formats

• qh_countfacets count good facets for printing and set visitid
• qh_markkeep mark good facets that meet qh.KEEParea ('PAn'), qh.KEEPmerge ('PMn'), and qh.KEEPminArea ('PFn')
• qh_order_vertexneighbors order neighbors for a 3-d vertex by adjacency ('i', 'o')
• qh_printafacet print facet in an output format
• qh_printbegin print header for an output format
• qh_printend print trailer for an output format
• qh_printfacetlist print facets in a facetlist
• qh_printfacets print facetlist and/or facet set in an output format
• qh_printneighborhood print neighborhood of one or two facets ('Po')
• qh_produce_output print the results of qh_qhull()
• qh_skipfacet True if not printing this facet ('Pdk:n', 'QVn', 'QGn')
• qh_facetvertices return vertices in a set of facets ('p')

»Text output functions

• qh_eachvoronoi print or visit each Voronoi ridge for an input site of the Voronoi diagram
• qh_printextremes print extreme points by point id (vertices of convex hull) ('Fx')
• qh_printextremes_2d print 2-d extreme points by point id ('Fx')
• qh_printextremes_d print extreme points of input sites for Delaunay triangulations ('Fx')
• qh_printfacet print all fields of a facet ('f')
• qh_printfacet2math print 2-d Mathematica output for a facet ('m')
• qh_printfacet3math print 3-d Mathematica facet ('m')
• qh_printfacet3vertex print vertices for a 3-d facet ('i', 'o')
• qh_printfacetheader prints header fields of a facet ('f')
• qh_printfacetNvertex_nonsimplicial print vertices for an N-d non-simplicial facet ('i', 'Ft')
• qh_printfacetNvertex_simplicial print vertices for an N-d simplicial facet ('i', 'o', 'Ft')
• qh_printfacetridges prints ridges of a facet ('f')
• qh_printpoints_out prints vertices for facets by their point coordinates ('p')
• qh_printridge print all fields for a ridge ('f')
• qh_printvdiagram print voronoi diagram as Voronoi vertices for each input pair
• qh_printvertex print all fields for a vertex ('f')
• qh_printvertexlist print vertices used by a list or set of facets ('f')
• qh_printvertices print a set of vertices ('f')
• qh_printvneighbors print vertex neighbors of vertices ('FN')
• qh_printvoronoi print voronoi diagram in 'o' or 'G' format

»Text utility functions

• dfacet print facet by id
• dvertex print vertex by id
• qh_compare_facetarea used by qsort() to order facets by area
• qh_compare_facetmerge used by qsort() to order facets by number of merges
• qh_compare_facetvisit used by qsort() to order facets by visit id or id
• qh_compare_vertexpoint used by qsort() to order vertices by point id
• qh_detvnorm determine normal for Voronoi ridge
• qh_detvridge determine Voronoi ridge for an input site
• qh_detvridge3 determine 3-d Voronoi ridge for an input site
• qh_facet2point return two projected temporary vertices for a 2-d facet ('m', 'G')
• qh_markvoronoi mark Voronoi vertices for printing
• qh_printcenter print facet->center as centrum or Voronoi center ('Ft', 'v p', 'FC', 'f')
• qh_printpoint, qh_printpointid, print coordinates of a point ('p', 'o', 'Fp', 'G', 'f')
• qh_printpoint3 prints 2-d, 3-d, or 4-d point as 3-d coordinates ('G')
• qh_printvdiagram2 print voronoi diagram for each ridge of each vertex from qh_markvoronoi
• qh_printvnorm print separating plane of the Voronoi diagram for a pair of input sites
• qh_printvridge print ridge of the Voronoi diagram for a pair of input sites
• qh_printvridge3 print one ridge of a 3-d Voronoi diagram for a pair of input sites
• qh_projectdim3 project 2-d 3-d or 4-d point to a 3-d point ('G')

»Geomview output functions

• qh_printfacet2geom print facet as a 2-d VECT object
• qh_printfacet2geom_points print points as a 2-d VECT object with offset
• qh_printfacet3geom_nonsimplicial print Geomview OFF for a 3-d nonsimplicial facet.
• qh_printfacet3geom_points prints a 3-d facet as OFF Geomview object.
• qh_printfacet3geom_simplicial print Geomview OFF for a 3-d simplicial facet.
• qh_printfacet4geom_nonsimplicial print Geomview 4OFF file for a 4d nonsimplicial facet
• qh_printfacet4geom_simplicial print Geomview 4OFF file for a 4d simplicial facet
• qh_printhyperplaneintersection print hyperplane intersection as OFF or 4OFF
• qh_printvoronoi print voronoi diagram in 'o' or 'G' format

»Geomview utility functions

• qh_geomplanes return outer and inner planes for Geomview
• qh_printcentrum print centrum for a facet in OOGL format
• qh_printend4geom helper function for qh_printbegin/printend
• qh_printhyperplaneintersection print Geomview OFF or 4OFF for the intersection of two hyperplanes in 3-d or 4-d
• qh_printline3geom prints a line as a VECT
• qh_printpointvect prints a 2-d or 3-d point as 3-d VECT's
• qh_printpointvect2 prints a 2-d or 3-d point as 2 3-d VECT's
• qh_printspheres prints 3-d vertices as OFF spheres
• qh_printspheres3 print 3-d vertices as spheres (OFF)

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

mem.c -- memory operations

Qhull uses quick-fit memory allocation. It maintains a set of free lists for a variety of small allocations. A small request returns a block from the best fitting free list. If the free list is empty, Qhull allocates a block from a reserved buffer.

Use 'T5' to trace memory allocations.

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

Index to mem.c and mem.h

• mem.h data types
• mem.h macros
• User level functions

»mem.h data types and constants

• ptr_intT for casting a void* to an integer-type
• qhmemT global memory structure for mem.c
• qh_NOmem disable memory allocation

»mem.h macros

• qh_memalloc_ allocate memory
• qh_memfree_ free memory

»User level functions

• qh_memalloc allocate memory
• qh_memfree free memory
• qh_meminit initialize memory
• qh_memstatistics print memory statistics
• qh_NOmem allocation routines with malloc() and free()

»Initialization and termination functions

• qh_intcompare used by qsort and bsearch to compare two integers
• qh_memfreeshort frees up all short and qhmem memory allocations
• qh_meminit initialize memory
• qh_meminitbuffers initialize qhmem
• qh_memsetup set up memory after running memsize()
• qh_memsize define a free list for this size
• qh_memstatistics print out memory statistics

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

merge.c -- facet merge operations

Qhull handles precision problems by merging facets. Except for redundant vertices, it corrects a problem by merging two facets. When done, all facets are clearly convex. See Imprecision in Qhull for further information.

Users may joggle the input ('QJn') instead of merging facets.

Qhull detects and corrects the following problems:

• More than two facets meeting at a ridge. When Qhull creates facets, it creates an even number of facets for each ridge. A convex hull always has two facets for each ridge. More than two facets may be created if non-adjacent facets share a vertex. This is called a duplicate ridge. In 2-d, a duplicate ridge would create a loop of facets.

• A facet contained in another facet. Facet merging may leave all vertices of one facet as a subset of the vertices of another facet. This is called a redundant facet.

• A facet with fewer than three neighbors. Facet merging may leave a facet with one or two neighbors. This is called a degenerate facet.

• A facet with flipped orientation. A facet's hyperplane may define a halfspace that does not include the interior point.This is called a flipped facet.

• A coplanar horizon facet. A newly processed point may be coplanar with an horizon facet. Qhull creates a new facet without a hyperplane. It links new facets for the same horizon facet together. This is called a samecycle. The new facet or samecycle is merged into the horizon facet.

• Concave facets. A facet's centrum may be above a neighboring facet. If so, the facets meet at a concave angle.

• Coplanar facets. A facet's centrum may be coplanar with a neighboring facet (i.e., it is neither clearly below nor clearly above the facet's hyperplane). Qhull removes coplanar facets in independent sets sorted by angle.

• Redundant vertex. A vertex may have fewer than three neighboring facets. If so, it is redundant and may be renamed to an adjacent vertex without changing the topological structure.This is called a redundant vertex.

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

Index to merge.c and merge.h

• merge.h data types, macros, and global sets
• merge.h constants

• top-level merge functions
• functions for identifying merges
• functions for determining the best merge
• functions for merging facets
• functions for merging a cycle of facets
• functions for renaming a vertex
• functions for identifying vertices for renaming
• functions for check and trace

»merge.h data types, macros, and global sets

• mergeT structure to identify a merge of two facets
• FOREACHmerge_ assign 'merge' to each merge in merges
• qh global sets qh.facet_mergeset contains non-convex merges while qh.degen_mergeset contains degenerate and redundant facets

»merge.h constants

• qh precision constants precision constants for Qhull
• MRG... indicates the type of a merge (mergeT->type)
• qh_ANGLEredundant indicates redundant merge in mergeT->angle
• qh_ANGLEdegen indicates degenerate facet in mergeT->angle
• qh_ANGLEconcave offset to indicate concave facets in mergeT->angle
• qh_MERGEapex flag for qh_mergefacet() to indicate an apex merge

»top-level merge functions

• qh_all_merges merge all non-convex facets
• qh_checkzero check that facets are clearly convex
• qh_flippedmerges merge flipped facets into best neighbor
• qh_forcedmerges merge all duplicate ridges
• qh_merge_degenredundant merge degenerate and redundant facets
• qh_merge_nonconvex merge a non-convex ridge
• qh_premerge pre-merge non-convex facets
• qh_postmerge post-merge nonconvex facets as defined by maxcentrum/maxangle

»functions for identifying merges

• qh_appendmergeset appends an entry to qh.facet_mergeset
• qh_compareangle used by qsort() to order merges
• qh_comparemerge used by qsort() to order merges
• qh_degen_redundant_facet check for a degenerate and redundant facet
• qh_degen_redundant_neighbors append degenerate and redundant neighbors to qh.degen_mergeset
• qh_facetdegen true if facet already in mergeset as a degenerate
• qh_getmergeset_initial build initial qh.facet_mergeset
• qh_getmergeset update qh.facet_mergeset
• qh_mark_dupridges add duplicated ridges to qh.facet_mergeset
• qh_maydropneighbor drop neighbor relationship if no ridge between facet and neighbor
• qh_test_appendmerge test a pair of facets for convexity and append to qh.facet_mergeset if non-convex
• qh_test_vneighbors test vertex neighbors for convexity

»functions for determining the best merge

• qh_findbest_test test neighbor for best merge
• qh_findbestneighbor finds best neighbor of a facet for merging (i.e., closest hyperplane)

»functions for merging facets

• qh_copynonconvex copy non-convex flag to another ridge for the same neighbor
• qh_makeridges creates explicit ridges between simplicial facets
• qh_mergefacet merges one facet into another facet
• qh_mergeneighbors merges the neighbors of two facets
• qh_mergeridges merges the ridge sets of two facets
• qh_mergesimplex merge a simplicial facet into another simplicial facet
• qh_mergevertex_del delete a vertex due to merging one facet into another facet
• qh_mergevertex_neighbors merge the vertex neighbors of two facets
• qh_mergevertices merge the vertex sets of two facets
• qh_newvertices register all vertices as new vertices
• qh_mergevertices2d merges vertices1 into vertices2 in 2-d case
• qh_updatetested clear tested flags and centrums involved in a merge
• qh_willdelete moves facet to qh.visible_list; sets replacement or NULL

»functions for merging a cycle of facets

If a point is coplanar with an horizon facet, the corresponding new facets are linked together (a samecycle) for merging.

• qh_basevertices return temporary set of base vertices for a samecycle
• qh_mergecycle merge a samecycle into a horizon facet
• qh_mergecycle_all merge all samecycles into horizon facets
• qh_mergecycle_facets finish merge of samecycle
• qh_mergecycle_neighbors merge neighbor sets for samecycle
• qh_mergecycle_ridges merge ridge sets for samecycle
• qh_mergecycle_vneighbors merge vertex neighbor sets for samecycle

»functions for renaming a vertex

• qh_comparevisit used by qsort() to order vertices by visitid
• qh_reducevertices reduce vertex sets
• qh_redundant_vertex returns true if detect and rename redundant vertex
• qh_rename_sharedvertex detect and rename a shared vertex
• qh_renameridgevertex rename oldvertex to newvertex in a ridge
• qh_renamevertex rename oldvertex to newvertex in ridges
• qh_remove_extravertices remove extra vertices in non-simplicial facets

»functions for identifying vertices for renaming

• qh_find_newvertex locate new vertex for renaming old vertex
• qh_hashridge add ridge to hashtable
• qh_hashridge_find returns matching ridge in hashtable
• qh_neighbor_intersections return intersection of vertex sets for neighboring facets
• qh_vertexridges return temporary set of ridges adjacent to a vertex
• qh_vertexridges_facet add adjacent ridges for a vertex in facet

»functions for check and trace

• qh_checkconnect check that new facets are connected
• qh_checkridge_boundary checks that ridges of a facet are boundaryless
• qh_tracemerge print trace message after merge
• qh_tracemerging print trace message during post-merging

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

poly.c, poly2.c -- polyhedron operations

Qhull uses dimension-free terminology. Qhull builds a polyhedron in dimension d. A polyhedron is a simplicial complex of faces with geometric information for the top and bottom-level faces. A (d-1)-face is a facet, a (d-2)-face is a ridge, and a 0-face is a vertex. For example in 3-d, a facet is a polygon and a ridge is an edge. A facet is built from a ridge (the base) and a vertex (the apex). See Qhull's data structures.

Qhull's primary data structure is a polyhedron. A polyhedron is a list of facets. Each facet has a set of neighoring facets and a set of vertices. Each facet has a hyperplane. For example, a tetrahedron has four facets. If its vertices are a, b, c, d, and its facets are 1, 2, 3, 4, the tetrahedron is

• facet 1
  • vertices: b c d
  • neighbors: 2 3 4
• facet 2
  • vertices: a c d
  • neighbors: 1 3 4
• facet 3
  • vertices: a b d
  • neighbors: 1 2 4
• facet 4
  • vertices: a b c
  • neighbors: 1 2 3

A facet may be simplicial or non-simplicial. In 3-d, a simplicial facet has three vertices and three neighbors. A nonsimplicial facet has more than three vertices and more than three neighbors. A nonsimplicial facet has a set of ridges and a centrum.

A simplicial facet has an orientation. An orientation is either top or bottom. The flag, facet->toporient, defines the orientation of the facet's vertices. For example in 3-d, 'top' is left-handed orientation (i.e., the vertex order follows the direction of the left-hand fingers when the thumb is pointing away from the center). Except for axis-parallel facets in 5-d and higher, topological orientation determines the geometric orientation of the facet's hyperplane.

A nonsimplicial facet is due to merging two or more facets. The facet's ridge set determine a simplicial decomposition of the facet. Each ridge is a 1-face (i.e., it has two vertices and two neighboring facets). The orientation of a ridge is determined by the order of the neighboring facets. The flag, facet->toporient,is ignored.

A nonsimplicial facet has a centrum for testing convexity. A centrum is a point on the facet's hyperplane that is near the center of the facet. Except for large facets, it is the arithmetic average of the facet's vertices.

A nonsimplicial facet is an approximation that is defined by offsets from the facet's hyperplane. When Qhull finishes, the outer plane is above all points while the inner plane is below the facet's vertices. This guarantees that any exact convex hull passes between the inner and outer planes. The outer plane is defined by facet->maxoutside while the inner plane is computed from the facet's vertices.

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

Index to poly.c, poly2.c, poly.h, and qhull.h

• Data types and global lists for polyhedrons
• poly.h constants
• Global FORALL macros
• FORALL macros
• FOREACH macros
• Indexed FOREACH macros
• Other macros for polyhedrons

   

• Facetlist functions
• Facet functions
• Vertex, ridge, and point functions
• Hashtable functions
• Allocation and deallocation functions
• Check functions

»Data types and global lists for polyhedrons

• hashentryT hash table entry for sub-ridges
• facetT defines a facet
• ridgeT defines a ridge
• vertexT defines a vertex
• qh facet and vertex lists lists of facets and vertices
• qh global sets global sets for merging, hashing, input, etc.

»poly.h constants

• ALGORITHMfault flag to not report errors in qh_checkconvex()
• DATAfault flag to report errors in qh_checkconvex()
• DUPLICATEridge special value for facet->neighbor to indicate a duplicate ridge
• MERGEridge special value for facet->neighbor to indicate a merged ridge

»Global FORALL macros

• FORALLfacets assign 'facet' to each facet in qh.facet_list
• FORALLnew_facets assign 'facet' to each facet in qh.newfacet_list
• FORALLvisible_facets assign 'visible' to each visible facet in qh.visible_list
• FORALLpoints assign 'point' to each point in qh.first_point, qh.num_points
• FORALLvertices assign 'vertex' to each vertex in qh.vertex_list

»FORALL macros

• FORALLfacet_ assign 'facet' to each facet in facetlist
• FORALLpoint_ assign 'point' to each point in points array
• FORALLsame_ assign 'same' to each facet in samecycle
• FORALLsame_cycle_ assign 'same' to each facet in samecycle
• FORALLvertex_ assign 'vertex' to each vertex in vertexlist

»FOREACH macros

• FOREACHentry_ assign 'entry' to each hash entry in entry set
• FOREACHfacet_ assign 'facet' to each facet in facets
• FOREACHneighbor_ assign 'neighbor' to each facet in facet->neighbors or vertex->neighbors
• FOREACHnewfacet_ assign 'newfacet' to each facet in facet set
• FOREACHpoint_ assign 'point' to each point in points set
• FOREACHridge_ assign 'ridge' to each ridge in ridge set
• FOREACHvertex_ assign 'vertex' to each vertex in vertex set
• FOREACHvertexA_ assign 'vertexA' to each vertex in vertex set
• FOREACHvisible_ assign 'visible' to each facet in facet set

»Indexed FOREACH macros

• FOREACHfacet_i_ assign 'facet' and 'facet_i' to each facet in facet set
• FOREACHneighbor_i_ assign 'neighbor' and 'neighbor_i' to each facet in facet->neighbors or vertex->neighbors
• FOREACHpoint_i_ assign 'point' and 'point_i' to each point in points set
• FOREACHridge_i_ assign 'ridge' and 'ridge_i' to each ridge in ridges set
• FOREACHvertex_i_ assign 'vertex' and 'vertex_i' to each vertex in vertices set
• FOREACHvertexreverse12_ assign 'vertex' to each vertex in vertex set; reverse the order of first two vertices

»Other macros for polyhedrons

• getid_ return id for a facet, ridge, or vertex
• otherfacet_ return neighboring facet for a ridge in a facet

»Facetlist functions

• qh_appendfacet appends facet to end of qh.facet_list
• qh_attachnewfacets attach new facets in qh.newfacet_list to the horizon
• qh_findgood identify good facets for qh.PRINTgood
• qh_findgood_all identify more good facets for qh.PRINTgood
• qh_furthestnext move facet with furthest of furthest points to facet_next
• qh_initialhull construct the initial hull as a simplex of vertices
• qh_nearcoplanar remove near-inside points from coplanar sets
• qh_nonupper return first non-flipped facet
• qh_prependfacet prepends facet to start of facetlist
• qh_removefacet unlinks facet from qh.facet_list
• qh_resetlists reset qh.newvertex_list, qh.newfacet_list, and qh.visible_list

»Facet functions

• qh_createsimplex create a simplex of facets from a set of vertices
• qh_furthestout make furthest outside point the last point of a facet's outside set
• qh_makenew_nonsimplicial make new facets from ridges of visible facets
• qh_makenew_simplicial make new facets for horizon neighbors
• qh_makenewfacet create a facet from vertices and apex
• qh_makenewfacets make new facets from vertex, horizon facets, and visible facets
• qh_makenewplanes make new hyperplanes for facets
• qh_outcoplanar move points from outside set to coplanar set
• qh_setvoronoi_all compute Voronoi centers for all facets

»Vertex, ridge, and point functions

• qh_appendvertex append vertex to end of qh.vertex_list,
• qh_facet3vertex return an oriented vertex set for a 3-d facet
• qh_facetintersect return intersection of simplicial facets
• qh_initialvertices return non-singular set of initial vertices
• qh_isvertex true if point is in a vertex set
• qh_nearvertex return nearest vertex to point
• qh_nextridge3d iterate over each ridge and vertex for a 3-d facet
• 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 temporary set of vertices indexed by point id
• qh_removevertex unlink vertex from qh.vertex_list,
• qh_updatevertices update vertex neighbors and delete interior vertices
• qh_vertexintersect intersect two vertex sets
• qh_vertexintersect_new return intersection of two vertex sets
• qh_vertexneighhbors for each vertex in hull, determine facet neighbors
• qh_vertexsubset returns True if vertexsetA is a subset of vertexsetB

»Hashtable functions

• qh_addhash add hash element to linear hash table
• qh_gethash return hash value for a set
• qh_matchduplicates match duplicate ridges in hash table
• qh_matchneighbor try to match subridge of new facet with a neighbor
• qh_matchnewfacets match new facets with their new facet neighbors
• qh_matchvertices tests whether a facet and hash entry match at a ridge
• qh_newhashtable allocate a new qh.hash_table
• qh_printhashtable print hash table

»Allocation and deallocation functions

• qh_clearcenters clear old data from facet->center
• qh_deletevisible delete visible facets and vertices
• qh_delfacet free up the memory occupied by a facet
• qh_delridge delete ridge
• qh_delvertex delete vertex
• qh_newfacet create and allocate space for a facet
• qh_newridge create and allocate space for a ridge
• qh_newvertex create and allocate space for a vertex

»Check functions

• qh_check_bestdist check that points are not outside of facets
• qh_check_maxout updates qh.max_outside and checks all points against bestfacet
• qh_check_output check topological and geometric output
• qh_check_point check that point is not outside of facet
• qh_check_points check that all points are inside all facets
• qh_checkconvex check that each ridge in facetlist is convex
• qh_checkfacet check for consistency errors in facet
• qh_checkflipped check facet orientation to the interior point
• qh_checkflipped_all check facet orientation for a facet list
• qh_checkpolygon check topological structure
• qh_checkvertex check vertex for consistency
• qh_infiniteloop report error for a loop of facets
• qh_printlists print out facet list for debugging

» 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 other 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 other 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

»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

• 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_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

• 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

• 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

• 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

• 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

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

qset.c -- set data type and operations

Qhull's data structures are constructed from sets. The functions and macros in qset.c construct, iterate, and modify these sets. They are the most frequently called functions in Qhull. For this reason, efficiency is the primary concern.

In Qhull, a set is represented by an unordered array of pointers with a maximum size and a NULL terminator (setT). Most sets correspond to mathematical sets (i.e., the pointers are unique). Some sets are sorted to enforce uniqueness. Some sets are ordered. For example, the order of vertices in a ridge determine the ridge's orientation. If you reverse the order of adjacent vertices, the orientation reverses. Some sets are not mathematical sets. They may be indexed as an array and they may include NULL pointers.

The most common operation on a set is to iterate its members. This is done with a 'FOREACH...' macro. Each set has a custom macro. For example, 'FOREACHvertex_' iterates over a set of vertices. Each vertex is assigned to the variable 'vertex' from the pointer 'vertexp'.

Most sets are constructed by appending elements to the set. The last element of a set is either NULL or the index of the terminating NULL for a partially full set. If a set is full, appending an element copies the set to a larger array.

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

Index to qset.c and qset.h

• Data types and constants
• FOREACH macros
• access and size macros
• internal macros
• address macros

   

• Allocation and deallocation functions
• Access and predicate functions
• Add functions
• Check and print functions
• Copy, compact, and zero functions
• Delete functions
• Temporary set functions

»Data types and constants

• SETelemsize size of a set element in bytes
• setT a set with a maximum size and a current size
• qh global sets global sets for temporary sets, etc.

»FOREACH macros

• FOREACHelem_ assign 'elem' to each element in a set
• FOREACHset_ assign 'set' to each set in a set of sets
• FOREACHsetelement_ define a FOREACH iterator
• FOREACHsetelement_i_ define an indexed FOREACH iterator
• FOREACHsetelementreverse_ define a reversed FOREACH iterator
• FOREACHsetelementreverse12_ define a FOREACH iterator with e[1] and e[0] reversed

»Access and size macros

• SETelem_ return the n'th element of set
• SETelemt_ return the n'th element of set as a type
• SETempty_ return true (1) if set is empty
• SETfirst_ return first element of set
• SETfirstt_ return first element of set as a type
• SETindex_ return index of elem in set
• SETreturnsize_ return size of a set (normally use qh_setsize)
• SETsecond_ return second element of set
• SETsecondt_ return second element of set as a type

»Internal macros

• SETsizeaddr_ return pointer to end element of a set (indicates current size)

»address macros

• SETaddr_ return address of a set's elements
• SETelemaddr_ return address of the n'th element of a set
• SETref_ l.h.s. for modifying the current element in a FOREACH iteration

»Allocation and deallocation functions

• qh_setfree free the space occupied by a set
• qh_setfree2 free a set and its elements
• qh_setfreelong free a set only if it is in long memory
• qh_setnew create a new set

»Access and predicate functions

• qh_setequal return 1 if two sorted sets are equal
• qh_setequal_except return 1 if two sorted sets are equal except for an element
• qh_setequal_skip return 1 if two sorted sets are equal except for a pair of skipped elements
• qh_setequal_skip return 1 if two sorted sets are equal except for a pair of skipped elements
• qh_setin return 1 if an element is in a set
• qh_setindex return the index of an element in a set
• qh_setlast return last element of a set
• qh_setsize returns the size of a set

»Add functions

• qh_setaddnth add a element as n'th element of sorted or unsorted set
• qh_setaddsorted add an element to a sorted set
• qh_setappend append an element to a set
• qh_setappend_set append a set of elements to a set
• qh_setappend2ndlast add an element as the next to the last element in a set
• qh_setlarger return a larger set with the same elements
• qh_setreplace replace one element with another in a set
• qh_setunique add an element if it is not already in a set

»Check and print functions

• qh_setcheck check a set for validity
• qh_setprint print a set's elements to fp

»Copy, compact, and zero functions

• qh_setcompact compact NULLs from an unsorted set
• qh_setcopy make a copy of a sorted or unsorted set
• qh_setduplicate duplicate a set and its elements
• qh_settruncate truncate a set to size elements
• qh_setzero zero the remainder of a set

»Delete functions

• qh_setdel delete an element from an unsorted set.
• qh_setdellast delete and return last element from a set
• qh_setdelnth delete and return nth element from an unsorted set
• qh_setdelnthsorted delete and return nth element from a sorted set
• qh_setdelsorted delete an element from a sorted set
• qh_setnew_delnthsorted create a sorted set not containing the nth element

»Temporary set functions

• qh_settemp return a temporary set and append it qhmem.tempstack
• qh_settempfree free and pop a set from qhmem.tempstack
• qh_settempfree_all free all sets in qhmem.tempstack
• qh_settemppop pop a set from qhmem.tempstack (makes it permanent)
• qh_settemppush push a set unto qhmem.tempstack (makes it temporary)

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

stat.c -- statistical operations

Qhull records many statistics. These functions and macros make it inexpensive to add a statistic.

As with Qhull's global variables, the statistics data structure is accessed by a macro, 'qhstat'. If qh_QHpointer is defined, the macro is 'qh_qhstat->', otherwise the macro is 'qh_qhstat.'. Statistics may be turned off in user.h. If so, all but the 'zz' statistics are ignored.

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

Index to stat.c and stat.h

• stat.h types
• stat.h constants
• stat.h macros
• stat.c functions

»stat.h types

• intrealT union of integer and real
• qhstat global data structure for statistics

»stat.h constants

• qh_KEEPstatistics 0 turns off most statistics
• Z..., W... integer (Z) and real (W) statistics
• ZZstat Z.../W... statistics that remain defined if qh_KEEPstatistics=0
• ztype zdoc, zinc, etc. for definining statistics

»stat.h macros

• MAYdebugx called frequently for error trapping
• zadd_/wadd_ add value to an integer or real statistic
• zdef_ define a statistic
• zinc_ increment an integer statistic
• zmax_/wmax_ update integer or real maximum statistic
• zmin_/wmin_ update integer or real minimum statistic
• zval_/wval_ set or return value of a statistic

»stat.c functions

• qh_allstatA define statistics in groups of 20
• qh_allstatistics reset printed flag for all statistics
• qh_collectstatistics collect statistics for qh.facet_list
• qh_freestatistics free memory used for statistics
• qh_initstatistics allocate and initialize statistics
• qh_newstats returns True if statistics for zdoc
• qh_nostatistic true if no statistic to print
• qh_printallstatistics print all statistics
• qh_printstatistics print statistics to a file
• qh_printstatlevel print level information for a statistic
• qh_printstats print statistics for a zdoc group
• qh_stddev compute the standard deviation and average from statistics

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

user.c -- user-definable operations

This section contains functions and constants that the user may want to change.

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

Index to user.c and user.h

• user.h data types and configuration macros
• joggle constants
• performance related constants
• memory and other constants
• conditional compilation
• merge constants
• user.c functions

»user.h data types and configuration macros

• realT, qh_REAL... size of floating point numbers
• qh_CPUclock clock() function for reporting the total time spent by Qhull
• qh_ORIENTclock define convention for orienting facets
• qh_RANDOM... random number generator

»joggle constants

• qh_JOGGLEagain how often to retry before using qh_JOGGLEmaxincrease again
• qh_JOGGLEdefault default value for qh.JOGGLEmax for 'QP'
• qh_JOGGLEincrease factor to increase qh.JOGGLEmax on retrys for 'QPn'
• qh_JOGGLEmaxincrease max for increasing qh.JOGGLEmax relative to qh.MAXwidth
• qh_JOGGLEmaxretry report error if this many retries
• qh_JOGGLEretry how often to retry before using qh_JOGGLEmax

»performance related constants

• qh_HASHfactor total/used hash slots
• qh_INITIALmax if dim >= qh_INITIALmax, use min/max coordinate points for initial simplex
• qh_INITIALsearch if qh.INITIALmax, search points up to this dimension
• qh_NOtrace disallow tracing
• qh_VERIFYdirect 'Tv' verifies all points X facets if op count is smaller

»memory and other constants

• qh_DEFAULTbox default box size (Geomview expects 0.5)
• qh_INFINITE on output, indicates Voronoi center at infinity
• qh_MEMalign memory alignment for qh_meminitbuffers() in global.c
• qh_MEMbufsize size of additional memory buffers
• qh_MEMinitbuf size of initial memory buffer

»conditional compilation

• compiler defined symbols, e.g., _STDC_ and _cplusplus
• qh_COMPUTEfurthest compute furthest distance to an outside point instead of storing it with the facet
• qh_KEEPstatistics enable statistic gathering and reporting with option 'Ts'
• qh_MAXoutside record outer plane for each facet
• qh_NOmerge disable facet merging
• qh_NOtrace disable tracing with option 'T4'
• qh_QHpointer access global data with pointer or static structure
• qh_QUICKhelp use abbreviated help messages, e.g., for degenerate inputs

»merge constants

• qh_BESTcentrum when does qh_findbestneighbor() test centrums?
• qh_BESTnonconvex when does qh_findbestneighbor() test nonconvex ridges only?
• qh_COPLANARratio what is qh.MINvisible?
• qh_DIMreduceBuild max dimension for vertex reduction
• qh_DIMmergeVertex max dimension for vertex merging
• qh_DISToutside when does qh_findbestnew() stop search?
• qh_MAXnarrow max. cosine for qh.NARROWhull
• qh_MAXnewcentrum when does qh_reducevertices_centrum() reset the centrum?
• qh_MAXnewmerges when does qh_merge_nonconvex() call qh_reducevertices_centrums?
• qh_RATIOnearinside ratio for retaining inside points for qh_check_maxout()
• qh_USEfindbestnew cut-off between qh_findbest() and qh_findbestnew()
• qh_WIDEcoplanar what is a WIDEfacet?
• qh_WARNnarrow max. cosine to warn about qh.NARROWhull

»user.c functions

• qh_errexit report error and exit qhull()
• qh_errlog write qh.errmsg and open qh.ferrlog
• qh_errprint print information about facets and ridges
• qh_new_qhull call qhull on an array of points
• qh_printfacetlist print all fields of all facets

Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Qhull options: Table of Contents
Up: Qhull internals: Table of Contents

To: Qhull files
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

The Geometry Center Home Page

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