Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
Up: Qhull internals: Table of Contents
To: Qhull functions, macros, and data structures
To: GeomGlobalIoMemMergePolyQhullSetStatUser


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 neighboring 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

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.

Qhull 3.1 includes triangulation of non-simplicial facets ('Qt'). These facets, called tricoplanar, share the same normal. centrum, and Voronoi center. One facet (keepcentrum) owns these data structures. While tricoplanar facets are more accurate than the simplicial facets from joggled input, they may have zero area or flipped orientation.

Copyright © 1995-2002 The Geometry Center, Minneapolis MN


Geom GlobalIoMemMergePolyQhullSetStatUser

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


Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTrace
Up: Qhull internals: Table of Contents
To: Qhull functions, macros, and data structures
To: GeomGlobalIoMemMergePolyQhullSetStatUser


The Geometry Center Home Page

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