Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Up: Qhull code: Table of Contents
To: Qhull functions, macros, and data structures
To: Geom Global
Io Mem
Merge Poly
Qhull Set
Stat User
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-2012 C.B. Barber
» Geom Global Io Mem Merge Poly Qhull Set Stat User
If a point is coplanar with an horizon facet, the corresponding new facets are linked together (a samecycle) for merging.
Up:
Home page for
Qhull
Up: Qhull manual: Table of Contents
Up: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Up: Qhull code: Table of Contents
To: Qhull functions, macros, and data structures
To: Geom
Global Io
Mem Merge
Poly Qhull
Set Stat
User
Comments to: qhull@qhull.org
Created: May 2, 1997 --- Last modified: see top