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++;
136  FORALLvisible_facets {
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"));
154  FORALLnew_facets {
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) {
196  FORALLvisible_facets {
197  if (!visible->f.replace)
198  zinc_(Zinsidevisible);
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;
223  zzinc_(Zdistcheck);
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;
229  zzinc_(Zflippedfacets);
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);
315  FOREACHvertex_(qh->del_vertices)
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 
516  FORALLnew_facets {
517  if (!newfacet->mergehorizon)
518  qh_setfacetplane(qh, newfacet);
519  }
520  if (qh->JOGGLEmax < REALmax/2)
521  minimize_(qh->min_vertex, -wwval_(Wnewvertexmax));
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));
735  zinc_(Zhashlookup);
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"));
852  FORALLnew_facets {
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);
864  FORALLnew_facets {
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) {
892  FORALLnew_facets {
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);
923  FORALLnew_facets {
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 */
985 facetT *qh_newfacet(qhT *qh) {
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 */
1018 ridgeT *qh_newridge(qhT *qh) {
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) {
1161  FORALLvertex_(qh->newvertex_list) {
1162  FOREACHneighbor_(vertex) {
1163  if (neighbor->visible)
1164  SETref_(neighbor)= NULL;
1165  }
1166  qh_setcompact(qh, vertex->neighbors);
1167  }
1168  FORALLnew_facets {
1169  FOREACHvertex_(newfacet->vertices)
1170  qh_setappend(qh, &vertex->neighbors, newfacet);
1171  }
1172  FORALLvisible_facets {
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 */
1191  FORALLvisible_facets {
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 
SETref_
#define SETref_(elem)
Definition: qset.h:319
facetT::tricoplanar
flagT tricoplanar
Definition: libqhull.h:314
FORALLnew_facets
#define FORALLnew_facets
Definition: poly.h:89
zzadd_
#define zzadd_(id, val)
Definition: stat.h:397
Zvisfacettot
@ Zvisfacettot
Definition: stat.h:268
qh_delvertex
void qh_delvertex(vertexT *vertex)
Definition: poly2.c:1146
qh_appendvertex
void qh_appendvertex(qhT *qh, vertexT *vertex)
Definition: poly_r.c:72
qh_updatevertices
void qh_updatevertices(qhT *qh)
Definition: poly_r.c:1155
Zvisfacetmax
@ Zvisfacetmax
Definition: stat.h:269
qh_DUPLICATEridge
#define qh_DUPLICATEridge
Definition: poly.h:46
ridgeT::vertices
setT * vertices
Definition: libqhull.h:372
FOREACHridge_
#define FOREACHridge_(ridges)
Definition: libqhull.h:936
facetT::center
coordT * center
Definition: libqhull.h:286
FORALLfacet_
#define FORALLfacet_(facetlist)
Definition: poly.h:77
qh_setappend_set
void qh_setappend_set(setT **setp, setT *setA)
Definition: qset.c:163
facetT::neighbors
setT * neighbors
Definition: libqhull.h:299
qh_newridge
ridgeT * qh_newridge(qhT *qh)
Definition: poly_r.c:1018
vertexT::next
vertexT * next
Definition: libqhull.h:397
qh_checkflipped
boolT qh_checkflipped(qhT *qh, facetT *facet, realT *distp, boolT allerror)
Definition: poly_r.c:218
qh_ALL
#define qh_ALL
Definition: libqhull.h:180
zzinc_
#define zzinc_(id)
Definition: stat.h:384
FORALLvisible_facets
#define FORALLvisible_facets
Definition: poly.h:113
Zflippedfacets
@ Zflippedfacets
Definition: stat.h:134
qh_IDnone
@ qh_IDnone
Definition: libqhull.h:99
SETelemaddr_
#define SETelemaddr_(set, n, type)
Definition: qset.h:353
facetT::newcycle
facetT * newcycle
Definition: libqhull.h:282
qh_setdel
void * qh_setdel(setT *set, void *oldelem)
Definition: qset.c:344
qh_pointid
int qh_pointid(qhT *qh, pointT *point)
Definition: poly_r.c:1053
qh_setdelnth
void * qh_setdelnth(setT *set, int nth)
Definition: qset.c:424
facetT::outsideset
setT * outsideset
Definition: libqhull.h:302
realT
#define realT
Definition: user.h:154
vertexT::point
pointT * point
Definition: libqhull.h:399
qh_setfree
void qh_setfree(setT **setp)
Definition: qset.c:716
qh_ASvoronoi
@ qh_ASvoronoi
Definition: libqhull.h:144
qh_newhashtable
int qh_newhashtable(int newsize)
Definition: poly2.c:2304
getid_
#define getid_(p)
Definition: libqhull.h:823
facetT::visible
flagT visible
Definition: libqhull.h:321
setelemT::i
int i
Definition: qset.h:80
qh_matchneighbor
void qh_matchneighbor(qhT *qh, facetT *newfacet, int newskip, int hashsize, int *hashcount)
Definition: poly_r.c:724
qh_removevertex
void qh_removevertex(qhT *qh, vertexT *vertex)
Definition: poly_r.c:1115
facetT::ridges
setT * ridges
Definition: libqhull.h:297
qhT
Definition: libqhull.h:465
qh_makenewplanes
void qh_makenewplanes(qhT *qh)
Definition: poly_r.c:513
qh_IDunknown
@ qh_IDunknown
Definition: libqhull.h:99
zadd_
#define zadd_(id, val)
Definition: stat.h:400
facetT::flipped
flagT flipped
Definition: libqhull.h:327
Zdelvertexmax
@ Zdelvertexmax
Definition: stat.h:101
trace3
#define trace3(args)
Definition: qhull_a.h:83
zinc_
#define zinc_(id)
Definition: stat.h:386
qh_gethash
int qh_gethash(qhT *qh, int hashsize, setT *set, int size, int firstindex, void *skipelem)
Definition: poly_r.c:405
facetT
Definition: libqhull.h:262
facetT::toporient
flagT toporient
Definition: libqhull.h:322
qh_facetintersect
setT * qh_facetintersect(qhT *qh, facetT *facetA, facetT *facetB, int *skipA, int *skipB, int prepend)
Definition: poly_r.c:343
ridgeT::bottom
facetT * bottom
Definition: libqhull.h:375
qh_matchduplicates
void qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount)
Definition: poly2.c:2088
SETelemt_
#define SETelemt_(set, n, type)
Definition: qset.h:342
ridgeT::top
facetT * top
Definition: libqhull.h:374
vertexT::deleted
flagT deleted
Definition: libqhull.h:407
Wnewvertexmax
@ Wnewvertexmax
Definition: stat.h:196
qh_setappend
void qh_setappend(setT **setp, void *newelem)
Definition: qset.c:131
facetT::seen
flagT seen
Definition: libqhull.h:325
facetT::samecycle
facetT * samecycle
Definition: libqhull.h:280
ridgeT::id
unsigned id
Definition: libqhull.h:376
boolT
#define boolT
Definition: libqhull.h:121
FOREACHneighbor_
#define FOREACHneighbor_(facet)
Definition: libqhull.h:908
facetT::mergehorizon
flagT mergehorizon
Definition: libqhull.h:341
qh_deletevisible
void qh_deletevisible(qhT *qh)
Definition: poly_r.c:292
trace2
#define trace2(args)
Definition: qhull_a.h:82
setT::e
setelemT e[1]
Definition: qset.h:85
otherfacet_
#define otherfacet_(ridge, facet)
Definition: libqhull.h:813
qh_delfacet
void qh_delfacet(qhT *qh, facetT *facet)
Definition: poly_r.c:247
qh_settruncate
void qh_settruncate(setT *set, int size)
Definition: qset.c:1275
False
#define False
Definition: libqhull.h:128
setT
Definition: qset.h:83
trace1
#define trace1(args)
Definition: qhull_a.h:81
qh_IDinterior
@ qh_IDinterior
Definition: libqhull.h:99
REALmax
#define REALmax
Definition: user.h:155
qh_setfacetplane
void qh_setfacetplane(facetT *facet)
Definition: geom.c:929
qh_checkflipped_all
void qh_checkflipped_all(facetT *facetlist)
Definition: poly2.c:831
ptr_intT
long ptr_intT
Definition: mem.h:86
Zhashtests
@ Zhashtests
Definition: stat.h:154
qh_setequal_skip
int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB)
Definition: qset.c:677
qh
#define qh
Definition: libqhull.h:457
SETelem_
#define SETelem_(set, n)
Definition: qset.h:331
qh_errexit
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge)
Definition: user.c:213
qh_setsize
int qh_setsize(setT *set)
Definition: qset.c:1111
ridgeT
Definition: libqhull.h:371
vertexT::previous
vertexT * previous
Definition: libqhull.h:398
qh_printhashtable
void qh_printhashtable(FILE *fp)
Definition: poly2.c:2613
trace0
#define trace0(args)
Definition: qhull_a.h:80
qh_printfacetlist
void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall)
Definition: user.c:325
Zinsidevisible
@ Zinsidevisible
Definition: stat.h:155
setT::maxsize
int maxsize
Definition: qset.h:84
SETfirst_
#define SETfirst_(set)
Definition: qset.h:362
qhull_ra.h
qh_makenewfacet
facetT * qh_makenewfacet(qhT *qh, setT *vertices, boolT toporient, facetT *horizon)
Definition: poly_r.c:479
facetT::next
facetT * next
Definition: libqhull.h:294
qh_errexit2
void qh_errexit2(int exitcode, facetT *facet, facetT *otherfacet)
Definition: libqhull.c:521
qh_setnew
setT * qh_setnew(int setsize)
Definition: qset.c:924
minimize_
#define minimize_(minval, val)
Definition: geom.h:59
zmax_
#define zmax_(id, val)
Definition: stat.h:431
facetT::simplicial
flagT simplicial
Definition: libqhull.h:324
SETaddr_
#define SETaddr_(set, type)
Definition: qset.h:396
SETelemsize
#define SETelemsize
Definition: qset.h:100
qh_distplane
void qh_distplane(pointT *point, facetT *facet, realT *dist)
Definition: geom.c:36
trace4
#define trace4(args)
Definition: qhull_a.h:84
Zdistcheck
@ Zdistcheck
Definition: stat.h:103
qh_removefacet
void qh_removefacet(qhT *qh, facetT *facet)
Definition: poly_r.c:1084
Zhashlookup
@ Zhashlookup
Definition: stat.h:151
qh_ERRprec
#define qh_ERRprec
Definition: libqhull.h:196
wwval_
#define wwval_(id)
Definition: stat.h:414
qh_memfree_
#define qh_memfree_(object, insize, freelistp)
Definition: mem.h:193
qh_addhash
void qh_addhash(void *newelem, setT *hashtable, int hashsize, int hash)
Definition: poly2.c:26
qh_ERRqhull
#define qh_ERRqhull
Definition: libqhull.h:198
qh_setreplace
void qh_setreplace(setT *set, void *oldelem, void *newelem)
Definition: qset.c:1080
qh_memalloc_
#define qh_memalloc_(insize, freelistp, object, type)
Definition: mem.h:164
SETfirstt_
#define SETfirstt_(set, type)
Definition: qset.h:371
x1
x1
pointT
#define pointT
Definition: libqhull.h:96
facetT::visitid
unsigned visitid
Definition: libqhull.h:309
qh_matchnewfacets
void qh_matchnewfacets(qhT *qh)
Definition: poly_r.c:841
vertexT
Definition: libqhull.h:396
vertexT::newlist
flagT newlist
Definition: libqhull.h:408
FOREACHvertex_
#define FOREACHvertex_(vertices)
Definition: libqhull.h:950
facetT::keepcentrum
flagT keepcentrum
Definition: libqhull.h:344
facetT::normal
coordT * normal
Definition: libqhull.h:274
qh_appendfacet
void qh_appendfacet(qhT *qh, facetT *facet)
Definition: poly_r.c:38
Ztotridges
@ Ztotridges
Definition: stat.h:253
qh_makenew_nonsimplicial
facetT * qh_makenew_nonsimplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew)
Definition: poly_r.c:563
facetT::coplanarset
setT * coplanarset
Definition: libqhull.h:305
FOREACHfacet_i_
#define FOREACHfacet_i_(facets)
Definition: libqhull.h:965
facetT::dupridge
flagT dupridge
Definition: libqhull.h:336
qh_fprintf
void qh_fprintf(FILE *fp, int msgcode, const char *fmt,...)
Definition: userprintf.c:42
qh_precision
void qh_precision(const char *reason)
Definition: libqhull.c:1180
dim
int dim
Zdelvertextot
@ Zdelvertextot
Definition: stat.h:100
qh_setindex
int qh_setindex(setT *set, void *atelem)
Definition: qset.c:821
facetT::id
unsigned id
Definition: libqhull.h:311
vertexT::neighbors
setT * neighbors
Definition: libqhull.h:400
FORALLvertex_
#define FORALLvertex_(vertexlist)
Definition: poly.h:101
qh_matchvertices
boolT qh_matchvertices(qhT *qh, int firstindex, setT *verticesA, int skipA, setT *verticesB, int *skipB, boolT *same)
Definition: poly_r.c:952
qh_newfacet
facetT * qh_newfacet(qhT *qh)
Definition: poly_r.c:985
SETindex_
#define SETindex_(set, elem)
Definition: qset.h:308
qh_makenew_simplicial
facetT * qh_makenew_simplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew)
Definition: poly_r.c:660
qh_setnew_delnthsorted
setT * qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend)
Definition: qset.c:967
FOREACHneighbor_i_
#define FOREACHneighbor_i_(facet)
Definition: libqhull.h:983
qh_memfree
void qh_memfree(void *object, int insize)
Definition: mem.c:245
qh_setcompact
void qh_setcompact(setT *set)
Definition: qset.c:276
facetT::vertices
setT * vertices
Definition: libqhull.h:295
qh_attachnewfacets
void qh_attachnewfacets(qhT *qh)
Definition: poly_r.c:129
vertexT::id
unsigned id
Definition: libqhull.h:402
facetT::previous
facetT * previous
Definition: libqhull.h:293
facetT::coplanar
flagT coplanar
Definition: libqhull.h:340
True
#define True
Definition: libqhull.h:129
facetT::f
union facetT::@20 f

hpp-fcl
Author(s):
autogenerated on Fri Feb 14 2025 03:45:51