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

## 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.

Copyright © 1995-2020 C.B. Barber

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

### Index to poly.c, poly2.c, poly.h, and libqhull.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_addfacetvertex add newvertex to facet.vertices if not already there
- 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_getreplacement get replacement facet for a visible facet
- 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_nextfacet2d return next facet and vertex for a 2d facet in qh_ORIENTclock order
- qh_opposite_vertex return the opposite vertex in facetA to neighbor
- qh_outcoplanar move points from outside set to coplanar set
- qh_replacefacetvertex replace oldvertex with newvertex in facet.vertices
- 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_neighbor_vertices return neighboring vertices for a vertex
- 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_update_vertexneighbors update vertex neighbors and delete interior vertices
- qh_update_vertexneighbors_cone update vertex neighbors for a cone of new facets 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_matchdupridge match duplicate ridges in hash table with a coplanar facet or pinched vertex
- qh_matchdupridge_coplanarhorizon match duplicate ridges in hash table with a coplanar horizon
- 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
- qh_printlists print out facet lists for debugging

### »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 free up the memory occupied by a 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_checklists Check and repair facetlist and its vertexlist for infinite loops or overwritten facets/vertices
- qh_checkpolygon check topological structure
- qh_checkvertex check vertex for consistency
- qh_infiniteloop report error for a loop 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