**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

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 aduplicate 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 aredundant facet.

A facet with fewer than three neighbors.Facet merging may leave a facet with one or two neighbors. This is called adegenerate facet.

A facet with flipped orientation.A facet's hyperplane may define a halfspace that does not include the interior point.This is called aflipped 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 asamecycle. 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 aredundant vertex.

**Copyright © 1995-2002 The Geometry Center, Minneapolis MN**

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

- top-level merge functions
- functions for identifying merges
- functions for determining the best merge
- functions for merging facets
- functions for merging a cycle of facets
- functions for renaming a vertex
- functions for identifying vertices for renaming
- functions for check and trace

- 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

- qh precision constants precision constants for Qhull
- MRG... indicates the type of a merge (mergeT->type)
- qh_ANGLEredundant indicates redundant merge in mergeT->angle
- qh_ANGLEdegen indicates degenerate facet in mergeT->angle
- qh_ANGLEconcave offset to indicate concave facets in mergeT->angle
- qh_MERGEapex flag for qh_mergefacet() to indicate an apex merge

- qh_all_merges merge all non-convex facets
- qh_checkzero check that facets are clearly convex
- qh_flippedmerges merge flipped facets into best neighbor
- qh_forcedmerges merge all duplicate ridges
- qh_merge_degenredundant merge degenerate and redundant facets
- qh_merge_nonconvex merge a non-convex ridge
- qh_premerge pre-merge non-convex facets
- qh_postmerge post-merge nonconvex facets as defined by maxcentrum/maxangle

- qh_appendmergeset appends an entry to qh.facet_mergeset
- qh_compareangle used by qsort() to order merges
- qh_comparemerge used by qsort() to order merges
- qh_degen_redundant_facet check for a degenerate and redundant facet
- qh_degen_redundant_neighbors append degenerate and redundant neighbors to qh.degen_mergeset
- qh_getmergeset_initial build initial qh.facet_mergeset
- qh_getmergeset update qh.facet_mergeset
- qh_mark_dupridges add duplicated ridges to qh.facet_mergeset
- qh_maydropneighbor drop neighbor relationship if no ridge between facet and neighbor
- qh_test_appendmerge test a pair of facets for convexity and append to qh.facet_mergeset if non-convex
- qh_test_vneighbors test vertex neighbors for convexity

- qh_findbest_test test neighbor for best merge
- qh_findbestneighbor finds best neighbor of a facet for merging (i.e., closest hyperplane)

- qh_copynonconvex copy non-convex flag to another ridge for the same neighbor
- qh_makeridges creates explicit ridges between simplicial facets
- qh_mergefacet merges one facet into another facet
- qh_mergeneighbors merges the neighbors of two facets
- qh_mergeridges merges the ridge sets of two facets
- qh_mergesimplex merge a simplicial facet into another simplicial facet
- qh_mergevertex_del delete a vertex due to merging one facet into another facet
- qh_mergevertex_neighbors merge the vertex neighbors of two facets
- qh_mergevertices merge the vertex sets of two facets
- qh_newvertices register all vertices as new vertices
- qh_updatetested clear tested flags and centrums involved in a merge
- qh_willdelete moves facet to qh.visible_list; sets replacement or NULL

If a point is coplanar with an horizon facet, the
corresponding new facets are linked together (a *samecycle*)
for merging.

- qh_basevertices return temporary set of base vertices for a samecycle
- qh_mergecycle merge a samecycle into a horizon facet
- qh_mergecycle_all merge all samecycles into horizon facets
- qh_mergecycle_facets finish merge of samecycle
- qh_mergecycle_neighbors merge neighbor sets for samecycle
- qh_mergecycle_ridges merge ridge sets for samecycle
- qh_mergecycle_vneighbors merge vertex neighbor sets for samecycle

- qh_comparevisit used by qsort() to order vertices by visitid
- qh_reducevertices reduce vertex sets
- qh_redundant_vertex returns true if detect and rename redundant vertex
- qh_rename_sharedvertex detect and rename a shared vertex
- qh_renameridgevertex rename oldvertex to newvertex in a ridge
- qh_renamevertex rename oldvertex to newvertex in ridges
- qh_remove_extravertices remove extra vertices in non-simplicial facets

- qh_find_newvertex locate new vertex for renaming old vertex
- qh_hashridge add ridge to hashtable
- qh_hashridge_find returns matching ridge in hashtable
- qh_neighbor_intersections return intersection of vertex sets for neighboring facets
- qh_vertexridges return temporary set of ridges adjacent to a vertex
- qh_vertexridges_facet add adjacent ridges for a vertex in facet

- qh_checkconnect check that new facets are connected
- qh_tracemerge print trace message after merge
- qh_tracemerging print trace message during post-merging

**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

Comments to: qhull@geom.umn.edu

Created: May 2, 1997 --- Last modified: see top