poly.c, poly2.c -- polyhedron operations

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

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

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.

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.

» 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

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

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_prependfacet prepends facet to start of facetlist
qh_printfacetlist print facets in a facetlist
qh_printlists print out facet list for debugging
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_findbestlower find best non-upper, non-flipped facet for point at upperfacet
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
qh_triangulate triangulate non-simplicial facets
qh_triangulate_facet triangulate a non-simplicial facet
qh_triangulate_link link facets together from qh_triangulate
qh_triangulate_mirror delete mirrored facets from qh_triangulate
qh_triangulate_null delete null facet from qh_triangulate

»Vertex, ridge, and point functions

qh_appendvertex append vertex to end of qh.vertex_list,
qh_detvridge determine Voronoi ridge for an input site
qh_detvridge3 determine 3-d Voronoi ridge for an input site
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_vertexneighbors 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

The Geometry Center Home Page

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