global.c

Quick hull implementation

      points[0] is the first coordinate of the first point
      points[1] is the second coordinate of the first point
      points[dim] is the first coordinate of the second point

    ismalloc=True
      Qhull will call free(points) on exit or input transformation
    ismalloc=False
      Qhull will allocate a new point array if needed for input transformation

    qh.qhull_command
      is the option string.
      It is defined by qh_init_B(), qh_qhull_command(), or qh_initflags

  returns:
    if qh.PROJECTinput or (qh.DELAUNAY and qh.PROJECTdelaunay)
      projects the input to a new point array

        if qh.DELAUNAY,
          qh.hull_dim is increased by one
        if qh.ATinfinity,
          qh_projectinput adds point-at-infinity for Delaunay tri.

    if qh.SCALEinput
      changes the upper and lower bounds of the input, see qh_scaleinput()

    if qh.ROTATEinput
      rotates the input by a random rotation, see qh_rotateinput()
      if qh.DELAUNAY
        rotates about the last coordinate

  notes:
    called after points are defined
    qh_errexit() may be used
*/
void qh_init_B (coordT *points, int numpoints, int dim, boolT ismalloc) {
  qh_initqhull_globals (points, numpoints, dim, ismalloc);
  if (qhmem.LASTsize == 0)
    qh_initqhull_mem();
  /* mem.c and qset.c are initialized */
  qh_initqhull_buffers();
  qh_initthresholds (qh qhull_command);
  if (qh PROJECTinput || (qh DELAUNAY && qh PROJECTdelaunay))
    qh_projectinput();
  if (qh SCALEinput)
    qh_scaleinput();
  if (qh ROTATErandom >= 0) {
    qh_randommatrix (qh gm_matrix, qh hull_dim, qh gm_row);
    if (qh DELAUNAY) {
      int k, lastk= qh hull_dim-1;
      for (k= 0; k < lastk; k++) {
        qh gm_row[k][lastk]= 0.0;
        qh gm_row[lastk][k]= 0.0;
      }
      qh gm_row[lastk][lastk]= 1.0;
    }
    qh_gram_schmidt (qh hull_dim, qh gm_row);
    qh_rotateinput (qh gm_row);
  }
} /* init_B */

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

  qh_init_qhull_command( argc, argv )
    build qh.qhull_command from argc/argv

  returns:
    a space-deliminated string of options (just as typed)

  notes:
    makes option string easy to input and output

    argc/argv may be 0/NULL
*/
void qh_init_qhull_command(int argc, char *argv[]) {
  int i;
  char *s;

  if (argc) {
    if ((s= strrchr( argv[0], '\\'))) /* Borland gives full path */
      strcpy (qh qhull_command, s+1);
    else
      strcpy (qh qhull_command, argv[0]);
    if ((s= strstr (qh qhull_command, ".EXE"))
    ||  (s= strstr (qh qhull_command, ".exe")))
      *s= '\0';
  }
  for (i=1; i < argc; i++) {
    if (strlen (qh qhull_command) + strlen(argv[i]) + 1 < sizeof(qh qhull_command)) {
      strcat (qh qhull_command, " ");
      strcat (qh qhull_command, argv[i]);
    }else {
      fprintf (qh ferr, "qhull input error: more than %d characters in command line\n",
        (int)sizeof(qh qhull_command));
      exit (1);  /* can not use qh_errexit */
    }
  }
} /* init_qhull_command */

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

  qh_initflags( commandStr )
    set flags and initialized constants from commandStr

  returns:
    sets qh.qhull_command to command if needed

  notes:
    ignores first word (e.g., "qhull d")
    use qh_strtol/strtod since strtol/strtod may or may not skip trailing spaces

  see:
    qh_initthresholds() continues processing of 'Pdn' and 'PDn'
    'prompt' in unix.c for documentation

  design:
    for each space-deliminated option group
      if top-level option
        check syntax
        append approriate option to option string
        set appropriate global variable or append printFormat to print options
      else
        for each sub-option
          check syntax
          append approriate option to option string
          set appropriate global variable or append printFormat to print options


*/
void qh_initflags(char *command) {
  int k, i, lastproject;
  char *s= command, *t, *prev_s, *start, key;
  boolT isgeom= False, wasproject;
  realT r;

  if (command != &qh qhull_command[0]) {
    *qh qhull_command= '\0';
    strncat( qh qhull_command, command, sizeof( qh qhull_command));
  }
  while (*s && !isspace(*s))  /* skip program name */
    s++;
  while (*s) {
    while (*s && isspace(*s))
      s++;
    if (*s == '-')
      s++;
    if (!*s)
      break;
    prev_s= s;
    switch (*s++) {
    case 'd':
      qh_option ("delaunay", NULL, NULL);
      qh DELAUNAY= True;
      break;
    case 'f':
      qh_option ("facets", NULL, NULL);
      qh_appendprint (qh_PRINTfacets);
      break;
    case 'i':
      qh_option ("incidence", NULL, NULL);
      qh_appendprint (qh_PRINTincidences);
      break;
    case 'm':
      qh_option ("mathematica", NULL, NULL);
      qh_appendprint (qh_PRINTmathematica);
      break;
    case 'n':
      qh_option ("normals", NULL, NULL);
      qh_appendprint (qh_PRINTnormals);
      break;
    case 'o':
      qh_option ("offFile", NULL, NULL);
      qh_appendprint (qh_PRINToff);
      break;
    case 'p':
      qh_option ("points", NULL, NULL);
      qh_appendprint (qh_PRINTpoints);
      break;
    case 's':
      qh_option ("summary", NULL, NULL);
      qh PRINTsummary= True;
      break;
    case 'v':
      qh_option ("voronoi", NULL, NULL);
      qh VORONOI= True;
      qh DELAUNAY= True;
      break;
    case 'A':
      if (!isdigit(*s) && *s != '.' && *s != '-')
	fprintf(qh ferr, "qhull warning: no maximum cosine angle given for option 'An'.  Ignored.\n");
      else {
	if (*s == '-') {
	  qh premerge_cos= -qh_strtod (s, &s);
          qh_option ("Angle-premerge-", NULL, &qh premerge_cos);
	  qh PREmerge= True;
	}else {
	  qh postmerge_cos= qh_strtod (s, &s);
          qh_option ("Angle-postmerge", NULL, &qh postmerge_cos);
	  qh POSTmerge= True;
	}
	qh MERGING= True;
      }
      break;
    case 'C':
      if (!isdigit(*s) && *s != '.' && *s != '-')
	fprintf(qh ferr, "qhull warning: no centrum radius given for option 'Cn'.  Ignored.\n");
      else {
	if (*s == '-') {
	  qh premerge_centrum= -qh_strtod (s, &s);
          qh_option ("Centrum-premerge-", NULL, &qh premerge_centrum);
	  qh PREmerge= True;
	}else {
	  qh postmerge_centrum= qh_strtod (s, &s);
          qh_option ("Centrum-postmerge", NULL, &qh postmerge_centrum);
	  qh POSTmerge= True;
	}
	qh MERGING= True;
      }
      break;
    case 'E':
      if (*s == '-')
	fprintf(qh ferr, "qhull warning: negative maximum roundoff given for option 'An'.  Ignored.\n");
      else if (!isdigit(*s))
	fprintf(qh ferr, "qhull warning: no maximum roundoff given for option 'En'.  Ignored.\n");
      else {
	qh DISTround= qh_strtod (s, &s);
        qh_option ("Distance-roundoff", NULL, &qh DISTround);
	qh SETroundoff= True;
      }
      break;
    case 'H':
      start= s;
      qh HALFspace= True;
      qh_strtod (s, &t);
      while (t > s)  {
        if (*t && !isspace (*t)) {
	  if (*t == ',')
	    t++;
	  else
	    fprintf (qh ferr, "qhull warning: origin for Halfspace intersection should be 'Hn,n,n,...'\n");
	}
        s= t;
	qh_strtod (s, &t);
      }
      if (start < t) {
        if (!(qh feasible_string= (char*)calloc (t-start+1, 1))) {
          fprintf(qh ferr, "qhull error: insufficient memory for 'Hn,n,n'\n");
          qh_errexit(qh_ERRmem, NULL, NULL);
        }
        strncpy (qh feasible_string, start, t-start);
        qh_option ("Halfspace-about", NULL, NULL);
        qh_option (qh feasible_string, NULL, NULL);
      }else
        qh_option ("Halfspace", NULL, NULL);
      break;
    case 'R':
      if (!isdigit(*s))
	fprintf(qh ferr, "qhull warning: missing random perturbation for option 'Rn'.  Ignored\n");
      else {
	qh RANDOMfactor= qh_strtod (s, &s);
        qh_option ("Random_perturb", NULL, &qh RANDOMfactor);
        qh RANDOMdist= True;
      }
      break;
    case 'V':
      if (!isdigit(*s) && *s != '-')
	fprintf(qh ferr, "qhull warning: missing visible distance for option 'Vn'.  Ignored\n");
      else {
	qh MINvisible= qh_strtod (s, &s);
        qh_option ("Visible", NULL, &qh MINvisible);
      }
      break;
    case 'U':
      if (!isdigit(*s) && *s != '-')
	fprintf(qh ferr, "qhull warning: missing coplanar distance for option 'Un'.  Ignored\n");
      else {
	qh MAXcoplanar= qh_strtod (s, &s);
        qh_option ("U-coplanar", NULL, &qh MAXcoplanar);
      }
      break;
    case 'W':
      if (*s == '-')
	fprintf(qh ferr, "qhull warning: negative outside width for option 'Wn'.  Ignored.\n");
      else if (!isdigit(*s))
	fprintf(qh ferr, "qhull warning: missing outside width for option 'Wn'.  Ignored\n");
      else {
	qh MINoutside= qh_strtod (s, &s);
        qh_option ("W-outside", NULL, &qh MINoutside);
        qh APPROXhull= True;
      }
      break;
    /************  sub menus ***************/
    case 'F':
      while (*s && !isspace(*s)) {
	switch(*s++) {
	case 'a':
	  qh_option ("Farea", NULL, NULL);
	  qh_appendprint (qh_PRINTarea);
	  qh GETarea= True;
	  break;
	case 'A':
	  qh_option ("FArea-total", NULL, NULL);
	  qh GETarea= True;
	  break;
        case 'c':
          qh_option ("Fcoplanars", NULL, NULL);
          qh_appendprint (qh_PRINTcoplanars);
          break;
        case 'C':
          qh_option ("FCentrums", NULL, NULL);
          qh_appendprint (qh_PRINTcentrums);
          break;
	case 'd':
          qh_option ("Fd-cdd-in", NULL, NULL);
	  qh CDDinput= True;
	  break;
	case 'D':
          qh_option ("FD-cdd-out", NULL, NULL);
	  qh CDDoutput= True;
	  break;
	case 'F':
	  qh_option ("FFacets-xridge", NULL, NULL);
          qh_appendprint (qh_PRINTfacets_xridge);
	  break;
        case 'i':
          qh_option ("Finner", NULL, NULL);
          qh_appendprint (qh_PRINTinner);
          break;
        case 'I':
          qh_option ("FIDs", NULL, NULL);
          qh_appendprint (qh_PRINTids);
          break;
        case 'm':
          qh_option ("Fmerges", NULL, NULL);
          qh_appendprint (qh_PRINTmerges);
          break;
        case 'M':
          qh_option ("FMaple", NULL, NULL);
          qh_appendprint (qh_PRINTmaple);
          break;
        case 'n':
          qh_option ("Fneighbors", NULL, NULL);
          qh_appendprint (qh_PRINTneighbors);
          break;
        case 'N':
          qh_option ("FNeighbors-vertex", NULL, NULL);
          qh_appendprint (qh_PRINTvneighbors);
          break;
        case 'o':
          qh_option ("Fouter", NULL, NULL);
          qh_appendprint (qh_PRINTouter);
          break;
	case 'O':
	  if (qh PRINToptions1st) {
	    qh_option ("FOptions", NULL, NULL);
	    qh_appendprint (qh_PRINToptions);
	  }else
	    qh PRINToptions1st= True;
	  break;
	case 'p':
	  qh_option ("Fpoint-intersect", NULL, NULL);
	  qh_appendprint (qh_PRINTpointintersect);
	  break;
	case 'P':
	  qh_option ("FPoint-nearest", NULL, NULL);
	  qh_appendprint (qh_PRINTpointnearest);
	  break;
	case 'Q':
	  qh_option ("FQhull", NULL, NULL);
	  qh_appendprint (qh_PRINTqhull);
	  break;
        case 's':
          qh_option ("Fsummary", NULL, NULL);
          qh_appendprint (qh_PRINTsummary);
          break;
        case 'S':
          qh_option ("FSize", NULL, NULL);
          qh_appendprint (qh_PRINTsize);
          qh GETarea= True;
          break;
        case 't':
          qh_option ("Ftriangles", NULL, NULL);
          qh_appendprint (qh_PRINTtriangles);
          break;
        case 'v':
          /* option set in qh_initqhull_globals */
          qh_appendprint (qh_PRINTvertices);
          break;
        case 'V':
          qh_option ("FVertex-average", NULL, NULL);
          qh_appendprint (qh_PRINTaverage);
          break;
	case 'x':
	  qh_option ("Fxtremes", NULL, NULL);
	  qh_appendprint (qh_PRINTextremes);
	  break;
	default:
	  s--;
	  fprintf (qh ferr, "qhull warning: unknown 'F' output option %c, rest ignored\n", (int)s[0]);
	  while (*++s && !isspace(*s));
	  break;
	}
      }
      break;
    case 'G':
      isgeom= True;
      qh_appendprint (qh_PRINTgeom);
      while (*s && !isspace(*s)) {