Up: Home page for Qhull (local)
Up: Qhull manual: contents
Up: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
Up: Qhull code
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

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.

Copyright © 1995-2020 C.B. Barber

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

Index to merge_r.c and merge_r.h

• merge_r.h data types, macros, and global sets
• merge_r.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 pinched vertices of dupridges
• functions for renaming a vertex
• functions for identifying vertices for renaming
• functions for check and trace

»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

»merge_r.h constants

• qh precision constants precision constants for Qhull
• MRG... indicates the type of a merge (mergeT->type)
• qh_ANGLEnone indicates missing 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 dupridges
• qh_merge_degenredundant merge degenerate and redundant facets
• qh_merge_nonconvex merge a non-convex ridge
• qh_merge_twisted merge a twisted ridge with a convex and a concave opposite vertex
• 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_check_dupridge check dupridge between facet1 and facet2 for wide merge
• qh_checkdelfacet check that facet is not referenced by a mergeset
• qh_compare_anglemerge used by qsort() to order merges by type and angle
• qh_compare_facetmerge used by qsort() to order merges by type and distance
• qh_degen_redundant_facet check for a degenerate or redundant facet
• qh_degen_redundant_neighbors append degenerate and redundant neighbors to qh.degen_mergeset
• qh_detmaxoutside determine qh.MAXoutside target for qh_RATIO... tests
• qh_getmergeset_initial build initial qh.facet_mergeset
• qh_getmergeset update qh.facet_mergeset
• qh_hasmerge True if mergeset has mergetype for facetA and facetB
• qh_mark_dupridges add dupridges to qh.facet_mergeset
• qh_maybe_convexvertex maybe convex vertex for newly merged facet1/vertex1 and facet2
• qh_maybe_duplicateridge if a neighboring facet has another ridge with the same vertices, merge the closest pair of vertices
• qh_maybe_duplicateridges if a merged facet has two ridges with the same vertices, merge the closest pair of vertices
• qh_maydropneighbor drop neighbor relationship if no ridge between facet and neighbor
• qh_matchdupridge match dupridges in hash table
• qh_merge_dupridges identify dupridges for merging
• qh_next_facetmerge return next facet merge from qh.facet_mergeset
• qh_next_vertexmerge return next vertex merge from qh.vertex_mergeset
• qh_test_appendmerge test a pair of facets for convexity and append to qh.facet_mergeset if non-convex
• qh_test_centrum_merge test centrum convexity and append non-convex facets to qh.facet_mergeset
• qh_test_degen_neighbors append degenerate neighbors to qh.degen_mergeset
• qh_test_nonsimplicial_merge test centrum and vertex convexity and append non-convex or redundant facets to qh.facet_mergeset
• qh_test_redundant_neighbors append degenerate facet or its redundant neighbors to qh.degen_mergeset
• 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)
• qh_opposite_horizonfacet return horizon facet and opposite vertex for merge

»functions for merging facets

• qh_checkdelridge check that qh_delridge_merge is not needed
• qh_coplanarhorizon_merge merge new facets separated by a coplanar horizon facet
• qh_coplanarhorizon_merges merge new facets separated by coplanar horizon facets
• qh_copynonconvex copy non-convex flag to another ridge for the same neighbor
• qh_delridge_merge delete ridge and associated references, set vertex.delridge
• qh_drop_mergevertex clear mergevertex flags for ridges in a facet of a vertex merge
• qh_freemergesets free mergesets
• qh_initmergesets initialize mergesets
• 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 pinched vertices of dupridges

• qh_findbest_pinchedvertex find the best vertex to merge for a dupridge in qh.newfacet_list
• qh_get_maybepinched_vertices return neighboring horizon vertices of a vertex in a dupridge
• qh_getpinchedmerges return qh.vertex_mergeset for pinched vertices that cannot be facet merged
• qh_merge_pinchedvertices merge pinched vertices in qh.vertex_mergeset to avoid qh_forcedmerges of dupridges
• qh_neighbor_vertices return neighboring vertices for a vertex
• qh_neighbor_vertices_facet return neighboring vertices for a vertex in a facet

»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 (local)
Up: Qhull manual: contents
Up: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions (local)
Up: Qhull code
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