📄 qhull.h
字号:
/*<html><pre> -<a href="qh-c.htm#qhull"
>-------------------------------</a><a name="TOP">-</a>
qhull.h
user-level header file for using qhull.a library
see qh-c.htm, qhull_a.h
copyright (c) 1993-1999, The Geometry Center
defines qh_qh, global data structure for qhull.
NOTE: access to qh_qh is via the 'qh' macro. This allows
qh_qh to be either a pointer or a structure. An example
of using qh is "qh DROPdim" which accesses the DROPdim
field of qh_qh. Similarly, access to qh_qhstat is via
the 'qhstat' macro.
includes function prototypes for qhull.c, geom.c, global.c, io.c, user.c
use mem.h for mem.c
use qset.h for qset.c
see unix.c for an example of using qhull.h
recompile qhull if you change this file
*/
#ifndef qhDEFqhull
#define qhDEFqhull 1
/*=========================== -included files ==============*/
#include <setjmp.h>
#include <float.h>
#include <time.h>
#if __MWERKS__ && __POWERPC__
#include <SIOUX.h>
#include <Files.h>
#include <Desk.h>
#endif
#ifndef __STDC__
#ifndef __cplusplus
#if !_MSC_VER
#error Neither __STDC__ nor __cplusplus is defined. Please use strict ANSI C or C++ to compile
#error Qhull. You may need to turn off compiler extensions in your project configuration. If
#error your compiler is a standard C compiler, you can delete this warning from qhull.h
#endif
#endif
#endif
#include "user.h" /* user defineable constants */
/*============ constants and basic types ====================*/
/*-<a href="qh-c.htm#geom"
>--------------------------------</a><a name="coordT">-</a>
coordT
coordinates and coefficients are stored as realT (i.e., double)
notes:
could use 'float' for data and 'double' for calculations (realT vs. coordT)
This requires many type casts, and adjusted error bounds.
Also C compilers may do expressions in double anyway.
*/
#define coordT realT
/*-<a href="qh-c.htm#geom"
>--------------------------------</a><a name="pointT">-</a>
pointT
a point is an array of DIM3 coordinates
*/
#define pointT coordT
/*-<a href="qh-c.htm#qhull"
>--------------------------------</a><a name="flagT">-</a>
flagT
Boolean flag as a bit
*/
#define flagT unsigned int
/*-<a href="qh-c.htm#qhull"
>--------------------------------</a><a name="boolT">-</a>
boolT
boolean value, either True or False
notes:
needed for portability
*/
#define boolT unsigned int
#ifdef False
#undef False
#endif
#ifdef True
#undef True
#endif
#define False 0
#define True 1
/*-<a href="qh-c.htm#qhull"
>--------------------------------</a><a name="CENTERtype">-</a>
qh_CENTER
to distinguish facet->center
*/
typedef enum
{
qh_ASnone = 0, qh_ASvoronoi, qh_AScentrum
}
qh_CENTER;
/*-<a href="qh-c.htm#qhull"
>--------------------------------</a><a name="qh_PRINT">-</a>
qh_PRINT
output formats for printing (qh.PRINTout).
notes:
some of these names are similar to qh names. The similar names are only
used in switch statements in qh_printbegin() etc.
*/
typedef enum {qh_PRINTnone= 0, qh_PRINTarea, qh_PRINTaverage,
qh_PRINTcoplanars, qh_PRINTcentrums,
qh_PRINTfacets, qh_PRINTfacets_xridge,
qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors,
qh_PRINTnormals, qh_PRINTouter, qh_PRINTincidences,
qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff,
qh_PRINToptions, qh_PRINTpointintersect, qh_PRINTpointnearest,
qh_PRINTpoints, qh_PRINTqhull, qh_PRINTsize, qh_PRINTsummary,
qh_PRINTtriangles, qh_PRINTvertices, qh_PRINTvneighbors, qh_PRINTextremes,
qh_PRINTEND} qh_PRINT;
/*-<a href="qh-c.htm#qhull"
>--------------------------------</a><a name="qh_ALL">-</a>
qh_ALL
argument flag for selecting everything
*/
#define qh_ALL True
#define qh_NOupper True /* argument for qh_findbest */
/*-<a href="qh-c.htm#qhull"
>--------------------------------</a><a name="qh_ERR">-</a>
qh_ERR
Qhull exit codes, for indicating errors
*/
#define qh_ERRnone 0 /* no error occurred during qhull */
#define qh_ERRinput 1 /* input inconsistency */
#define qh_ERRsingular 2 /* singular input data */
#define qh_ERRprec 3 /* precision error */
#define qh_ERRmem 4 /* insufficient memory, matches mem.h */
#define qh_ERRqhull 5 /* internal error detected, matches mem.h */
/* ============ -structures- ====================
each of the following structures is defined by a typedef
all realT and coordT fields occur at the beginning of a structure
(otherwise space may be wasted due to alignment)
define all flags together and pack into 32-bit number
*/
typedef struct vertexT vertexT;
typedef struct ridgeT ridgeT;
typedef struct facetT facetT;
#ifndef DEFsetT
#define DEFsetT 1
typedef struct setT setT; /* defined in qset.h */
#endif
/*-<a href="qh-c.htm#poly"
>--------------------------------</a><a name="facetT">-</a>
facetT
defines a facet
notes:
qhull() generates the hull as a list of facets.
topological information:
f.previous,next doubly-linked list of facets
f.vertices set of vertices
f.ridges set of ridges
f.neighbors set of neighbors
f.toporient True if facet has top-orientation (else bottom)
geometric information:
f.offset,normal hyperplane equation
f.maxoutside offset to outer plane -- all points inside
f.center centrum for testing convexity
f.simplicial True if facet is simplicial
f.flipped True if facet does not include qh.interior_point
for constructing hull:
f.visible True if facet on list of visible facets (will be deleted)
f.newfacet True if facet on list of newly created facets
f.coplanarset set of points coplanar with this facet
(includes near-inside points for later testing)
f.outsideset set of points outside of this facet
f.furthestdist distance to furthest point of outside set
f.visitid marks visited facets during a loop
f.replace replacement facet for to-be-deleted, visible facets
f.samecycle,newcycle cycle of facets for merging into horizon facet
see below for other flags and fields
*/
struct facetT {
#if !qh_COMPUTEfurthest
coordT furthestdist;/* distance to furthest point of outsideset */
#endif
#if qh_MAXoutside
coordT maxoutside; /* max computed distance of point to facet
Before QHULLfinished this is an approximation
since maxdist not always set for mergefacet
Actual outer plane is +DISTround and
computed outer plane is +2*DISTround */
#endif
coordT offset; /* exact offset of hyperplane from origin */
coordT *normal; /* normal of hyperplane, hull_dim coefficients */
union { /* in order of testing */
realT area; /* area of facet, only in io.c if ->isarea */
facetT *replace; /* replacement facet if ->visible and NEWfacets
is NULL only if qh_mergedegen_redundant or interior */
facetT *samecycle; /* cycle of facets from the same visible/horizon intersection,
if ->newfacet */
facetT *newcycle; /* in horizon facet, current samecycle of new facets */
}f;
coordT *center; /* centrum for convexity, qh CENTERtype == qh_AScentrum */
/* Voronoi center, qh CENTERtype == qh_ASvoronoi */
facetT *previous; /* previous facet in the facet_list */
facetT *next; /* next facet in the facet_list */
setT *vertices; /* vertices for this facet, inverse sorted by id
if simplicial, 1st vertex was apex/furthest */
setT *ridges; /* explicit ridges for nonsimplicial facets.
for simplicial facets, neighbors defines ridge */
setT *neighbors; /* neighbors of the facet. If simplicial, the kth
neighbor is opposite the kth vertex, and the first
neighbor is the horizon facet for the first vertex*/
setT *outsideset; /* set of points outside this facet
if non-empty, last point is furthest
if NARROWhull, includes coplanars for partitioning*/
setT *coplanarset; /* set of points coplanar with this facet
> qh.min_vertex and <= facet->max_outside
a point is assigned to the furthest facet
if non-empty, last point is furthest away */
unsigned visitid; /* visit_id, for visiting all neighbors,
all uses are independent */
unsigned id; /* unique identifier from qh facet_id */
unsigned nummerge:9; /* number of merges */
#define qh_MAXnummerge 511 /* 2^9-1 */
flagT newfacet:1; /* True if facet on qh newfacet_list (new or merged) */
flagT visible:1; /* True if visible facet (will be deleted) */
flagT toporient:1; /* True if created with top orientation
after merging, use ridge orientation */
flagT simplicial:1;/* True if simplicial facet, ->ridges may be implicit */
flagT seen:1; /* used to perform operations only once, like visitid */
flagT seen2:1; /* used to perform operations only once, like visitid */
flagT flipped:1; /* True if facet is flipped */
flagT upperdelaunay:1; /* True if facet is upper envelope of Delaunay triangulation */
flagT notfurthest:1; /* True if last point of outsideset is not furthest*/
/*-------- flags primarily for output ---------*/
flagT good:1; /* True if a facet marked good for output */
flagT isarea:1; /* True if facet->f.area is defined */
/*-------- flags for merging ------------------*/
flagT dupridge:1; /* True if duplicate ridge in facet */
flagT mergeridge:1; /* True if facet or neighbor contains a qh_MERGEridge
->normal defined (also defined for mergeridge2) */
flagT mergeridge2:1; /* True if neighbor contains a qh_MERGEridge (mark_dupridges */
flagT coplanar:1; /* True if horizon facet is coplanar at last use */
flagT mergehorizon:1; /* True if will merge into horizon (->coplanar) */
flagT cycledone:1;/* True if mergecycle_all already done */
flagT tested:1; /* True if facet convexity has been tested (false after merge */
flagT keepcentrum:1; /* True if keep old centrum after a merge */
flagT newmerge:1; /* True if facet is newly merged for reducevertices */
flagT degenerate:1; /* True if facet is degenerate (degen_mergeset) */
flagT redundant:1; /* True if facet is redundant (degen_mergeset) */
};
/*-<a href="qh-c.htm#poly"
>--------------------------------</a><a name="ridgeT">-</a>
ridgeT
defines a ridge
notes:
a ridge is DIM3-1 simplex between two neighboring facets. If the
facets are non-simplicial, there may be more than one ridge between
two facets. E.G. a 4-d hypercube has two triangles between each pair
of neighboring facets.
topological information:
vertices a set of vertices
top,bottom neighboring facets with orientation
geometric information:
tested True if ridge is clearly convex
nonconvex True if ridge is non-convex
*/
struct ridgeT {
setT *vertices; /* vertices belonging to this ridge, inverse sorted by id
NULL if a degen ridge (matchsame) */
facetT *top; /* top facet this ridge is part of */
facetT *bottom; /* bottom facet this ridge is part of */
unsigned id:24; /* unique identifier, =>room for 8 flags */
flagT seen:1; /* used to perform operations only once */
flagT tested:1; /* True when ridge is tested for convexity */
flagT nonconvex:1; /* True if getmergeset detected a non-convex neighbor
only one ridge between neighbors may have nonconvex */
};
/*-<a href="qh-c.htm#poly"
>--------------------------------</a><a name="vertexT">-</a>
vertexT
defines a vertex
topological information:
next,previous doubly-linked list of all vertices
neighbors set of adjacent facets (only if qh.VERTEXneighbors)
geometric information:
point array of DIM3 coordinates
*/
struct vertexT {
vertexT *next; /* next vertex in vertex_list */
vertexT *previous; /* previous vertex in vertex_list */
pointT *point; /* hull_dim coordinates (coordT) */
setT *neighbors; /* neighboring facets of vertex, qh_vertexneighbors()
inits in io.c or after first merge */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -