user.h

DT三角化实现

#define qh_MEMinitbuf 0x20000      /* initially allocate 128K buffer */

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="INFINITE">-</a>
  
  qh_INFINITE
    on output, indicates Voronoi center at infinity
*/
#define qh_INFINITE  -10.101

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="DEFAULTbox">-</a>
  
  qh_DEFAULTbox
    default box size (Geomview expects 0.5)
*/
#define qh_DEFAULTbox 0.5 

/*======= conditional compilation ============================*/

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="compiler">-</a>

  __cplusplus
    defined by C++ compilers

  __MSC_VER
    defined by Microsoft Visual C++
  
  __MWERKS__ && __POWERPC__
    defined by Metrowerks when compiling for the Power Macintosh

  __STDC__
    defined for strict ANSI C 
*/

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="COMPUTEfurthest">-</a>
 
  qh_COMPUTEfurthest 
    compute furthest distance to an outside point instead of storing it with the facet
    =1 to compute furthest
  
  notes:
    computing furthest saves memory but costs time
      about 40% more distance tests for partitioning
      removes facet->furthestdist 
*/
#define qh_COMPUTEfurthest 0
                         
/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="KEEPstatistics">-</a>
 
  qh_KEEPstatistics   
    =0 removes most of statistic gathering and reporting

  notes:
    if 0, code size is reduced by about 4%.
*/
#define qh_KEEPstatistics 1
                       
/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="MAXoutside">-</a>
 
  qh_MAXoutside 
    record outer plane for each facet
    =1 to record facet->maxoutside
  
  notes:
    this takes a realT per facet and slightly slows down qhull
    it produces better outer planes for geomview output 
*/
#define qh_MAXoutside 1

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="NOmerge">-</a>
 
  qh_NOmerge
    disables facet merging if defined
    
  notes:
    This saves about 10% space.
    
    Unless 'Q0'
      qh_NOmerge sets 'QJ' to avoid precision errors

    #define qh_NOmerge    

  see:
    <a href="mem.h#NOmem">qh_NOmem</a> in mem.c
    
    see user.c/user_eg.c for removing io.o
*/  
    
/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="NOtrace">-</a>
 
  qh_NOtrace
    no tracing if defined 
  
  notes:
    This saves about 5% space.

    #define qh_NOtrace
*/    

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="QHpointer">-</a>
  
  qh_QHpointer
    access global data with pointer or static structure

  qh_QHpointer  = 1     access globals via a pointer to allocated memory
                        enables qh_saveqhull() and qh_restoreqhull()
			costs about 8% in time and 2% in space

		= 0     qh_qh and qh_qhstat are static data structures
		        only one instance of qhull() can be active at a time
			default value

  notes:
    all global variables for qhull are in qh, qhmem, and qhstat
    qh is defined in qhull.h
    qhmem is defined in mem.h
    qhstat is defined in stat.h

  see:
    user_eg.c for an example
*/
#define qh_QHpointer 0
#if 0  /* sample code */
    qhT *oldqhA, *oldqhB;

    exitcode= qh_new_qhull (dim, numpoints, points, ismalloc,
                      flags, outfile, errfile); 
    /* use results from first call to qh_new_qhull */
    oldqhA= qh_save_qhull();
    exitcode= qh_new_qhull (dimB, numpointsB, pointsB, ismalloc,
                      flags, outfile, errfile); 
    /* use results from second call to qh_new_qhull */
    oldqhB= qh_save_qhull();
    qh_restore_qhull (&oldqhA);
    /* use results from first call to qh_new_qhull */
    qh_freeqhull (qh_ALL);  /* frees all memory used by first call */
    qh_restore_qhull (&oldqhB);
    /* use results from second call to qh_new_qhull */
    qh_freeqhull (!qh_ALL); /* frees long memory used by second call */
    qh_memfreeshort (&curlong, &totlong);  /* frees short memory and memory allocator */
#endif

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="QUICKhelp">-</a>
 
  qh_QUICKhelp        
    =1 to use abbreviated help messages, e.g., for degenerate inputs
*/
#define qh_QUICKhelp    0  

/* ============ -merge constants- ====================

   These constants effect facet merging.  You probably will not need
   to modify these.  They effect the performance of facet merging.
*/

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="DIMmergeVertex">-</a>
  
  qh_DIMmergeVertex
    max dimension for vertex merging (it is not effective in high-d)
*/
#define qh_DIMmergeVertex 6

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="DIMreduceBuild">-</a>
  
  qh_DIMreduceBuild
     max dimension for vertex reduction during build (slow in high-d)
*/
#define qh_DIMreduceBuild 5

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="BESTcentrum">-</a>
     
  qh_BESTcentrum
     if > 2*dim+n vertices, qh_findbestneighbor() tests centrums (faster)
     else, qh_findbestneighbor() tests all vertices (much better merges)

  qh_BESTcentrum2
     if qh_BESTcentrum2 * DIM3 + BESTcentrum < #vertices tests centrums
*/
#define qh_BESTcentrum 20
#define qh_BESTcentrum2 2

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="BESTnonconvex">-</a>
  
  qh_BESTnonconvex
    if > dim+n neighbors, qh_findbestneighbor() tests nonconvex ridges.
    
  notes:
    It is needed because qh_findbestneighbor is slow for large facets
*/
#define qh_BESTnonconvex 15 

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="MAXnewmerges">-</a>
  
  qh_MAXnewmerges
    if >n newmerges, qh_merge_nonconvex() calls qh_reducevertices_centrums.
     
  notes:
    It is needed because postmerge can merge many facets at once
*/
#define qh_MAXnewmerges 2

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="MAXnewcentrum">-</a>
  
  qh_MAXnewcentrum
    if <= dim+n vertices (n approximates the number of merges),
      reset the centrum in qh_updatetested() and qh_mergecycle_facets()
    
  notes:
    needed to reduce cost and because centrums may move too much if 
    many vertices in high-d
*/
#define qh_MAXnewcentrum 5

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="COPLANARratio">-</a>
  
  qh_COPLANARratio
    for 3-d+ merging, qh.MINvisible is n*premerge_centrum

  notes:
    for non-merging, it's DISTround
*/
#define qh_COPLANARratio 3

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="DISToutside">-</a>
  
  qh_DISToutside
    When is a point clearly outside of a facet?  
    Stops search in qh_findbestnew or qh_partitionall
    qh_findbest uses qh.MINoutside since since it is only called if no merges.
     
  notes:
    'Qf' always searches for best facet
    if !qh.MERGING, same as qh.MINoutside. 
    if qh_USEfindbestnew, increase value since neighboring facets may be ill-behaved
      [Note: Zdelvertextot occurs normally with interior points]
            RBOX 1000 s Z1 G1e-13 t1001188774 | QHULL Tv
    When there is a sharp edge, need to move points to a
    clearly good facet; otherwise may be lost in another partitioning.
    if too big then O(n^2) behavior for partitioning in cone
    if very small then important points not processed
    Needed in qh_partitionall for
      RBOX 1000 s Z1 G1e-13 t1001032651 | QHULL Tv
    Needed in qh_findbestnew for many instances of
      RBOX 1000 s Z1 G1e-13 t | QHULL Tv

  See:  
    qh_DISToutside -- when is a point clearly outside of a facet
    qh_SEARCHdist -- when is facet coplanar with the best facet?
    qh_USEfindbestnew -- when to use qh_findbestnew for qh_partitionpoint()
*/
#define qh_DISToutside ((qh_USEfindbestnew ? 2 : 1) * \
     fmax_((qh MERGING ? 2 : 1)*qh MINoutside, qh max_outside))

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="RATIOnearinside">-</a>
  
  qh_RATIOnearinside
    ratio of qh.NEARinside to qh.ONEmerge for retaining inside points for
    qh_check_maxout().  
  
  notes:
    This is overkill since do not know the correct value.
    It effects whether 'Qc' reports all coplanar points
    Not used for 'd' since non-extreme points are coplanar
*/
#define qh_RATIOnearinside 5

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="SEARCHdist">-</a>
  
  qh_SEARCHdist
    When is a facet coplanar with the best facet?  
    qh_findbesthorizon: all coplanar facets of the best facet need to be searched.

  See:
    qh_DISToutside -- when is a point clearly outside of a facet
    qh_SEARCHdist -- when is facet coplanar with the best facet?
    qh_USEfindbestnew -- when to use qh_findbestnew for qh_partitionpoint()
*/
#define qh_SEARCHdist ((qh_USEfindbestnew ? 2 : 1) * \
      (qh max_outside + 2 * qh DISTround + fmax_( qh MINvisible, qh MAXcoplanar)));

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="USEfindbestnew">-</a>
  
  qh_USEfindbestnew
     Always use qh_findbestnew for qh_partitionpoint, otherwise use
     qh_findbestnew if merged new facet or sharpnewfacets.
  
  See:
    qh_DISToutside -- when is a point clearly outside of a facet
    qh_SEARCHdist -- when is facet coplanar with the best facet?
    qh_USEfindbestnew -- when to use qh_findbestnew for qh_partitionpoint()
*/
#define qh_USEfindbestnew (zzval_(Ztotmerge) > 50)

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="WIDEcoplanar">-</a>
  
  qh_WIDEcoplanar
    n*MAXcoplanar or n*MINvisible for a WIDEfacet 
    
    if vertex is further than qh.WIDEfacet from the hyperplane
    then its ridges are not counted in computing the area, and
    the facet's centrum is frozen. 
    
  notes:
   qh.WIDEfacet= max(qh.MAXoutside,qh_WIDEcoplanar*qh.MAXcoplanar,
      qh_WIDEcoplanar * qh.MINvisible);
*/
#define qh_WIDEcoplanar 6

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="MAXnarrow">-</a>
  
  qh_MAXnarrow
    max. cosine in initial hull that sets qh.NARROWhull
       
  notes:
    If qh.NARROWhull, the initial partition does not make 
    coplanar points.  If narrow, a coplanar point can be 
    coplanar to two facets of opposite orientations and
    distant from the exact convex hull.

    Conservative estimate.  Don't actually see problems until it is -1.0
*/
#define qh_MAXnarrow -0.99999999

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="WARNnarrow">-</a>
  
  qh_WARNnarrow
    max. cosine in initial hull to warn about qh.NARROWhull
      
  notes:
    this is a conservative estimate.  
    Don't actually see problems until it is -1.0.  See qh-impre.htm
*/
#define qh_WARNnarrow -0.999999999999999

/*-<a                             href="qh-user.htm#TOC"
  >--------------------------------</a><a name="ZEROdelaunay">-</a>
  
  qh_ZEROdelaunay
    a zero Delaunay facet occurs for input sites coplanar with their convex hull
    the last normal coefficient of a zero Delaunay facet is within
        qh_ZEROdelaunay * qh.ANGLEround of 0
      
  notes:
    qh_ZEROdelaunay does not allow for joggled input ('QJ').

    You can avoid zero Delaunay facets by surrounding the input with a box.

    Use option 'PDk:-n' to explicitly define zero Delaunay facets
      k= dimension of input sites (e.g., 3 for 3-d Delaunay triangulation)
      n= the cutoff for zero Delaunay facets (e.g., 'PD3:-1e-12')
*/
#define qh_ZEROdelaunay 2

#endif /* qh_DEFuser */