Up: ProgramsOptionsOutputFormatsGeomviewPrintQhullPrecisionTraceFunctions (local)
Up: Qhull code
To: GeomGlobalIoMemMergePolyQhullSetStatUser

## merge_r.c -- facet merge operations

Qhull handles precision problems by merged facets or joggled input. 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 subridge. This is called a dupridge. In 2-d, a dupridge would create a loop of facets. See 'pinched vertices' below for the resolution of a dupridge.
• 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.
• Pinched vertices. Nearly adjacent vertices may allow a dupridge that connects more than two new facets. A pinched vertex is the nearest horizon vertex that is a neighbor of a dupridge vertex. In 4-D and higher, both vertices may be in the same dupridge. If the vertices are in new facets with inverse orientation, the facets cannot be merged. If so, qhull merges the pinched vertices and recreates the cone of new facets. For a discussion, see 'Nearly adjacent vertices within 1e-13' in Limitations of merged facets.

» Geom GlobalIoMemMergePolyQhullSetStatUser

### »merge_r.h data types, macros, and global sets

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

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