poly_r.c
Go to the documentation of this file.
1 /*<html><pre> -<a href="qh-poly_r.htm"
2  >-------------------------------</a><a name="TOP">-</a>
3 
4  poly_r.c
5  implements polygons and simplices
6 
7  see qh-poly_r.htm, poly_r.h and libqhull_r.h
8 
9  infrequent code is in poly2_r.c
10  (all but top 50 and their callers 12/3/95)
11 
12  Copyright (c) 1993-2015 The Geometry Center.
13  $Id: //main/2015/qhull/src/libqhull_r/poly_r.c#3 $$Change: 2064 $
14  $DateTime: 2016/01/18 12:36:08 $$Author: bbarber $
15 */
16 
17 #include "qhull_ra.h"
18 
19 /*======== functions in alphabetical order ==========*/
20 
21 /*-<a href="qh-poly_r.htm#TOC"
22  >-------------------------------</a><a name="appendfacet">-</a>
23 
24  qh_appendfacet(qh, facet )
25  appends facet to end of qh.facet_list,
26 
27  returns:
28  updates qh.newfacet_list, facet_next, facet_list
29  increments qh.numfacets
30 
31  notes:
32  assumes qh.facet_list/facet_tail is defined (createsimplex)
33 
34  see:
35  qh_removefacet()
36 
37 */
38 void qh_appendfacet(qhT *qh, facetT *facet) {
39  facetT *tail= qh->facet_tail;
40 
41  if (tail == qh->newfacet_list)
42  qh->newfacet_list= facet;
43  if (tail == qh->facet_next)
44  qh->facet_next= facet;
45  facet->previous= tail->previous;
46  facet->next= tail;
47  if (tail->previous)
48  tail->previous->next= facet;
49  else
50  qh->facet_list= facet;
51  tail->previous= facet;
52  qh->num_facets++;
53  trace4((qh, qh->ferr, 4044, "qh_appendfacet: append f%d to facet_list\n", facet->id));
54 } /* appendfacet */
55 
56 
57 /*-<a href="qh-poly_r.htm#TOC"
58  >-------------------------------</a><a name="appendvertex">-</a>
59 
60  qh_appendvertex(qh, vertex )
61  appends vertex to end of qh.vertex_list,
62 
63  returns:
64  sets vertex->newlist
65  updates qh.vertex_list, newvertex_list
66  increments qh.num_vertices
67 
68  notes:
69  assumes qh.vertex_list/vertex_tail is defined (createsimplex)
70 
71 */
72 void qh_appendvertex(qhT *qh, vertexT *vertex) {
73  vertexT *tail= qh->vertex_tail;
74 
75  if (tail == qh->newvertex_list)
76  qh->newvertex_list= vertex;
77  vertex->newlist= True;
78  vertex->previous= tail->previous;
79  vertex->next= tail;
80  if (tail->previous)
81  tail->previous->next= vertex;
82  else
83  qh->vertex_list= vertex;
84  tail->previous= vertex;
85  qh->num_vertices++;
86  trace4((qh, qh->ferr, 4045, "qh_appendvertex: append v%d to vertex_list\n", vertex->id));
87 } /* appendvertex */
88 
89 
90 /*-<a href="qh-poly_r.htm#TOC"
91  >-------------------------------</a><a name="attachnewfacets">-</a>
92 
93  qh_attachnewfacets(qh, )
94  attach horizon facets to new facets in qh.newfacet_list
95  newfacets have neighbor and ridge links to horizon but not vice versa
96  only needed for qh.ONLYgood
97 
98  returns:
99  set qh.NEWfacets
100  horizon facets linked to new facets
101  ridges changed from visible facets to new facets
102  simplicial ridges deleted
103  qh.visible_list, no ridges valid
104  facet->f.replace is a newfacet (if any)
105 
106  design:
107  delete interior ridges and neighbor sets by
108  for each visible, non-simplicial facet
109  for each ridge
110  if last visit or if neighbor is simplicial
111  if horizon neighbor
112  delete ridge for horizon's ridge set
113  delete ridge
114  erase neighbor set
115  attach horizon facets and new facets by
116  for all new facets
117  if corresponding horizon facet is simplicial
118  locate corresponding visible facet {may be more than one}
119  link visible facet to new facet
120  replace visible facet with new facet in horizon
121  else it's non-simplicial
122  for all visible neighbors of the horizon facet
123  link visible neighbor to new facet
124  delete visible neighbor from horizon facet
125  append new facet to horizon's neighbors
126  the first ridge of the new facet is the horizon ridge
127  link the new facet into the horizon ridge
128 */
129 void qh_attachnewfacets(qhT *qh /* qh.visible_list, newfacet_list */) {
130  facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
131  ridgeT *ridge, **ridgep;
132 
133  qh->NEWfacets= True;
134  trace3((qh, qh->ferr, 3012, "qh_attachnewfacets: delete interior ridges\n"));
135  qh->visit_id++;
137  visible->visitid= qh->visit_id;
138  if (visible->ridges) {
139  FOREACHridge_(visible->ridges) {
140  neighbor= otherfacet_(ridge, visible);
141  if (neighbor->visitid == qh->visit_id
142  || (!neighbor->visible && neighbor->simplicial)) {
143  if (!neighbor->visible) /* delete ridge for simplicial horizon */
144  qh_setdel(neighbor->ridges, ridge);
145  qh_setfree(qh, &(ridge->vertices)); /* delete on 2nd visit */
146  qh_memfree(qh, ridge, (int)sizeof(ridgeT));
147  }
148  }
149  SETfirst_(visible->ridges)= NULL;
150  }
151  SETfirst_(visible->neighbors)= NULL;
152  }
153  trace1((qh, qh->ferr, 1017, "qh_attachnewfacets: attach horizon facets to new facets\n"));
155  horizon= SETfirstt_(newfacet->neighbors, facetT);
156  if (horizon->simplicial) {
157  visible= NULL;
158  FOREACHneighbor_(horizon) { /* may have more than one horizon ridge */
159  if (neighbor->visible) {
160  if (visible) {
161  if (qh_setequal_skip(newfacet->vertices, 0, horizon->vertices,
162  SETindex_(horizon->neighbors, neighbor))) {
163  visible= neighbor;
164  break;
165  }
166  }else
167  visible= neighbor;
168  }
169  }
170  if (visible) {
171  visible->f.replace= newfacet;
172  qh_setreplace(qh, horizon->neighbors, visible, newfacet);
173  }else {
174  qh_fprintf(qh, qh->ferr, 6102, "qhull internal error (qh_attachnewfacets): couldn't find visible facet for horizon f%d of newfacet f%d\n",
175  horizon->id, newfacet->id);
176  qh_errexit2(qh, qh_ERRqhull, horizon, newfacet);
177  }
178  }else { /* non-simplicial, with a ridge for newfacet */
179  FOREACHneighbor_(horizon) { /* may hold for many new facets */
180  if (neighbor->visible) {
181  neighbor->f.replace= newfacet;
182  qh_setdelnth(qh, horizon->neighbors,
183  SETindex_(horizon->neighbors, neighbor));
184  neighborp--; /* repeat */
185  }
186  }
187  qh_setappend(qh, &horizon->neighbors, newfacet);
188  ridge= SETfirstt_(newfacet->ridges, ridgeT);
189  if (ridge->top == horizon)
190  ridge->bottom= newfacet;
191  else
192  ridge->top= newfacet;
193  }
194  } /* newfacets */
195  if (qh->PRINTstatistics) {
197  if (!visible->f.replace)
199  }
200  }
201 } /* attachnewfacets */
202 
203 /*-<a href="qh-poly_r.htm#TOC"
204  >-------------------------------</a><a name="checkflipped">-</a>
205 
206  qh_checkflipped(qh, facet, dist, allerror )
207  checks facet orientation to interior point
208 
209  if allerror set,
210  tests against qh.DISTround
211  else
212  tests against 0 since tested against DISTround before
213 
214  returns:
215  False if it flipped orientation (sets facet->flipped)
216  distance if non-NULL
217 */
218 boolT qh_checkflipped(qhT *qh, facetT *facet, realT *distp, boolT allerror) {
219  realT dist;
220 
221  if (facet->flipped && !distp)
222  return False;
224  qh_distplane(qh, qh->interior_point, facet, &dist);
225  if (distp)
226  *distp= dist;
227  if ((allerror && dist > -qh->DISTround)|| (!allerror && dist >= 0.0)) {
228  facet->flipped= True;
230  trace0((qh, qh->ferr, 19, "qh_checkflipped: facet f%d is flipped, distance= %6.12g during p%d\n",
231  facet->id, dist, qh->furthest_id));
232  qh_precision(qh, "flipped facet");
233  return False;
234  }
235  return True;
236 } /* checkflipped */
237 
238 /*-<a href="qh-poly_r.htm#TOC"
239  >-------------------------------</a><a name="delfacet">-</a>
240 
241  qh_delfacet(qh, facet )
242  removes facet from facet_list and frees up its memory
243 
244  notes:
245  assumes vertices and ridges already freed
246 */
247 void qh_delfacet(qhT *qh, facetT *facet) {
248  void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
249 
250  trace4((qh, qh->ferr, 4046, "qh_delfacet: delete f%d\n", facet->id));
251  if (facet == qh->tracefacet)
252  qh->tracefacet= NULL;
253  if (facet == qh->GOODclosest)
254  qh->GOODclosest= NULL;
255  qh_removefacet(qh, facet);
256  if (!facet->tricoplanar || facet->keepcentrum) {
257  qh_memfree_(qh, facet->normal, qh->normal_size, freelistp);
258  if (qh->CENTERtype == qh_ASvoronoi) { /* braces for macro calls */
259  qh_memfree_(qh, facet->center, qh->center_size, freelistp);
260  }else /* AScentrum */ {
261  qh_memfree_(qh, facet->center, qh->normal_size, freelistp);
262  }
263  }
264  qh_setfree(qh, &(facet->neighbors));
265  if (facet->ridges)
266  qh_setfree(qh, &(facet->ridges));
267  qh_setfree(qh, &(facet->vertices));
268  if (facet->outsideset)
269  qh_setfree(qh, &(facet->outsideset));
270  if (facet->coplanarset)
271  qh_setfree(qh, &(facet->coplanarset));
272  qh_memfree_(qh, facet, (int)sizeof(facetT), freelistp);
273 } /* delfacet */
274 
275 
276 /*-<a href="qh-poly_r.htm#TOC"
277  >-------------------------------</a><a name="deletevisible">-</a>
278 
279  qh_deletevisible()
280  delete visible facets and vertices
281 
282  returns:
283  deletes each facet and removes from facetlist
284  at exit, qh.visible_list empty (== qh.newfacet_list)
285 
286  notes:
287  ridges already deleted
288  horizon facets do not reference facets on qh.visible_list
289  new facets in qh.newfacet_list
290  uses qh.visit_id;
291 */
292 void qh_deletevisible(qhT *qh /*qh.visible_list*/) {
293  facetT *visible, *nextfacet;
294  vertexT *vertex, **vertexp;
295  int numvisible= 0, numdel= qh_setsize(qh, qh->del_vertices);
296 
297  trace1((qh, qh->ferr, 1018, "qh_deletevisible: delete %d visible facets and %d vertices\n",
298  qh->num_visible, numdel));
299  for (visible= qh->visible_list; visible && visible->visible;
300  visible= nextfacet) { /* deleting current */
301  nextfacet= visible->next;
302  numvisible++;
303  qh_delfacet(qh, visible);
304  }
305  if (numvisible != qh->num_visible) {
306  qh_fprintf(qh, qh->ferr, 6103, "qhull internal error (qh_deletevisible): qh->num_visible %d is not number of visible facets %d\n",
307  qh->num_visible, numvisible);
308  qh_errexit(qh, qh_ERRqhull, NULL, NULL);
309  }
310  qh->num_visible= 0;
311  zadd_(Zvisfacettot, numvisible);
312  zmax_(Zvisfacetmax, numvisible);
313  zzadd_(Zdelvertextot, numdel);
314  zmax_(Zdelvertexmax, numdel);
316  qh_delvertex(qh, vertex);
317  qh_settruncate(qh, qh->del_vertices, 0);
318 } /* deletevisible */
319 
320 /*-<a href="qh-poly_r.htm#TOC"
321  >-------------------------------</a><a name="facetintersect">-</a>
322 
323  qh_facetintersect(qh, facetA, facetB, skipa, skipB, prepend )
324  return vertices for intersection of two simplicial facets
325  may include 1 prepended entry (if more, need to settemppush)
326 
327  returns:
328  returns set of qh.hull_dim-1 + prepend vertices
329  returns skipped index for each test and checks for exactly one
330 
331  notes:
332  does not need settemp since set in quick memory
333 
334  see also:
335  qh_vertexintersect and qh_vertexintersect_new
336  use qh_setnew_delnthsorted to get nth ridge (no skip information)
337 
338  design:
339  locate skipped vertex by scanning facet A's neighbors
340  locate skipped vertex by scanning facet B's neighbors
341  intersect the vertex sets
342 */
343 setT *qh_facetintersect(qhT *qh, facetT *facetA, facetT *facetB,
344  int *skipA,int *skipB, int prepend) {
345  setT *intersect;
346  int dim= qh->hull_dim, i, j;
347  facetT **neighborsA, **neighborsB;
348 
349  neighborsA= SETaddr_(facetA->neighbors, facetT);
350  neighborsB= SETaddr_(facetB->neighbors, facetT);
351  i= j= 0;
352  if (facetB == *neighborsA++)
353  *skipA= 0;
354  else if (facetB == *neighborsA++)
355  *skipA= 1;
356  else if (facetB == *neighborsA++)
357  *skipA= 2;
358  else {
359  for (i=3; i < dim; i++) {
360  if (facetB == *neighborsA++) {
361  *skipA= i;
362  break;
363  }
364  }
365  }
366  if (facetA == *neighborsB++)
367  *skipB= 0;
368  else if (facetA == *neighborsB++)
369  *skipB= 1;
370  else if (facetA == *neighborsB++)
371  *skipB= 2;
372  else {
373  for (j=3; j < dim; j++) {
374  if (facetA == *neighborsB++) {
375  *skipB= j;
376  break;
377  }
378  }
379  }
380  if (i >= dim || j >= dim) {
381  qh_fprintf(qh, qh->ferr, 6104, "qhull internal error (qh_facetintersect): f%d or f%d not in others neighbors\n",
382  facetA->id, facetB->id);
383  qh_errexit2(qh, qh_ERRqhull, facetA, facetB);
384  }
385  intersect= qh_setnew_delnthsorted(qh, facetA->vertices, qh->hull_dim, *skipA, prepend);
386  trace4((qh, qh->ferr, 4047, "qh_facetintersect: f%d skip %d matches f%d skip %d\n",
387  facetA->id, *skipA, facetB->id, *skipB));
388  return(intersect);
389 } /* facetintersect */
390 
391 /*-<a href="qh-poly_r.htm#TOC"
392  >-------------------------------</a><a name="gethash">-</a>
393 
394  qh_gethash(qh, hashsize, set, size, firstindex, skipelem )
395  return hashvalue for a set with firstindex and skipelem
396 
397  notes:
398  returned hash is in [0,hashsize)
399  assumes at least firstindex+1 elements
400  assumes skipelem is NULL, in set, or part of hash
401 
402  hashes memory addresses which may change over different runs of the same data
403  using sum for hash does badly in high d
404 */
405 int qh_gethash(qhT *qh, int hashsize, setT *set, int size, int firstindex, void *skipelem) {
406  void **elemp= SETelemaddr_(set, firstindex, void);
407  ptr_intT hash = 0, elem;
408  unsigned result;
409  int i;
410 #ifdef _MSC_VER /* Microsoft Visual C++ -- warn about 64-bit issues */
411 #pragma warning( push) /* WARN64 -- ptr_intT holds a 64-bit pointer */
412 #pragma warning( disable : 4311) /* 'type cast': pointer truncation from 'void*' to 'ptr_intT' */
413 #endif
414 
415  switch (size-firstindex) {
416  case 1:
417  hash= (ptr_intT)(*elemp) - (ptr_intT) skipelem;
418  break;
419  case 2:
420  hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] - (ptr_intT) skipelem;
421  break;
422  case 3:
423  hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
424  - (ptr_intT) skipelem;
425  break;
426  case 4:
427  hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
428  + (ptr_intT)elemp[3] - (ptr_intT) skipelem;
429  break;
430  case 5:
431  hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
432  + (ptr_intT)elemp[3] + (ptr_intT)elemp[4] - (ptr_intT) skipelem;
433  break;
434  case 6:
435  hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
436  + (ptr_intT)elemp[3] + (ptr_intT)elemp[4]+ (ptr_intT)elemp[5]
437  - (ptr_intT) skipelem;
438  break;
439  default:
440  hash= 0;
441  i= 3;
442  do { /* this is about 10% in 10-d */
443  if ((elem= (ptr_intT)*elemp++) != (ptr_intT)skipelem) {
444  hash ^= (elem << i) + (elem >> (32-i));
445  i += 3;
446  if (i >= 32)
447  i -= 32;
448  }
449  }while (*elemp);
450  break;
451  }
452  if (hashsize<0) {
453  qh_fprintf(qh, qh->ferr, 6202, "qhull internal error: negative hashsize %d passed to qh_gethash [poly.c]\n", hashsize);
454  qh_errexit2(qh, qh_ERRqhull, NULL, NULL);
455  }
456  result= (unsigned)hash;
457  result %= (unsigned)hashsize;
458  /* result= 0; for debugging */
459  return result;
460 #ifdef _MSC_VER
461 #pragma warning( pop)
462 #endif
463 } /* gethash */
464 
465 /*-<a href="qh-poly_r.htm#TOC"
466  >-------------------------------</a><a name="makenewfacet">-</a>
467 
468  qh_makenewfacet(qh, vertices, toporient, horizon )
469  creates a toporient? facet from vertices
470 
471  returns:
472  returns newfacet
473  adds newfacet to qh.facet_list
474  newfacet->vertices= vertices
475  if horizon
476  newfacet->neighbor= horizon, but not vice versa
477  newvertex_list updated with vertices
478 */
479 facetT *qh_makenewfacet(qhT *qh, setT *vertices, boolT toporient,facetT *horizon) {
480  facetT *newfacet;
481  vertexT *vertex, **vertexp;
482 
483  FOREACHvertex_(vertices) {
484  if (!vertex->newlist) {
485  qh_removevertex(qh, vertex);
486  qh_appendvertex(qh, vertex);
487  }
488  }
489  newfacet= qh_newfacet(qh);
490  newfacet->vertices= vertices;
491  newfacet->toporient= (unsigned char)toporient;
492  if (horizon)
493  qh_setappend(qh, &(newfacet->neighbors), horizon);
494  qh_appendfacet(qh, newfacet);
495  return(newfacet);
496 } /* makenewfacet */
497 
498 
499 /*-<a href="qh-poly_r.htm#TOC"
500  >-------------------------------</a><a name="makenewplanes">-</a>
501 
502  qh_makenewplanes()
503  make new hyperplanes for facets on qh.newfacet_list
504 
505  returns:
506  all facets have hyperplanes or are marked for merging
507  doesn't create hyperplane if horizon is coplanar (will merge)
508  updates qh.min_vertex if qh.JOGGLEmax
509 
510  notes:
511  facet->f.samecycle is defined for facet->mergehorizon facets
512 */
513 void qh_makenewplanes(qhT *qh /* qh.newfacet_list */) {
514  facetT *newfacet;
515 
517  if (!newfacet->mergehorizon)
518  qh_setfacetplane(qh, newfacet);
519  }
520  if (qh->JOGGLEmax < REALmax/2)
522 } /* makenewplanes */
523 
524 /*-<a href="qh-poly_r.htm#TOC"
525  >-------------------------------</a><a name="makenew_nonsimplicial">-</a>
526 
527  qh_makenew_nonsimplicial(qh, visible, apex, numnew )
528  make new facets for ridges of a visible facet
529 
530  returns:
531  first newfacet, bumps numnew as needed
532  attaches new facets if !qh.ONLYgood
533  marks ridge neighbors for simplicial visible
534  if (qh.ONLYgood)
535  ridges on newfacet, horizon, and visible
536  else
537  ridge and neighbors between newfacet and horizon
538  visible facet's ridges are deleted
539 
540  notes:
541  qh.visit_id if visible has already been processed
542  sets neighbor->seen for building f.samecycle
543  assumes all 'seen' flags initially false
544 
545  design:
546  for each ridge of visible facet
547  get neighbor of visible facet
548  if neighbor was already processed
549  delete the ridge (will delete all visible facets later)
550  if neighbor is a horizon facet
551  create a new facet
552  if neighbor coplanar
553  adds newfacet to f.samecycle for later merging
554  else
555  updates neighbor's neighbor set
556  (checks for non-simplicial facet with multiple ridges to visible facet)
557  updates neighbor's ridge set
558  (checks for simplicial neighbor to non-simplicial visible facet)
559  (deletes ridge if neighbor is simplicial)
560 
561 */
562 #ifndef qh_NOmerge
563 facetT *qh_makenew_nonsimplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew) {
564  void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
565  ridgeT *ridge, **ridgep;
566  facetT *neighbor, *newfacet= NULL, *samecycle;
567  setT *vertices;
568  boolT toporient;
569  int ridgeid;
570 
571  FOREACHridge_(visible->ridges) {
572  ridgeid= ridge->id;
573  neighbor= otherfacet_(ridge, visible);
574  if (neighbor->visible) {
575  if (!qh->ONLYgood) {
576  if (neighbor->visitid == qh->visit_id) {
577  qh_setfree(qh, &(ridge->vertices)); /* delete on 2nd visit */
578  qh_memfree_(qh, ridge, (int)sizeof(ridgeT), freelistp);
579  }
580  }
581  }else { /* neighbor is an horizon facet */
582  toporient= (ridge->top == visible);
583  vertices= qh_setnew(qh, qh->hull_dim); /* makes sure this is quick */
584  qh_setappend(qh, &vertices, apex);
585  qh_setappend_set(qh, &vertices, ridge->vertices);
586  newfacet= qh_makenewfacet(qh, vertices, toporient, neighbor);
587  (*numnew)++;
588  if (neighbor->coplanar) {
589  newfacet->mergehorizon= True;
590  if (!neighbor->seen) {
591  newfacet->f.samecycle= newfacet;
592  neighbor->f.newcycle= newfacet;
593  }else {
594  samecycle= neighbor->f.newcycle;
595  newfacet->f.samecycle= samecycle->f.samecycle;
596  samecycle->f.samecycle= newfacet;
597  }
598  }
599  if (qh->ONLYgood) {
600  if (!neighbor->simplicial)
601  qh_setappend(qh, &(newfacet->ridges), ridge);
602  }else { /* qh_attachnewfacets */
603  if (neighbor->seen) {
604  if (neighbor->simplicial) {
605  qh_fprintf(qh, qh->ferr, 6105, "qhull internal error (qh_makenew_nonsimplicial): simplicial f%d sharing two ridges with f%d\n",
606  neighbor->id, visible->id);
607  qh_errexit2(qh, qh_ERRqhull, neighbor, visible);
608  }
609  qh_setappend(qh, &(neighbor->neighbors), newfacet);
610  }else
611  qh_setreplace(qh, neighbor->neighbors, visible, newfacet);
612  if (neighbor->simplicial) {
613  qh_setdel(neighbor->ridges, ridge);
614  qh_setfree(qh, &(ridge->vertices));
615  qh_memfree(qh, ridge, (int)sizeof(ridgeT));
616  }else {
617  qh_setappend(qh, &(newfacet->ridges), ridge);
618  if (toporient)
619  ridge->top= newfacet;
620  else
621  ridge->bottom= newfacet;
622  }
623  trace4((qh, qh->ferr, 4048, "qh_makenew_nonsimplicial: created facet f%d from v%d and r%d of horizon f%d\n",
624  newfacet->id, apex->id, ridgeid, neighbor->id));
625  }
626  }
627  neighbor->seen= True;
628  } /* for each ridge */
629  if (!qh->ONLYgood)
630  SETfirst_(visible->ridges)= NULL;
631  return newfacet;
632 } /* makenew_nonsimplicial */
633 #else /* qh_NOmerge */
634 facetT *qh_makenew_nonsimplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew) {
635  return NULL;
636 }
637 #endif /* qh_NOmerge */
638 
639 /*-<a href="qh-poly_r.htm#TOC"
640  >-------------------------------</a><a name="makenew_simplicial">-</a>
641 
642  qh_makenew_simplicial(qh, visible, apex, numnew )
643  make new facets for simplicial visible facet and apex
644 
645  returns:
646  attaches new facets if (!qh.ONLYgood)
647  neighbors between newfacet and horizon
648 
649  notes:
650  nop if neighbor->seen or neighbor->visible(see qh_makenew_nonsimplicial)
651 
652  design:
653  locate neighboring horizon facet for visible facet
654  determine vertices and orientation
655  create new facet
656  if coplanar,
657  add new facet to f.samecycle
658  update horizon facet's neighbor list
659 */
660 facetT *qh_makenew_simplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew) {
661  facetT *neighbor, **neighborp, *newfacet= NULL;
662  setT *vertices;
663  boolT flip, toporient;
664  int horizonskip= 0, visibleskip= 0;
665 
666  FOREACHneighbor_(visible) {
667  if (!neighbor->seen && !neighbor->visible) {
668  vertices= qh_facetintersect(qh, neighbor,visible, &horizonskip, &visibleskip, 1);
669  SETfirst_(vertices)= apex;
670  flip= ((horizonskip & 0x1) ^ (visibleskip & 0x1));
671  if (neighbor->toporient)
672  toporient= horizonskip & 0x1;
673  else
674  toporient= (horizonskip & 0x1) ^ 0x1;
675  newfacet= qh_makenewfacet(qh, vertices, toporient, neighbor);
676  (*numnew)++;
677  if (neighbor->coplanar && (qh->PREmerge || qh->MERGEexact)) {
678 #ifndef qh_NOmerge
679  newfacet->f.samecycle= newfacet;
680  newfacet->mergehorizon= True;
681 #endif
682  }
683  if (!qh->ONLYgood)
684  SETelem_(neighbor->neighbors, horizonskip)= newfacet;
685  trace4((qh, qh->ferr, 4049, "qh_makenew_simplicial: create facet f%d top %d from v%d and horizon f%d skip %d top %d and visible f%d skip %d, flip? %d\n",
686  newfacet->id, toporient, apex->id, neighbor->id, horizonskip,
687  neighbor->toporient, visible->id, visibleskip, flip));
688  }
689  }
690  return newfacet;
691 } /* makenew_simplicial */
692 
693 /*-<a href="qh-poly_r.htm#TOC"
694  >-------------------------------</a><a name="matchneighbor">-</a>
695 
696  qh_matchneighbor(qh, newfacet, newskip, hashsize, hashcount )
697  either match subridge of newfacet with neighbor or add to hash_table
698 
699  returns:
700  duplicate ridges are unmatched and marked by qh_DUPLICATEridge
701 
702  notes:
703  ridge is newfacet->vertices w/o newskip vertex
704  do not allocate memory (need to free hash_table cleanly)
705  uses linear hash chains
706 
707  see also:
708  qh_matchduplicates
709 
710  design:
711  for each possible matching facet in qh.hash_table
712  if vertices match
713  set ismatch, if facets have opposite orientation
714  if ismatch and matching facet doesn't have a match
715  match the facets by updating their neighbor sets
716  else
717  indicate a duplicate ridge
718  set facet hyperplane for later testing
719  add facet to hashtable
720  unless the other facet was already a duplicate ridge
721  mark both facets with a duplicate ridge
722  add other facet (if defined) to hash table
723 */
724 void qh_matchneighbor(qhT *qh, facetT *newfacet, int newskip, int hashsize, int *hashcount) {
725  boolT newfound= False; /* True, if new facet is already in hash chain */
726  boolT same, ismatch;
727  int hash, scan;
728  facetT *facet, *matchfacet;
729  int skip, matchskip;
730 
731  hash= qh_gethash(qh, hashsize, newfacet->vertices, qh->hull_dim, 1,
732  SETelem_(newfacet->vertices, newskip));
733  trace4((qh, qh->ferr, 4050, "qh_matchneighbor: newfacet f%d skip %d hash %d hashcount %d\n",
734  newfacet->id, newskip, hash, *hashcount));
736  for (scan= hash; (facet= SETelemt_(qh->hash_table, scan, facetT));
737  scan= (++scan >= hashsize ? 0 : scan)) {
738  if (facet == newfacet) {
739  newfound= True;
740  continue;
741  }
742  zinc_(Zhashtests);
743  if (qh_matchvertices(qh, 1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
744  if (SETelem_(newfacet->vertices, newskip) ==
745  SETelem_(facet->vertices, skip)) {
746  qh_precision(qh, "two facets with the same vertices");
747  qh_fprintf(qh, qh->ferr, 6106, "qhull precision error: Vertex sets are the same for f%d and f%d. Can not force output.\n",
748  facet->id, newfacet->id);
749  qh_errexit2(qh, qh_ERRprec, facet, newfacet);
750  }
751  ismatch= (same == (boolT)((newfacet->toporient ^ facet->toporient)));
752  matchfacet= SETelemt_(facet->neighbors, skip, facetT);
753  if (ismatch && !matchfacet) {
754  SETelem_(facet->neighbors, skip)= newfacet;
755  SETelem_(newfacet->neighbors, newskip)= facet;
756  (*hashcount)--;
757  trace4((qh, qh->ferr, 4051, "qh_matchneighbor: f%d skip %d matched with new f%d skip %d\n",
758  facet->id, skip, newfacet->id, newskip));
759  return;
760  }
761  if (!qh->PREmerge && !qh->MERGEexact) {
762  qh_precision(qh, "a ridge with more than two neighbors");
763  qh_fprintf(qh, qh->ferr, 6107, "qhull precision error: facets f%d, f%d and f%d meet at a ridge with more than 2 neighbors. Can not continue.\n",
764  facet->id, newfacet->id, getid_(matchfacet));
765  qh_errexit2(qh, qh_ERRprec, facet, newfacet);
766  }
767  SETelem_(newfacet->neighbors, newskip)= qh_DUPLICATEridge;
768  newfacet->dupridge= True;
769  if (!newfacet->normal)
770  qh_setfacetplane(qh, newfacet);
771  qh_addhash(newfacet, qh->hash_table, hashsize, hash);
772  (*hashcount)++;
773  if (!facet->normal)
774  qh_setfacetplane(qh, facet);
775  if (matchfacet != qh_DUPLICATEridge) {
776  SETelem_(facet->neighbors, skip)= qh_DUPLICATEridge;
777  facet->dupridge= True;
778  if (!facet->normal)
779  qh_setfacetplane(qh, facet);
780  if (matchfacet) {
781  matchskip= qh_setindex(matchfacet->neighbors, facet);
782  if (matchskip<0) {
783  qh_fprintf(qh, qh->ferr, 6260, "qhull internal error (qh_matchneighbor): matchfacet f%d is in f%d neighbors but not vice versa. Can not continue.\n",
784  matchfacet->id, facet->id);
785  qh_errexit2(qh, qh_ERRqhull, matchfacet, facet);
786  }
787  SETelem_(matchfacet->neighbors, matchskip)= qh_DUPLICATEridge; /* matchskip>=0 by QH6260 */
788  matchfacet->dupridge= True;
789  if (!matchfacet->normal)
790  qh_setfacetplane(qh, matchfacet);
791  qh_addhash(matchfacet, qh->hash_table, hashsize, hash);
792  *hashcount += 2;
793  }
794  }
795  trace4((qh, qh->ferr, 4052, "qh_matchneighbor: new f%d skip %d duplicates ridge for f%d skip %d matching f%d ismatch %d at hash %d\n",
796  newfacet->id, newskip, facet->id, skip,
797  (matchfacet == qh_DUPLICATEridge ? -2 : getid_(matchfacet)),
798  ismatch, hash));
799  return; /* end of duplicate ridge */
800  }
801  }
802  if (!newfound)
803  SETelem_(qh->hash_table, scan)= newfacet; /* same as qh_addhash */
804  (*hashcount)++;
805  trace4((qh, qh->ferr, 4053, "qh_matchneighbor: no match for f%d skip %d at hash %d\n",
806  newfacet->id, newskip, hash));
807 } /* matchneighbor */
808 
809 
810 /*-<a href="qh-poly_r.htm#TOC"
811  >-------------------------------</a><a name="matchnewfacets">-</a>
812 
813  qh_matchnewfacets()
814  match newfacets in qh.newfacet_list to their newfacet neighbors
815 
816  returns:
817  qh.newfacet_list with full neighbor sets
818  get vertices with nth neighbor by deleting nth vertex
819  if qh.PREmerge/MERGEexact or qh.FORCEoutput
820  sets facet->flippped if flipped normal (also prevents point partitioning)
821  if duplicate ridges and qh.PREmerge/MERGEexact
822  sets facet->dupridge
823  missing neighbor links identifies extra ridges to be merging (qh_MERGEridge)
824 
825  notes:
826  newfacets already have neighbor[0] (horizon facet)
827  assumes qh.hash_table is NULL
828  vertex->neighbors has not been updated yet
829  do not allocate memory after qh.hash_table (need to free it cleanly)
830 
831  design:
832  delete neighbor sets for all new facets
833  initialize a hash table
834  for all new facets
835  match facet with neighbors
836  if unmatched facets (due to duplicate ridges)
837  for each new facet with a duplicate ridge
838  match it with a facet
839  check for flipped facets
840 */
841 void qh_matchnewfacets(qhT *qh /* qh.newfacet_list */) {
842  int numnew=0, hashcount=0, newskip;
843  facetT *newfacet, *neighbor;
844  int dim= qh->hull_dim, hashsize, neighbor_i, neighbor_n;
845  setT *neighbors;
846 #ifndef qh_NOtrace
847  int facet_i, facet_n, numfree= 0;
848  facetT *facet;
849 #endif
850 
851  trace1((qh, qh->ferr, 1019, "qh_matchnewfacets: match neighbors for new facets.\n"));
853  numnew++;
854  { /* inline qh_setzero(qh, newfacet->neighbors, 1, qh->hull_dim); */
855  neighbors= newfacet->neighbors;
856  neighbors->e[neighbors->maxsize].i= dim+1; /*may be overwritten*/
857  memset((char *)SETelemaddr_(neighbors, 1, void), 0, dim * SETelemsize);
858  }
859  }
860 
861  qh_newhashtable(qh, numnew*(qh->hull_dim-1)); /* twice what is normally needed,
862  but every ridge could be DUPLICATEridge */
863  hashsize= qh_setsize(qh, qh->hash_table);
865  for (newskip=1; newskip<qh->hull_dim; newskip++) /* furthest/horizon already matched */
866  /* hashsize>0 because hull_dim>1 and numnew>0 */
867  qh_matchneighbor(qh, newfacet, newskip, hashsize, &hashcount);
868 #if 0 /* use the following to trap hashcount errors */
869  {
870  int count= 0, k;
871  facetT *facet, *neighbor;
872 
873  count= 0;
874  FORALLfacet_(qh->newfacet_list) { /* newfacet already in use */
875  for (k=1; k < qh->hull_dim; k++) {
876  neighbor= SETelemt_(facet->neighbors, k, facetT);
877  if (!neighbor || neighbor == qh_DUPLICATEridge)
878  count++;
879  }
880  if (facet == newfacet)
881  break;
882  }
883  if (count != hashcount) {
884  qh_fprintf(qh, qh->ferr, 8088, "qh_matchnewfacets: after adding facet %d, hashcount %d != count %d\n",
885  newfacet->id, hashcount, count);
886  qh_errexit(qh, qh_ERRqhull, newfacet, NULL);
887  }
888  }
889 #endif /* end of trap code */
890  }
891  if (hashcount) {
893  if (newfacet->dupridge) {
894  FOREACHneighbor_i_(qh, newfacet) {
895  if (neighbor == qh_DUPLICATEridge) {
896  qh_matchduplicates(qh, newfacet, neighbor_i, hashsize, &hashcount);
897  /* this may report MERGEfacet */
898  }
899  }
900  }
901  }
902  }
903  if (hashcount) {
904  qh_fprintf(qh, qh->ferr, 6108, "qhull internal error (qh_matchnewfacets): %d neighbors did not match up\n",
905  hashcount);
906  qh_printhashtable(qh, qh->ferr);
907  qh_errexit(qh, qh_ERRqhull, NULL, NULL);
908  }
909 #ifndef qh_NOtrace
910  if (qh->IStracing >= 2) {
911  FOREACHfacet_i_(qh, qh->hash_table) {
912  if (!facet)
913  numfree++;
914  }
915  qh_fprintf(qh, qh->ferr, 8089, "qh_matchnewfacets: %d new facets, %d unused hash entries . hashsize %d\n",
916  numnew, numfree, qh_setsize(qh, qh->hash_table));
917  }
918 #endif /* !qh_NOtrace */
919  qh_setfree(qh, &qh->hash_table);
920  if (qh->PREmerge || qh->MERGEexact) {
921  if (qh->IStracing >= 4)
922  qh_printfacetlist(qh, qh->newfacet_list, NULL, qh_ALL);
924  if (newfacet->normal)
925  qh_checkflipped(qh, newfacet, NULL, qh_ALL);
926  }
927  }else if (qh->FORCEoutput)
928  qh_checkflipped_all(qh, qh->newfacet_list); /* prints warnings for flipped */
929 } /* matchnewfacets */
930 
931 
932 /*-<a href="qh-poly_r.htm#TOC"
933  >-------------------------------</a><a name="matchvertices">-</a>
934 
935  qh_matchvertices(qh, firstindex, verticesA, skipA, verticesB, skipB, same )
936  tests whether vertices match with a single skip
937  starts match at firstindex since all new facets have a common vertex
938 
939  returns:
940  true if matched vertices
941  skip index for each set
942  sets same iff vertices have the same orientation
943 
944  notes:
945  assumes skipA is in A and both sets are the same size
946 
947  design:
948  set up pointers
949  scan both sets checking for a match
950  test orientation
951 */
952 boolT qh_matchvertices(qhT *qh, int firstindex, setT *verticesA, int skipA,
953  setT *verticesB, int *skipB, boolT *same) {
954  vertexT **elemAp, **elemBp, **skipBp=NULL, **skipAp;
955 
956  elemAp= SETelemaddr_(verticesA, firstindex, vertexT);
957  elemBp= SETelemaddr_(verticesB, firstindex, vertexT);
958  skipAp= SETelemaddr_(verticesA, skipA, vertexT);
959  do if (elemAp != skipAp) {
960  while (*elemAp != *elemBp++) {
961  if (skipBp)
962  return False;
963  skipBp= elemBp; /* one extra like FOREACH */
964  }
965  }while (*(++elemAp));
966  if (!skipBp)
967  skipBp= ++elemBp;
968  *skipB= SETindex_(verticesB, skipB); /* i.e., skipBp - verticesB */
969  *same= !((skipA & 0x1) ^ (*skipB & 0x1)); /* result is 0 or 1 */
970  trace4((qh, qh->ferr, 4054, "qh_matchvertices: matched by skip %d(v%d) and skip %d(v%d) same? %d\n",
971  skipA, (*skipAp)->id, *skipB, (*(skipBp-1))->id, *same));
972  return(True);
973 } /* matchvertices */
974 
975 /*-<a href="qh-poly_r.htm#TOC"
976  >-------------------------------</a><a name="newfacet">-</a>
977 
978  qh_newfacet(qh)
979  return a new facet
980 
981  returns:
982  all fields initialized or cleared (NULL)
983  preallocates neighbors set
984 */
986  facetT *facet;
987  void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
988 
989  qh_memalloc_(qh, (int)sizeof(facetT), freelistp, facet, facetT);
990  memset((char *)facet, (size_t)0, sizeof(facetT));
991  if (qh->facet_id == qh->tracefacet_id)
992  qh->tracefacet= facet;
993  facet->id= qh->facet_id++;
994  facet->neighbors= qh_setnew(qh, qh->hull_dim);
995 #if !qh_COMPUTEfurthest
996  facet->furthestdist= 0.0;
997 #endif
998 #if qh_MAXoutside
999  if (qh->FORCEoutput && qh->APPROXhull)
1000  facet->maxoutside= qh->MINoutside;
1001  else
1002  facet->maxoutside= qh->DISTround;
1003 #endif
1004  facet->simplicial= True;
1005  facet->good= True;
1006  facet->newfacet= True;
1007  trace4((qh, qh->ferr, 4055, "qh_newfacet: created facet f%d\n", facet->id));
1008  return(facet);
1009 } /* newfacet */
1010 
1011 
1012 /*-<a href="qh-poly_r.htm#TOC"
1013  >-------------------------------</a><a name="newridge">-</a>
1014 
1015  qh_newridge()
1016  return a new ridge
1017 */
1019  ridgeT *ridge;
1020  void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
1021 
1022  qh_memalloc_(qh, (int)sizeof(ridgeT), freelistp, ridge, ridgeT);
1023  memset((char *)ridge, (size_t)0, sizeof(ridgeT));
1024  zinc_(Ztotridges);
1025  if (qh->ridge_id == UINT_MAX) {
1026  qh_fprintf(qh, qh->ferr, 7074, "\
1027 qhull warning: more than 2^32 ridges. Qhull results are OK. Since the ridge ID wraps around to 0, two ridges may have the same identifier.\n");
1028  }
1029  ridge->id= qh->ridge_id++;
1030  trace4((qh, qh->ferr, 4056, "qh_newridge: created ridge r%d\n", ridge->id));
1031  return(ridge);
1032 } /* newridge */
1033 
1034 
1035 /*-<a href="qh-poly_r.htm#TOC"
1036  >-------------------------------</a><a name="pointid">-</a>
1037 
1038  qh_pointid(qh, point )
1039  return id for a point,
1040  returns qh_IDnone(-3) if null, qh_IDinterior(-2) if interior, or qh_IDunknown(-1) if not known
1041 
1042  alternative code if point is in qh.first_point...
1043  unsigned long id;
1044  id= ((unsigned long)point - (unsigned long)qh.first_point)/qh.normal_size;
1045 
1046  notes:
1047  Valid points are non-negative
1048  WARN64 -- id truncated to 32-bits, at most 2G points
1049  NOerrors returned (QhullPoint::id)
1050  if point not in point array
1051  the code does a comparison of unrelated pointers.
1052 */
1053 int qh_pointid(qhT *qh, pointT *point) {
1054  ptr_intT offset, id;
1055 
1056  if (!point || !qh)
1057  return qh_IDnone;
1058  else if (point == qh->interior_point)
1059  return qh_IDinterior;
1060  else if (point >= qh->first_point
1061  && point < qh->first_point + qh->num_points * qh->hull_dim) {
1062  offset= (ptr_intT)(point - qh->first_point);
1063  id= offset / qh->hull_dim;
1064  }else if ((id= qh_setindex(qh->other_points, point)) != -1)
1065  id += qh->num_points;
1066  else
1067  return qh_IDunknown;
1068  return (int)id;
1069 } /* pointid */
1070 
1071 /*-<a href="qh-poly_r.htm#TOC"
1072  >-------------------------------</a><a name="removefacet">-</a>
1073 
1074  qh_removefacet(qh, facet )
1075  unlinks facet from qh.facet_list,
1076 
1077  returns:
1078  updates qh.facet_list .newfacet_list .facet_next visible_list
1079  decrements qh.num_facets
1080 
1081  see:
1082  qh_appendfacet
1083 */
1084 void qh_removefacet(qhT *qh, facetT *facet) {
1085  facetT *next= facet->next, *previous= facet->previous;
1086 
1087  if (facet == qh->newfacet_list)
1088  qh->newfacet_list= next;
1089  if (facet == qh->facet_next)
1090  qh->facet_next= next;
1091  if (facet == qh->visible_list)
1092  qh->visible_list= next;
1093  if (previous) {
1094  previous->next= next;
1095  next->previous= previous;
1096  }else { /* 1st facet in qh->facet_list */
1097  qh->facet_list= next;
1098  qh->facet_list->previous= NULL;
1099  }
1100  qh->num_facets--;
1101  trace4((qh, qh->ferr, 4057, "qh_removefacet: remove f%d from facet_list\n", facet->id));
1102 } /* removefacet */
1103 
1104 
1105 /*-<a href="qh-poly_r.htm#TOC"
1106  >-------------------------------</a><a name="removevertex">-</a>
1107 
1108  qh_removevertex(qh, vertex )
1109  unlinks vertex from qh.vertex_list,
1110 
1111  returns:
1112  updates qh.vertex_list .newvertex_list
1113  decrements qh.num_vertices
1114 */
1115 void qh_removevertex(qhT *qh, vertexT *vertex) {
1116  vertexT *next= vertex->next, *previous= vertex->previous;
1117 
1118  if (vertex == qh->newvertex_list)
1119  qh->newvertex_list= next;
1120  if (previous) {
1121  previous->next= next;
1122  next->previous= previous;
1123  }else { /* 1st vertex in qh->vertex_list */
1124  qh->vertex_list= vertex->next;
1125  qh->vertex_list->previous= NULL;
1126  }
1127  qh->num_vertices--;
1128  trace4((qh, qh->ferr, 4058, "qh_removevertex: remove v%d from vertex_list\n", vertex->id));
1129 } /* removevertex */
1130 
1131 
1132 /*-<a href="qh-poly_r.htm#TOC"
1133  >-------------------------------</a><a name="updatevertices">-</a>
1134 
1135  qh_updatevertices()
1136  update vertex neighbors and delete interior vertices
1137 
1138  returns:
1139  if qh.VERTEXneighbors, updates neighbors for each vertex
1140  if qh.newvertex_list,
1141  removes visible neighbors from vertex neighbors
1142  if qh.newfacet_list
1143  adds new facets to vertex neighbors
1144  if qh.visible_list
1145  interior vertices added to qh.del_vertices for later partitioning
1146 
1147  design:
1148  if qh.VERTEXneighbors
1149  deletes references to visible facets from vertex neighbors
1150  appends new facets to the neighbor list for each vertex
1151  checks all vertices of visible facets
1152  removes visible facets from neighbor lists
1153  marks unused vertices for deletion
1154 */
1155 void qh_updatevertices(qhT *qh /*qh.newvertex_list, newfacet_list, visible_list*/) {
1156  facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
1157  vertexT *vertex, **vertexp;
1158 
1159  trace3((qh, qh->ferr, 3013, "qh_updatevertices: delete interior vertices and update vertex->neighbors\n"));
1160  if (qh->VERTEXneighbors) {
1162  FOREACHneighbor_(vertex) {
1163  if (neighbor->visible)
1164  SETref_(neighbor)= NULL;
1165  }
1166  qh_setcompact(qh, vertex->neighbors);
1167  }
1169  FOREACHvertex_(newfacet->vertices)
1170  qh_setappend(qh, &vertex->neighbors, newfacet);
1171  }
1173  FOREACHvertex_(visible->vertices) {
1174  if (!vertex->newlist && !vertex->deleted) {
1175  FOREACHneighbor_(vertex) { /* this can happen under merging */
1176  if (!neighbor->visible)
1177  break;
1178  }
1179  if (neighbor)
1180  qh_setdel(vertex->neighbors, visible);
1181  else {
1182  vertex->deleted= True;
1183  qh_setappend(qh, &qh->del_vertices, vertex);
1184  trace2((qh, qh->ferr, 2041, "qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
1185  qh_pointid(qh, vertex->point), vertex->id, visible->id));
1186  }
1187  }
1188  }
1189  }
1190  }else { /* !VERTEXneighbors */
1192  FOREACHvertex_(visible->vertices) {
1193  if (!vertex->newlist && !vertex->deleted) {
1194  vertex->deleted= True;
1195  qh_setappend(qh, &qh->del_vertices, vertex);
1196  trace2((qh, qh->ferr, 2042, "qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
1197  qh_pointid(qh, vertex->point), vertex->id, visible->id));
1198  }
1199  }
1200  }
1201  }
1202 } /* updatevertices */
1203 
1204 
1205 
#define trace2(args)
Definition: qhull_a.h:82
int hull_dim
Definition: libqhull.h:591
Definition: libqhull.h:465
#define qh_ERRprec
Definition: libqhull.h:196
int qh_pointid(qhT *qh, pointT *point)
Definition: poly_r.c:1053
#define qh_ERRqhull
Definition: libqhull.h:198
setT * hash_table
Definition: libqhull.h:760
vertexT * previous
Definition: libqhull.h:398
#define zinc_(id)
Definition: stat.h:386
#define boolT
Definition: libqhull.h:121
void qh_settruncate(setT *set, int size)
Definition: qset.c:1275
setT * neighbors
Definition: libqhull.h:299
Definition: qset.h:83
facetT * top
Definition: libqhull.h:374
#define otherfacet_(ridge, facet)
Definition: libqhull.h:813
boolT NEWfacets
Definition: libqhull.h:733
void qh_appendvertex(qhT *qh, vertexT *vertex)
Definition: poly_r.c:72
long ptr_intT
Definition: mem.h:86
coordT * center
Definition: libqhull.h:286
facetT * qh_makenew_simplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew)
Definition: poly_r.c:660
void qh_checkflipped_all(facetT *facetlist)
Definition: poly2.c:831
void qh_addhash(void *newelem, setT *hashtable, int hashsize, int hash)
Definition: poly2.c:26
#define FOREACHvertex_(vertices)
Definition: libqhull.h:950
#define trace1(args)
Definition: qhull_a.h:81
void qh_setcompact(setT *set)
Definition: qset.c:276
void qh_setreplace(setT *set, void *oldelem, void *newelem)
Definition: qset.c:1080
#define zadd_(id, val)
Definition: stat.h:400
ridgeT * qh_newridge(qhT *qh)
Definition: poly_r.c:1018
#define SETfirstt_(set, type)
Definition: qset.h:371
facetT * facet_tail
Definition: libqhull.h:678
unsigned tracefacet_id
Definition: libqhull.h:686
facetT * facet_list
Definition: libqhull.h:677
#define pointT
Definition: libqhull.h:96
#define FORALLvertex_(vertexlist)
Definition: poly.h:101
flagT mergehorizon
Definition: libqhull.h:341
flagT deleted
Definition: libqhull.h:407
void qh_removevertex(qhT *qh, vertexT *vertex)
Definition: poly_r.c:1115
#define getid_(p)
Definition: libqhull.h:823
#define qh_memalloc_(insize, freelistp, object, type)
Definition: mem.h:164
void qh_fprintf(FILE *fp, int msgcode, const char *fmt,...)
Definition: userprintf.c:42
facetT * newcycle
Definition: libqhull.h:282
void qh_makenewplanes(qhT *qh)
Definition: poly_r.c:513
void qh_precision(const char *reason)
Definition: libqhull.c:1180
void qh_matchneighbor(qhT *qh, facetT *newfacet, int newskip, int hashsize, int *hashcount)
Definition: poly_r.c:724
facetT * previous
Definition: libqhull.h:293
int IStracing
Definition: libqhull.h:503
void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall)
Definition: user.c:325
qh_CENTER CENTERtype
Definition: libqhull.h:716
pointT * interior_point
Definition: libqhull.h:663
#define FORALLfacet_(facetlist)
Definition: poly.h:77
setT * coplanarset
Definition: libqhull.h:305
pointT * first_point
Definition: libqhull.h:594
#define SETref_(elem)
Definition: qset.h:319
facetT * visible_list
Definition: libqhull.h:683
#define SETelemsize
Definition: qset.h:100
boolT qh_checkflipped(qhT *qh, facetT *facet, realT *distp, boolT allerror)
Definition: poly_r.c:218
#define zzadd_(id, val)
Definition: stat.h:397
facetT * newfacet_list
Definition: libqhull.h:682
int qh_gethash(qhT *qh, int hashsize, setT *set, int size, int firstindex, void *skipelem)
Definition: poly_r.c:405
void qh_delvertex(vertexT *vertex)
Definition: poly2.c:1146
int num_facets
Definition: libqhull.h:694
int qh_setindex(setT *set, void *atelem)
Definition: qset.c:821
void qh_printhashtable(FILE *fp)
Definition: poly2.c:2613
setT * qh_facetintersect(qhT *qh, facetT *facetA, facetT *facetB, int *skipA, int *skipB, int prepend)
Definition: poly_r.c:343
setT * ridges
Definition: libqhull.h:297
setelemT e[1]
Definition: qset.h:85
#define FORALLnew_facets
Definition: poly.h:89
#define qh_DUPLICATEridge
Definition: poly.h:46
int dim
setT * other_points
Definition: libqhull.h:762
#define REALmax
Definition: user.h:155
realT JOGGLEmax
Definition: libqhull.h:721
facetT * bottom
Definition: libqhull.h:375
unsigned visitid
Definition: libqhull.h:309
FILE * ferr
Definition: libqhull.h:662
realT MINoutside
Definition: libqhull.h:480
setT * vertices
Definition: libqhull.h:295
vertexT * vertex_tail
Definition: libqhull.h:691
setT * neighbors
Definition: libqhull.h:400
void qh_delfacet(qhT *qh, facetT *facet)
Definition: poly_r.c:247
#define True
Definition: libqhull.h:129
boolT FORCEoutput
Definition: libqhull.h:494
realT DISTround
Definition: libqhull.h:630
boolT VERTEXneighbors
Definition: libqhull.h:606
flagT simplicial
Definition: libqhull.h:324
facetT * qh_makenewfacet(qhT *qh, setT *vertices, boolT toporient, facetT *horizon)
Definition: poly_r.c:479
setT * outsideset
Definition: libqhull.h:302
flagT dupridge
Definition: libqhull.h:336
#define qh
Definition: libqhull.h:457
int num_points
Definition: libqhull.h:593
int normal_size
Definition: libqhull.h:664
boolT PREmerge
Definition: libqhull.h:526
#define FOREACHridge_(ridges)
Definition: libqhull.h:936
void qh_setappend_set(setT **setp, setT *setA)
Definition: qset.c:163
int qh_newhashtable(int newsize)
Definition: poly2.c:2304
pointT * point
Definition: libqhull.h:399
flagT flipped
Definition: libqhull.h:327
#define FOREACHfacet_i_(facets)
Definition: libqhull.h:965
flagT newlist
Definition: libqhull.h:408
int maxsize
Definition: qset.h:84
void qh_errexit2(int exitcode, facetT *facet, facetT *otherfacet)
Definition: libqhull.c:521
#define SETelemaddr_(set, n, type)
Definition: qset.h:353
unsigned id
Definition: libqhull.h:376
setT * qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend)
Definition: qset.c:967
unsigned id
Definition: libqhull.h:402
void qh_deletevisible(qhT *qh)
Definition: poly_r.c:292
void * qh_setdelnth(setT *set, int nth)
Definition: qset.c:424
facetT * samecycle
Definition: libqhull.h:280
void qh_setfree(setT **setp)
Definition: qset.c:716
#define FOREACHneighbor_(facet)
Definition: libqhull.h:908
void qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount)
Definition: poly2.c:2088
#define SETelemt_(set, n, type)
Definition: qset.h:342
void qh_appendfacet(qhT *qh, facetT *facet)
Definition: poly_r.c:38
#define SETindex_(set, elem)
Definition: qset.h:308
flagT keepcentrum
Definition: libqhull.h:344
facetT * facet_next
Definition: libqhull.h:679
facetT * next
Definition: libqhull.h:294
int furthest_id
Definition: libqhull.h:717
void qh_setappend(setT **setp, void *newelem)
Definition: qset.c:131
flagT visible
Definition: libqhull.h:321
#define qh_memfree_(object, insize, freelistp)
Definition: mem.h:193
realT min_vertex
Definition: libqhull.h:729
int i
Definition: qset.h:80
void qh_memfree(void *object, int insize)
Definition: mem.c:245
int num_vertices
Definition: libqhull.h:696
int num_visible
Definition: libqhull.h:685
facetT * qh_makenew_nonsimplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew)
Definition: poly_r.c:563
unsigned int visit_id
Definition: libqhull.h:746
#define SETelem_(set, n)
Definition: qset.h:331
boolT ONLYgood
Definition: libqhull.h:522
boolT MERGEexact
Definition: libqhull.h:511
setT * del_vertices
Definition: libqhull.h:763
flagT seen
Definition: libqhull.h:325
void * qh_setdel(setT *set, void *oldelem)
Definition: qset.c:344
setT * vertices
Definition: libqhull.h:372
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge)
Definition: user.c:213
boolT PRINTstatistics
Definition: libqhull.h:542
int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB)
Definition: qset.c:677
#define zmax_(id, val)
Definition: stat.h:431
void qh_matchnewfacets(qhT *qh)
Definition: poly_r.c:841
void qh_removefacet(qhT *qh, facetT *facet)
Definition: poly_r.c:1084
#define trace0(args)
Definition: qhull_a.h:80
#define trace4(args)
Definition: qhull_a.h:84
unsigned ridge_id
Definition: libqhull.h:701
#define FORALLvisible_facets
Definition: poly.h:113
vertexT * newvertex_list
Definition: libqhull.h:692
int center_size
Definition: libqhull.h:665
#define False
Definition: libqhull.h:128
#define zzinc_(id)
Definition: stat.h:384
boolT APPROXhull
Definition: libqhull.h:479
#define qh_ALL
Definition: libqhull.h:180
void qh_attachnewfacets(qhT *qh)
Definition: poly_r.c:129
flagT toporient
Definition: libqhull.h:322
void qh_distplane(pointT *point, facetT *facet, realT *dist)
Definition: geom.c:36
int qh_setsize(setT *set)
Definition: qset.c:1111
void qh_updatevertices(qhT *qh)
Definition: poly_r.c:1155
setT * qh_setnew(int setsize)
Definition: qset.c:924
unsigned id
Definition: libqhull.h:311
vertexT * next
Definition: libqhull.h:397
#define SETaddr_(set, type)
Definition: qset.h:396
#define realT
Definition: user.h:154
#define FOREACHneighbor_i_(facet)
Definition: libqhull.h:983
flagT coplanar
Definition: libqhull.h:340
coordT * normal
Definition: libqhull.h:274
boolT qh_matchvertices(qhT *qh, int firstindex, setT *verticesA, int skipA, setT *verticesB, int *skipB, boolT *same)
Definition: poly_r.c:952
unsigned facet_id
Definition: libqhull.h:700
#define trace3(args)
Definition: qhull_a.h:83
#define SETfirst_(set)
Definition: qset.h:362
union facetT::@20 f
facetT * qh_newfacet(qhT *qh)
Definition: poly_r.c:985
facetT * GOODclosest
Definition: libqhull.h:718
facetT * tracefacet
Definition: libqhull.h:687
#define minimize_(minval, val)
Definition: geom.h:59
flagT tricoplanar
Definition: libqhull.h:314
#define wwval_(id)
Definition: stat.h:414
vertexT * vertex_list
Definition: libqhull.h:690
void qh_setfacetplane(facetT *facet)
Definition: geom.c:929


hpp-fcl
Author(s):
autogenerated on Fri Jun 2 2023 02:39:01