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

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

Copyright © 1995-2015 C.B. Barber

» Geom GlobalIoMemMergePolyQhullSetStatUser

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

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

### »functions for check and trace

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

The Geometry Center Home Page

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