global.c

Quick hull implementation

  if (!qh KEEPcoplanar && !qh KEEPinside && !qh ONLYgood) {
    if ((qh PRINTcoplanar && qh PRINTspheres) || printcoplanar) {
      qh KEEPcoplanar = True;
      qh_option ("Qcoplanar", NULL, NULL);
    }
  }
  if (printmath && (qh hull_dim > 3 || qh VORONOI)) {
    fprintf (qh ferr, "qhull input error: Mathematica and Maple output is only available for 2-d and 3-d convex hulls and 2-d Delaunay triangulations\n");
    qh_errexit (qh_ERRinput, NULL, NULL);
  }
  if (printgeom) {
    if (qh hull_dim > 4) {
      fprintf (qh ferr, "qhull input error: Geomview output is only available for 2-d, 3-d and 4-d\n");
      qh_errexit (qh_ERRinput, NULL, NULL);
    }
    if (qh PRINTnoplanes && !(qh PRINTcoplanar + qh PRINTcentrums
     + qh PRINTdots + qh PRINTspheres + qh DOintersections + qh PRINTridges)) {
      fprintf (qh ferr, "qhull input error: no output specified for Geomview\n");
      qh_errexit (qh_ERRinput, NULL, NULL);
    }
    if (qh VORONOI && (qh hull_dim > 3 || qh DROPdim >= 0)) {
      fprintf (qh ferr, "qhull input error: Geomview output for Voronoi diagrams only for 2-d\n");
      qh_errexit (qh_ERRinput, NULL, NULL);
    }
    /* can not warn about furthest-site Geomview output: no lower_threshold */
    if (qh hull_dim == 4 && qh DROPdim == -1 &&
	(qh PRINTcoplanar || qh PRINTspheres || qh PRINTcentrums)) {
      fprintf (qh ferr, "qhull input warning: coplanars, vertices, and centrums output not\n\
available for 4-d output (ignored).  Could use 'GDn' instead.\n");
      qh PRINTcoplanar= qh PRINTspheres= qh PRINTcentrums= False;
    }
  }
  qh PRINTdim= qh hull_dim;
  if (qh DROPdim >=0) {    /* after Geomview checks */
    if (qh DROPdim < qh hull_dim) {
      qh PRINTdim--;
      if (!printgeom || qh hull_dim < 3)
        fprintf (qh ferr, "qhull input warning: drop dimension 'GD%d' is only available for 3-d/4-d Geomview\n", qh DROPdim);
    }else
      qh DROPdim= -1;
  }else if (qh VORONOI) {
    qh DROPdim= qh hull_dim-1;
    qh PRINTdim= qh hull_dim-1;
  }
} /* initqhull_globals */
 
/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="initqhull_mem">-</a>

  qh_initqhull_mem(  )
    initialize mem.c for qhull
    qh.hull_dim and qh.normal_size determine some of the allocation sizes
    if qh.MERGING,
      includes ridgeT
    calls qh_user_memsizes() to add up to 10 additional sizes for quick allocation
      (see numsizes below)

  returns:
    mem.c already for qh_memalloc/qh_memfree (errors if called beforehand)

  notes:
    qh_produceoutput() prints memsizes

*/
void qh_initqhull_mem (void) {
  int numsizes;
  int i;

  numsizes= 8+10;
  qh_meminitbuffers (qh IStracing, qh_MEMalign, numsizes,
                     qh_MEMbufsize,qh_MEMinitbuf);
  qh_memsize(sizeof(vertexT));
  if (qh MERGING) {
    qh_memsize(sizeof(ridgeT));
    qh_memsize(sizeof(mergeT));
  }
  qh_memsize(sizeof(facetT));
  i= sizeof(setT) + (qh hull_dim - 1) * SETelemsize;  /* ridge.vertices */
  qh_memsize(i);
  qh_memsize(qh normal_size);        /* normal */
  i += SETelemsize;                 /* facet.vertices, .ridges, .neighbors */
  qh_memsize(i);
  qh_user_memsizes();
  qh_memsetup();
} /* initqhull_mem */

/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="initqhull_start">-</a>

  qh_initqhull_start( infile, outfile, errfile )
    start initialization of qhull
    initialize statistics, stdio, default values for global variables

  see:
    qh_maxmin() determines the precision constants
*/
void qh_initqhull_start (FILE *infile, FILE *outfile, FILE *errfile) {

  qh_CPUclock; /* start the clock */
#if qh_QHpointer
  if (!(qh_qh= (qhT *)malloc (sizeof(qhT)))) {
    fprintf (errfile, "qhull error (qh_initqhull_globals): insufficient memory\n");
    exit (qh_ERRmem);  /* no error handler */
  }
  memset((char *)qh_qh, 0, sizeof(qhT));   /* every field is 0, FALSE, NULL */
#else
  memset((char *)&qh_qh, 0, sizeof(qhT));
#endif
  strcat (qh qhull, "qhull");
  qh_initstatistics();
  qh ANGLEmerge= True;
  qh DROPdim= -1;
  qh ferr= errfile;
  qh fin= infile;
  qh fout= outfile;
  qh furthest_id= -1;
  qh JOGGLEmax= REALmax;
  qh KEEPminArea = REALmax;
  qh last_low= REALmax;
  qh last_high= REALmax;
  qh last_newhigh= REALmax;
  qh max_outside= 0.0;
  qh max_vertex= 0.0;
  qh MAXabs_coord= 0.0;
  qh MAXsumcoord= 0.0;
  qh MAXwidth= -REALmax;
  qh MERGEindependent= True;
  qh MINdenom_1= fmax_(1.0/REALmax, REALmin); /* used by qh_scalepoints */
  qh MINoutside= 0.0;
  qh MINvisible= REALmax;
  qh MAXcoplanar= REALmax;
  qh outside_err= REALmax;
  qh premerge_centrum= 0.0;
  qh premerge_cos= REALmax;
  qh PRINTprecision= True;
  qh PRINTradius= 0.0;
  qh postmerge_cos= REALmax;
  qh postmerge_centrum= 0.0;
  qh ROTATErandom= INT_MIN;
  qh MERGEvertices= True;
  qh totarea= 0.0;
  qh totvol= 0.0;
  qh TRACEdist= REALmax;
  qh TRACEpoint= -1; /* recompile or use 'TPn' */
  qh tracefacet_id= UINT_MAX;  /* recompile to trace a facet */
  qh tracevertex_id= UINT_MAX; /* recompile to trace a vertex */
  qh_RANDOMseed_(1);
} /* initqhull_start */

/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="initthresholds">-</a>

  qh_initthresholds( commandString )
    set thresholds for printing and scaling from commandString

  returns:
    sets qh.GOODthreshold or qh.SPLITthreshold if 'Pd0D1' used

  see:
    qh_initflags(), 'Qbk' 'QBk' 'Pdk' and 'PDk'
    qh_inthresholds()

  design:
    for each 'Pdn' or 'PDn' option
      check syntax
      set qh.lower_threshold or qh.upper_threshold
    set qh.GOODthreshold if an unbounded threshold is used
    set qh.SPLITthreshold if a bounded threshold is used
*/
void qh_initthresholds(char *command) {
  realT value;
  int index, maxdim, k;
  char *s= command;
  char key;

  maxdim= qh input_dim;
  if (qh DELAUNAY && (qh PROJECTdelaunay || qh PROJECTinput))
    maxdim++;
  while (*s) {
    if (*s == '-')
      s++;
    if (*s == 'P') {
      s++;
      while (*s && !isspace(key= *s++)) {
	if (key == 'd' || key == 'D') {
	  if (!isdigit(*s)) {
	    fprintf(qh ferr, "qhull warning: no dimension given for Print option '%c' at: %s.  Ignored\n",
		    key, s-1);
	    continue;
	  }
	  index= qh_strtol (s, &s);
	  if (index >= qh hull_dim) {
	    fprintf(qh ferr, "qhull warning: dimension %d for Print option '%c' is >= %d.  Ignored\n",
	        index, key, qh hull_dim);
	    continue;
	  }
	  if (*s == ':') {
	    s++;
	    value= qh_strtod(s, &s);
	    if (fabs((double)value) > 1.0) {
	      fprintf(qh ferr, "qhull warning: value %2.4g for Print option %c is > +1 or < -1.  Ignored\n",
	              value, key);
	      continue;
	    }
	  }else
	    value= 0.0;
	  if (key == 'd')
	    qh lower_threshold[index]= value;
	  else
	    qh upper_threshold[index]= value;
	}
      }
    }else if (*s == 'Q') {
      s++;
      while (*s && !isspace(key= *s++)) {
	if (key == 'b' && *s == 'B') {
	  s++;
	  for (k=maxdim; k--; ) {
	    qh lower_bound[k]= -qh_DEFAULTbox;
	    qh upper_bound[k]= qh_DEFAULTbox;
	  }
	}else if (key == 'b' && *s == 'b')
	  s++;
	else if (key == 'b' || key == 'B') {
	  if (!isdigit(*s)) {
	    fprintf(qh ferr, "qhull warning: no dimension given for Qhull option %c.  Ignored\n",
		    key);
	    continue;
	  }
	  index= qh_strtol (s, &s);
	  if (index >= maxdim) {
	    fprintf(qh ferr, "qhull warning: dimension %d for Qhull option %c is >= %d.  Ignored\n",
	        index, key, maxdim);
	    continue;
	  }
	  if (*s == ':') {
	    s++;
	    value= qh_strtod(s, &s);
	  }else if (key == 'b')
	    value= -qh_DEFAULTbox;
	  else
	    value= qh_DEFAULTbox;
	  if (key == 'b')
	    qh lower_bound[index]= value;
	  else
	    qh upper_bound[index]= value;
	}
      }
    }else {
      while (*s && !isspace (*s))
        s++;
    }
    while (isspace (*s))
      s++;
  }
  for (k= qh hull_dim; k--; ) {
    if (qh lower_threshold[k] > -REALmax/2) {
      qh GOODthreshold= True;
      if (qh upper_threshold[k] < REALmax/2) {
        qh SPLITthresholds= True;
        qh GOODthreshold= False;
        break;
      }
    }else if (qh upper_threshold[k] < REALmax/2)
      qh GOODthreshold= True;
  }
} /* initthresholds */

/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="option">-</a>

  qh_option( option, intVal, realVal )
    add an option description to qh.qhull_options

  notes:
    will be printed with statistics ('Ts') and errors
    strlen(option) < 40
*/
void qh_option (char *option, int *i, realT *r) {
  char buf[200];
  int len, maxlen;

  sprintf (buf, "  %s", option);
  if (i)
    sprintf (buf+strlen(buf), " %d", *i);
  if (r)
    sprintf (buf+strlen(buf), " %2.2g", *r);
  len= strlen(buf);
  qh qhull_optionlen += len;
  maxlen= sizeof (qh qhull_options) - len -1;
  maximize_(maxlen, 0);
  if (qh qhull_optionlen >= 80 && maxlen > 0) {
    qh qhull_optionlen= len;
    strncat (qh qhull_options, "\n", maxlen--);
  }
  strncat (qh qhull_options, buf, maxlen);
} /* option */

#if qh_QHpointer
/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="restore_qhull">-</a>

  qh_restore_qhull( oldqh )
    restores a previously saved qhull
    also restores qh_qhstat and qhmem.tempstack

  notes:
    errors if current qhull hasn't been saved or freed
    uses qhmem for error reporting

  NOTE 1998/5/11:
    Freeing memory after qh_save_qhull and qh_restore_qhull
    is complicated.  The procedures will be redesigned.

  see:
    qh_save_qhull()
*/
void qh_restore_qhull (qhT **oldqh) {

  if (*oldqh && strcmp ((*oldqh)->qhull, "qhull")) {
    fprintf (qhmem.ferr, "qhull internal error (qh_restore_qhull): %p is not a qhull data structure\n",
                  *oldqh);
    qh_errexit (qh_ERRqhull, NULL, NULL);
  }
  if (qh_qh) {
    fprintf (qhmem.ferr, "qhull internal error (qh_restore_qhull): did not save or free existing qhull\n");
    qh_errexit (qh_ERRqhull, NULL, NULL);
  }
  if (!*oldqh || !(*oldqh)->old_qhstat) {
    fprintf (qhmem.ferr, "qhull internal error (qh_restore_qhull): did not previously save qhull %p\n",
                  *oldqh);
    qh_errexit (qh_ERRqhull, NULL, NULL);
  }
  qh_qh= *oldqh;
  *oldqh= NULL;
  qh_qhstat= qh old_qhstat;
  qhmem.tempstack= qh old_tempstack;
  trace1((qh ferr, "qh_restore_qhull: restored qhull from %p\n", *oldqh));
} /* restore_qhull */

/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="save_qhull">-</a>

  qh_save_qhull(  )
    saves qhull for a later qh_restore_qhull
    also saves qh_qhstat and qhmem.tempstack

  returns:
    qh_qh=NULL

  notes:
    need to initialize qhull or call qh_restore_qhull before continuing

  NOTE 1998/5/11:
    Freeing memory after qh_save_qhull and qh_restore_qhull
    is complicated.  The procedures will be redesigned.

  see:
    qh_restore_qhull()
*/
qhT *qh_save_qhull (void) {
  qhT *oldqh;

  trace1((qhmem.ferr, "qh_save_qhull: save qhull %p\n", qh_qh));
  if (!qh_qh) {
    fprintf (qhmem.ferr, "qhull internal error (qh_save_qhull): qhull not initialized\n");
    qh_errexit (qh_ERRqhull, NULL, NULL);
  }
  qh old_qhstat= qh_qhstat;
  qh_qhstat= NULL;
  qh old_tempstack= qhmem.tempstack;
  qhmem.tempstack= NULL;
  oldqh= qh_qh;
  qh_qh= NULL;
  return oldqh;
} /* save_qhull */

#endif

/*-<a                             href="qh-globa.htm#TOC"
  >-------------------------------</a><a name="strtol">-</a>

  qh_strtol( s, endp) qh_strtod( s, endp)
    internal versions of strtol() and strtod()
    does not skip trailing spaces
  notes:
    some implementations of strtol()/strtod() skip trailing spaces
*/
double qh_strtod (const char *s, char **endp) {
  double result;

  result= strtod (s, endp);
  if (s < (*endp) && (*endp)[-1] == ' ')
    (*endp)--;
  return result;
} /* strtod */

int qh_strtol (const char *s, char **endp) {
  int result;

  result= (int) strtol (s, endp, 10);
  if (s< (*endp) && (*endp)[-1] == ' ')
    (*endp)--;
  return result;
} /* strtol */