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

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-2003 The Geometry Center, Minneapolis MN

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

Index to merge.c and merge.h

• merge.h data types, macros, and global sets
• merge.h constants

• 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

»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

»merge.h constants

• 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

»top-level merge functions

• 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

»functions for identifying merges

• 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

»functions for determining the best merge

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

»functions for merging facets

• 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

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

• 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

»functions for renaming a vertex

• 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

»functions for identifying vertices for renaming

• 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

»functions for check and trace

• 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

The Geometry Center Home Page

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