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

## 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-2010 C.B. Barber

» 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 code: 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