Line data Source code
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-2020 The Geometry Center.
13 : $Id: //main/2019/qhull/src/libqhull_r/poly_r.c#8 $$Change: 2953 $
14 : $DateTime: 2020/05/21 22:05:32 $$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 190465 : void qh_appendfacet(qhT *qh, facetT *facet) {
39 190465 : facetT *tail= qh->facet_tail;
40 :
41 190465 : if (tail == qh->newfacet_list) {
42 29069 : qh->newfacet_list= facet;
43 29069 : if (tail == qh->visible_list) /* visible_list is at or before newfacet_list */
44 14405 : qh->visible_list= facet;
45 : }
46 190465 : if (tail == qh->facet_next)
47 4 : qh->facet_next= facet;
48 190465 : facet->previous= tail->previous;
49 190465 : facet->next= tail;
50 190465 : if (tail->previous)
51 190461 : tail->previous->next= facet;
52 : else
53 4 : qh->facet_list= facet;
54 190465 : tail->previous= facet;
55 190465 : qh->num_facets++;
56 190465 : trace4((qh, qh->ferr, 4044, "qh_appendfacet: append f%d to facet_list\n", facet->id));
57 190465 : } /* appendfacet */
58 :
59 :
60 : /*-<a href="qh-poly_r.htm#TOC"
61 : >-------------------------------</a><a name="appendvertex">-</a>
62 :
63 : qh_appendvertex(qh, vertex )
64 : appends vertex to end of qh.vertex_list,
65 :
66 : returns:
67 : sets vertex->newfacet
68 : updates qh.vertex_list, newvertex_list
69 : increments qh.num_vertices
70 :
71 : notes:
72 : assumes qh.vertex_list/vertex_tail is defined (createsimplex)
73 :
74 : */
75 150967 : void qh_appendvertex(qhT *qh, vertexT *vertex) {
76 150967 : vertexT *tail= qh->vertex_tail;
77 :
78 150967 : if (tail == qh->newvertex_list)
79 14666 : qh->newvertex_list= vertex;
80 150967 : vertex->newfacet= True;
81 150967 : vertex->previous= tail->previous;
82 150967 : vertex->next= tail;
83 150967 : if (tail->previous)
84 150963 : tail->previous->next= vertex;
85 : else
86 4 : qh->vertex_list= vertex;
87 150967 : tail->previous= vertex;
88 150967 : qh->num_vertices++;
89 150967 : trace4((qh, qh->ferr, 4045, "qh_appendvertex: append v%d to qh.newvertex_list and set v.newfacet\n", vertex->id));
90 150967 : } /* appendvertex */
91 :
92 :
93 : /*-<a href="qh-poly_r.htm#TOC"
94 : >-------------------------------</a><a name="attachnewfacets">-</a>
95 :
96 : qh_attachnewfacets(qh)
97 : attach horizon facets to new facets in qh.newfacet_list
98 : newfacets have neighbor and ridge links to horizon but not vice versa
99 :
100 : returns:
101 : clears qh.NEWtentative
102 : set qh.NEWfacets
103 : horizon facets linked to new facets
104 : ridges changed from visible facets to new facets
105 : simplicial ridges deleted
106 : qh.visible_list, no ridges valid
107 : facet->f.replace is a newfacet (if any)
108 :
109 : notes:
110 : used for qh.NEWtentative, otherwise see qh_makenew_nonsimplicial and qh_makenew_simplicial
111 : qh_delridge_merge not needed (as tested by qh_checkdelridge)
112 :
113 : design:
114 : delete interior ridges and neighbor sets by
115 : for each visible, non-simplicial facet
116 : for each ridge
117 : if last visit or if neighbor is simplicial
118 : if horizon neighbor
119 : delete ridge for horizon's ridge set
120 : delete ridge
121 : erase neighbor set
122 : attach horizon facets and new facets by
123 : for all new facets
124 : if corresponding horizon facet is simplicial
125 : locate corresponding visible facet {may be more than one}
126 : link visible facet to new facet
127 : replace visible facet with new facet in horizon
128 : else it is non-simplicial
129 : for all visible neighbors of the horizon facet
130 : link visible neighbor to new facet
131 : delete visible neighbor from horizon facet
132 : append new facet to horizon's neighbors
133 : the first ridge of the new facet is the horizon ridge
134 : link the new facet into the horizon ridge
135 : */
136 0 : void qh_attachnewfacets(qhT *qh /* qh.visible_list, qh.newfacet_list */) {
137 0 : facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
138 : ridgeT *ridge, **ridgep;
139 :
140 0 : trace3((qh, qh->ferr, 3012, "qh_attachnewfacets: delete interior ridges\n"));
141 0 : if (qh->CHECKfrequently) {
142 0 : qh_checkdelridge(qh);
143 : }
144 0 : qh->visit_id++;
145 0 : FORALLvisible_facets {
146 0 : visible->visitid= qh->visit_id;
147 0 : if (visible->ridges) {
148 0 : FOREACHridge_(visible->ridges) {
149 0 : neighbor= otherfacet_(ridge, visible);
150 0 : if (neighbor->visitid == qh->visit_id
151 0 : || (!neighbor->visible && neighbor->simplicial)) {
152 0 : if (!neighbor->visible) /* delete ridge for simplicial horizon */
153 0 : qh_setdel(neighbor->ridges, ridge);
154 0 : qh_delridge(qh, ridge); /* delete on second visit */
155 : }
156 : }
157 : }
158 : }
159 0 : trace1((qh, qh->ferr, 1017, "qh_attachnewfacets: attach horizon facets to new facets\n"));
160 0 : FORALLnew_facets {
161 0 : horizon= SETfirstt_(newfacet->neighbors, facetT);
162 0 : if (horizon->simplicial) {
163 0 : visible= NULL;
164 0 : FOREACHneighbor_(horizon) { /* may have more than one horizon ridge */
165 0 : if (neighbor->visible) {
166 0 : if (visible) {
167 0 : if (qh_setequal_skip(newfacet->vertices, 0, horizon->vertices,
168 0 : SETindex_(horizon->neighbors, neighbor))) {
169 0 : visible= neighbor;
170 0 : break;
171 : }
172 : }else
173 0 : visible= neighbor;
174 : }
175 : }
176 0 : if (visible) {
177 0 : visible->f.replace= newfacet;
178 0 : qh_setreplace(qh, horizon->neighbors, visible, newfacet);
179 : }else {
180 0 : qh_fprintf(qh, qh->ferr, 6102, "qhull internal error (qh_attachnewfacets): could not find visible facet for horizon f%d of newfacet f%d\n",
181 : horizon->id, newfacet->id);
182 0 : qh_errexit2(qh, qh_ERRqhull, horizon, newfacet);
183 : }
184 : }else { /* non-simplicial, with a ridge for newfacet */
185 0 : FOREACHneighbor_(horizon) { /* may hold for many new facets */
186 0 : if (neighbor->visible) {
187 0 : neighbor->f.replace= newfacet;
188 0 : qh_setdelnth(qh, horizon->neighbors, SETindex_(horizon->neighbors, neighbor));
189 0 : neighborp--; /* repeat */
190 : }
191 : }
192 0 : qh_setappend(qh, &horizon->neighbors, newfacet);
193 0 : ridge= SETfirstt_(newfacet->ridges, ridgeT);
194 0 : if (ridge->top == horizon) {
195 0 : ridge->bottom= newfacet;
196 0 : ridge->simplicialbot= True;
197 : }else {
198 0 : ridge->top= newfacet;
199 0 : ridge->simplicialtop= True;
200 : }
201 : }
202 : } /* newfacets */
203 0 : trace4((qh, qh->ferr, 4094, "qh_attachnewfacets: clear f.ridges and f.neighbors for visible facets, may become invalid before qh_deletevisible\n"));
204 0 : FORALLvisible_facets {
205 0 : if (visible->ridges)
206 0 : SETfirst_(visible->ridges)= NULL;
207 0 : SETfirst_(visible->neighbors)= NULL;
208 : }
209 0 : qh->NEWtentative= False;
210 0 : qh->NEWfacets= True;
211 0 : if (qh->PRINTstatistics) {
212 0 : FORALLvisible_facets {
213 0 : if (!visible->f.replace)
214 0 : zinc_(Zinsidevisible);
215 : }
216 : }
217 0 : } /* attachnewfacets */
218 :
219 : /*-<a href="qh-poly_r.htm#TOC"
220 : >-------------------------------</a><a name="checkflipped">-</a>
221 :
222 : qh_checkflipped(qh, facet, dist, allerror )
223 : checks facet orientation to interior point
224 :
225 : if allerror set,
226 : tests against -qh.DISTround
227 : else
228 : tests against 0.0 since tested against -qh.DISTround before
229 :
230 : returns:
231 : False if it flipped orientation (sets facet->flipped)
232 : distance if non-NULL
233 :
234 : notes:
235 : called by qh_setfacetplane, qh_initialhull, and qh_checkflipped_all
236 : */
237 53386 : boolT qh_checkflipped(qhT *qh, facetT *facet, realT *distp, boolT allerror) {
238 : realT dist;
239 :
240 53386 : if (facet->flipped && !distp)
241 0 : return False;
242 53386 : zzinc_(Zdistcheck);
243 53386 : qh_distplane(qh, qh->interior_point, facet, &dist);
244 53386 : if (distp)
245 0 : *distp= dist;
246 53386 : if ((allerror && dist >= -qh->DISTround) || (!allerror && dist > 0.0)) {
247 5 : facet->flipped= True;
248 5 : trace0((qh, qh->ferr, 19, "qh_checkflipped: facet f%d flipped, allerror? %d, distance= %6.12g during p%d\n",
249 : facet->id, allerror, dist, qh->furthest_id));
250 5 : if (qh->num_facets > qh->hull_dim+1) { /* qh_initialhull reverses orientation if !qh_checkflipped */
251 0 : zzinc_(Zflippedfacets);
252 0 : qh_joggle_restart(qh, "flipped facet");
253 : }
254 5 : return False;
255 : }
256 53381 : return True;
257 : } /* checkflipped */
258 :
259 : /*-<a href="qh-poly_r.htm#TOC"
260 : >-------------------------------</a><a name="delfacet">-</a>
261 :
262 : qh_delfacet(qh, facet )
263 : removes facet from facet_list and frees up its memory
264 :
265 : notes:
266 : assumes vertices and ridges already freed or referenced elsewhere
267 : */
268 102172 : void qh_delfacet(qhT *qh, facetT *facet) {
269 : void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
270 :
271 102172 : trace3((qh, qh->ferr, 3057, "qh_delfacet: delete f%d\n", facet->id));
272 102172 : if (qh->CHECKfrequently || qh->VERIFYoutput) {
273 0 : if (!qh->NOerrexit) {
274 0 : qh_checkdelfacet(qh, facet, qh->facet_mergeset);
275 0 : qh_checkdelfacet(qh, facet, qh->degen_mergeset);
276 0 : qh_checkdelfacet(qh, facet, qh->vertex_mergeset);
277 : }
278 : }
279 102172 : if (facet == qh->tracefacet)
280 0 : qh->tracefacet= NULL;
281 102172 : if (facet == qh->GOODclosest)
282 0 : qh->GOODclosest= NULL;
283 102172 : qh_removefacet(qh, facet);
284 102172 : if (!facet->tricoplanar || facet->keepcentrum) {
285 73362 : qh_memfree_(qh, facet->normal, qh->normal_size, freelistp);
286 73362 : if (qh->CENTERtype == qh_ASvoronoi) { /* braces for macro calls */
287 0 : qh_memfree_(qh, facet->center, qh->center_size, freelistp);
288 : }else /* AScentrum */ {
289 73362 : qh_memfree_(qh, facet->center, qh->normal_size, freelistp);
290 : }
291 : }
292 102172 : qh_setfree(qh, &(facet->neighbors));
293 102172 : if (facet->ridges)
294 52123 : qh_setfree(qh, &(facet->ridges));
295 102172 : qh_setfree(qh, &(facet->vertices));
296 102172 : if (facet->outsideset)
297 26519 : qh_setfree(qh, &(facet->outsideset));
298 102172 : if (facet->coplanarset)
299 3 : qh_setfree(qh, &(facet->coplanarset));
300 102172 : qh_memfree_(qh, facet, (int)sizeof(facetT), freelistp);
301 102172 : } /* delfacet */
302 :
303 :
304 : /*-<a href="qh-poly_r.htm#TOC"
305 : >-------------------------------</a><a name="deletevisible">-</a>
306 :
307 : qh_deletevisible()
308 : delete visible facets and vertices
309 :
310 : returns:
311 : deletes each facet and removes from facetlist
312 : deletes vertices on qh.del_vertices and ridges in qh.del_ridges
313 : at exit, qh.visible_list empty (== qh.newfacet_list)
314 :
315 : notes:
316 : called by qh_all_vertexmerges, qh_addpoint, and qh_qhull
317 : ridges already deleted or moved elsewhere
318 : deleted vertices on qh.del_vertices
319 : horizon facets do not reference facets on qh.visible_list
320 : new facets in qh.newfacet_list
321 : uses qh.visit_id;
322 : */
323 14660 : void qh_deletevisible(qhT *qh /* qh.visible_list */) {
324 : facetT *visible, *nextfacet;
325 : vertexT *vertex, **vertexp;
326 14660 : int numvisible= 0, numdel= qh_setsize(qh, qh->del_vertices);
327 :
328 14660 : trace1((qh, qh->ferr, 1018, "qh_deletevisible: delete %d visible facets and %d vertices\n",
329 : qh->num_visible, numdel));
330 73617 : for (visible=qh->visible_list; visible && visible->visible;
331 58957 : visible= nextfacet) { /* deleting current */
332 58957 : nextfacet= visible->next;
333 58957 : numvisible++;
334 58957 : qh_delfacet(qh, visible); /* f.ridges deleted or moved elsewhere, deleted f.vertices on qh.del_vertices */
335 : }
336 14660 : if (numvisible != qh->num_visible) {
337 0 : qh_fprintf(qh, qh->ferr, 6103, "qhull internal error (qh_deletevisible): qh->num_visible %d is not number of visible facets %d\n",
338 : qh->num_visible, numvisible);
339 0 : qh_errexit(qh, qh_ERRqhull, NULL, NULL);
340 : }
341 14660 : qh->num_visible= 0;
342 14660 : zadd_(Zvisfacettot, numvisible);
343 14660 : zmax_(Zvisfacetmax, numvisible);
344 14660 : zzadd_(Zdelvertextot, numdel);
345 14660 : zmax_(Zdelvertexmax, numdel);
346 14660 : FOREACHvertex_(qh->del_vertices)
347 0 : qh_delvertex(qh, vertex);
348 14660 : qh_settruncate(qh, qh->del_vertices, 0);
349 14660 : } /* deletevisible */
350 :
351 : /*-<a href="qh-poly_r.htm#TOC"
352 : >-------------------------------</a><a name="facetintersect">-</a>
353 :
354 : qh_facetintersect(qh, facetA, facetB, skipa, skipB, prepend )
355 : return vertices for intersection of two simplicial facets
356 : may include 1 prepended entry (if more, need to settemppush)
357 :
358 : returns:
359 : returns set of qh.hull_dim-1 + prepend vertices
360 : returns skipped index for each test and checks for exactly one
361 :
362 : notes:
363 : does not need settemp since set in quick memory
364 :
365 : see also:
366 : qh_vertexintersect and qh_vertexintersect_new
367 : use qh_setnew_delnthsorted to get nth ridge (no skip information)
368 :
369 : design:
370 : locate skipped vertex by scanning facet A's neighbors
371 : locate skipped vertex by scanning facet B's neighbors
372 : intersect the vertex sets
373 : */
374 49253 : setT *qh_facetintersect(qhT *qh, facetT *facetA, facetT *facetB,
375 : int *skipA,int *skipB, int prepend) {
376 : setT *intersect;
377 49253 : int dim= qh->hull_dim, i, j;
378 : facetT **neighborsA, **neighborsB;
379 :
380 49253 : neighborsA= SETaddr_(facetA->neighbors, facetT);
381 49253 : neighborsB= SETaddr_(facetB->neighbors, facetT);
382 49253 : i= j= 0;
383 49253 : if (facetB == *neighborsA++)
384 20564 : *skipA= 0;
385 : /* coverity[overrun-local] */
386 28689 : else if (facetB == *neighborsA++)
387 15063 : *skipA= 1;
388 : /* coverity[overrun-local] */
389 13626 : else if (facetB == *neighborsA++)
390 13626 : *skipA= 2;
391 : else {
392 0 : for (i=3; i < dim; i++) {
393 0 : if (facetB == *neighborsA++) {
394 0 : *skipA= i;
395 0 : break;
396 : }
397 : }
398 : }
399 49253 : if (facetA == *neighborsB++)
400 12805 : *skipB= 0;
401 : /* coverity[overrun-local] */
402 36448 : else if (facetA == *neighborsB++)
403 19769 : *skipB= 1;
404 : /* coverity[overrun-local] */
405 16679 : else if (facetA == *neighborsB++)
406 16679 : *skipB= 2;
407 : else {
408 0 : for (j=3; j < dim; j++) {
409 0 : if (facetA == *neighborsB++) {
410 0 : *skipB= j;
411 0 : break;
412 : }
413 : }
414 : }
415 49253 : if (i >= dim || j >= dim) {
416 0 : qh_fprintf(qh, qh->ferr, 6104, "qhull internal error (qh_facetintersect): f%d or f%d not in other's neighbors\n",
417 : facetA->id, facetB->id);
418 0 : qh_errexit2(qh, qh_ERRqhull, facetA, facetB);
419 : }
420 49253 : intersect= qh_setnew_delnthsorted(qh, facetA->vertices, qh->hull_dim, *skipA, prepend);
421 49253 : trace4((qh, qh->ferr, 4047, "qh_facetintersect: f%d skip %d matches f%d skip %d\n",
422 : facetA->id, *skipA, facetB->id, *skipB));
423 49253 : return(intersect);
424 : } /* facetintersect */
425 :
426 : /*-<a href="qh-poly_r.htm#TOC"
427 : >-------------------------------</a><a name="gethash">-</a>
428 :
429 : qh_gethash(qh, hashsize, set, size, firstindex, skipelem )
430 : return hashvalue for a set with firstindex and skipelem
431 :
432 : notes:
433 : returned hash is in [0,hashsize)
434 : assumes at least firstindex+1 elements
435 : assumes skipelem is NULL, in set, or part of hash
436 :
437 : hashes memory addresses which may change over different runs of the same data
438 : using sum for hash does badly in high d
439 : */
440 262984 : int qh_gethash(qhT *qh, int hashsize, setT *set, int size, int firstindex, void *skipelem) {
441 262984 : void **elemp= SETelemaddr_(set, firstindex, void);
442 262984 : ptr_intT hash= 0, elem;
443 : unsigned int uresult;
444 : int i;
445 : #ifdef _MSC_VER /* Microsoft Visual C++ -- warn about 64-bit issues */
446 : #pragma warning( push) /* WARN64 -- ptr_intT holds a 64-bit pointer */
447 : #pragma warning( disable : 4311) /* 'type cast': pointer truncation from 'void*' to 'ptr_intT' */
448 : #endif
449 :
450 262984 : switch (size-firstindex) {
451 0 : case 1:
452 0 : hash= (ptr_intT)((long long)(ptr_intT)(*elemp) - (ptr_intT) skipelem);
453 0 : break;
454 262984 : case 2:
455 : /* coverity[overrun-local] */
456 262984 : hash= (ptr_intT)((long long)(ptr_intT)(*elemp) + (ptr_intT)elemp[1] - (ptr_intT) skipelem);
457 262984 : break;
458 0 : case 3:
459 0 : hash= (ptr_intT)((long long)(ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
460 0 : - (ptr_intT) skipelem);
461 0 : break;
462 0 : case 4:
463 0 : hash= (ptr_intT)((long long)(ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
464 0 : + (ptr_intT)elemp[3] - (ptr_intT) skipelem);
465 0 : break;
466 0 : case 5:
467 0 : hash= (ptr_intT)((long long)(ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
468 0 : + (ptr_intT)elemp[3] + (ptr_intT)elemp[4] - (ptr_intT) skipelem);
469 0 : break;
470 0 : case 6:
471 0 : hash= (ptr_intT)((long long)(ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
472 0 : + (ptr_intT)elemp[3] + (ptr_intT)elemp[4]+ (ptr_intT)elemp[5]
473 0 : - (ptr_intT) skipelem);
474 0 : break;
475 0 : default:
476 0 : hash= 0;
477 0 : i= 3;
478 : do { /* this is about 10% in 10-d */
479 0 : if ((elem= (ptr_intT)*elemp++) != (ptr_intT)skipelem) {
480 0 : hash ^= (elem << i) + (elem >> (32-i));
481 0 : i += 3;
482 0 : if (i >= 32)
483 0 : i -= 32;
484 : }
485 0 : }while (*elemp);
486 0 : break;
487 : }
488 262984 : if (hashsize<0) {
489 0 : qh_fprintf(qh, qh->ferr, 6202, "qhull internal error: negative hashsize %d passed to qh_gethash [poly_r.c]\n", hashsize);
490 0 : qh_errexit2(qh, qh_ERRqhull, NULL, NULL);
491 : }
492 262984 : uresult= (unsigned int)hash;
493 262984 : uresult %= (unsigned int)hashsize;
494 : /* result= 0; for debugging */
495 262984 : return (int)uresult;
496 : #ifdef _MSC_VER
497 : #pragma warning( pop)
498 : #endif
499 : } /* gethash */
500 :
501 : /*-<a href="qh-poly_r.htm#TOC"
502 : >-------------------------------</a><a name="getreplacement">-</a>
503 :
504 : qh_getreplacement(qh, visible )
505 : get replacement for visible facet
506 :
507 : returns:
508 : valid facet from visible.replace (may be chained)
509 : */
510 26522 : facetT *qh_getreplacement(qhT *qh, facetT *visible) {
511 26522 : unsigned int count= 0;
512 :
513 26522 : facetT *result= visible;
514 58607 : while (result && result->visible) {
515 32085 : result= result->f.replace;
516 32085 : if (count++ > qh->facet_id)
517 0 : qh_infiniteloop(qh, visible);
518 : }
519 26522 : return result;
520 : }
521 :
522 : /*-<a href="qh-poly_r.htm#TOC"
523 : >-------------------------------</a><a name="makenewfacet">-</a>
524 :
525 : qh_makenewfacet(qh, vertices, toporient, horizon )
526 : creates a toporient? facet from vertices
527 :
528 : returns:
529 : returns newfacet
530 : adds newfacet to qh.facet_list
531 : newfacet->vertices= vertices
532 : if horizon
533 : newfacet->neighbor= horizon, but not vice versa
534 : newvertex_list updated with vertices
535 : */
536 131492 : facetT *qh_makenewfacet(qhT *qh, setT *vertices, boolT toporient, facetT *horizon) {
537 : facetT *newfacet;
538 : vertexT *vertex, **vertexp;
539 :
540 525968 : FOREACHvertex_(vertices) {
541 394476 : if (!vertex->newfacet) {
542 88049 : qh_removevertex(qh, vertex);
543 88049 : qh_appendvertex(qh, vertex);
544 : }
545 : }
546 131492 : newfacet= qh_newfacet(qh);
547 131492 : newfacet->vertices= vertices;
548 131492 : if (toporient)
549 65686 : newfacet->toporient= True;
550 131492 : if (horizon)
551 131492 : qh_setappend(qh, &(newfacet->neighbors), horizon);
552 131492 : qh_appendfacet(qh, newfacet);
553 131492 : return(newfacet);
554 : } /* makenewfacet */
555 :
556 :
557 : /*-<a href="qh-poly_r.htm#TOC"
558 : >-------------------------------</a><a name="makenewplanes">-</a>
559 :
560 : qh_makenewplanes()
561 : make new hyperplanes for facets on qh.newfacet_list
562 :
563 : returns:
564 : all facets have hyperplanes or are marked for merging
565 : doesn't create hyperplane if horizon is coplanar (will merge)
566 : updates qh.min_vertex if qh.JOGGLEmax
567 :
568 : notes:
569 : facet->f.samecycle is defined for facet->mergehorizon facets
570 : */
571 14660 : void qh_makenewplanes(qhT *qh /* qh.newfacet_list */) {
572 : facetT *newfacet;
573 :
574 14660 : trace4((qh, qh->ferr, 4074, "qh_makenewplanes: make new hyperplanes for facets on qh.newfacet_list f%d\n",
575 : qh->newfacet_list->id));
576 88064 : FORALLnew_facets {
577 73404 : if (!newfacet->mergehorizon)
578 53357 : qh_setfacetplane(qh, newfacet); /* updates Wnewvertexmax */
579 : }
580 14660 : if (qh->JOGGLEmax < REALmax/2)
581 0 : minimize_(qh->min_vertex, -wwval_(Wnewvertexmax));
582 14660 : } /* makenewplanes */
583 :
584 : #ifndef qh_NOmerge
585 : /*-<a href="qh-poly_r.htm#TOC"
586 : >-------------------------------</a><a name="makenew_nonsimplicial">-</a>
587 :
588 : qh_makenew_nonsimplicial(qh, visible, apex, numnew )
589 : make new facets for ridges of a visible facet
590 :
591 : returns:
592 : first newfacet, bumps numnew as needed
593 : attaches new facets if !qh->NEWtentative
594 : marks ridge neighbors for simplicial visible
595 : if (qh.NEWtentative)
596 : ridges on newfacet, horizon, and visible
597 : else
598 : ridge and neighbors between newfacet and horizon
599 : visible facet's ridges are deleted
600 : visible facet's f.neighbors is empty
601 :
602 : notes:
603 : called by qh_makenewfacets and qh_triangulatefacet
604 : qh.visit_id if visible has already been processed
605 : sets neighbor->seen for building f.samecycle
606 : assumes all 'seen' flags initially false
607 : qh_delridge_merge not needed (as tested by qh_checkdelridge in qh_makenewfacets)
608 :
609 : design:
610 : for each ridge of visible facet
611 : get neighbor of visible facet
612 : if neighbor was already processed
613 : delete the ridge (will delete all visible facets later)
614 : if neighbor is a horizon facet
615 : create a new facet
616 : if neighbor coplanar
617 : adds newfacet to f.samecycle for later merging
618 : else
619 : updates neighbor's neighbor set
620 : (checks for non-simplicial facet with multiple ridges to visible facet)
621 : updates neighbor's ridge set
622 : (checks for simplicial neighbor to non-simplicial visible facet)
623 : (deletes ridge if neighbor is simplicial)
624 :
625 : */
626 32075 : facetT *qh_makenew_nonsimplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew) {
627 : void **freelistp; /* used if !qh_NOmem by qh_memfree_() */
628 : ridgeT *ridge, **ridgep;
629 32075 : facetT *neighbor, *newfacet= NULL, *samecycle;
630 : setT *vertices;
631 : boolT toporient;
632 : unsigned int ridgeid;
633 :
634 121748 : FOREACHridge_(visible->ridges) {
635 89673 : ridgeid= ridge->id;
636 89673 : neighbor= otherfacet_(ridge, visible);
637 89673 : if (neighbor->visible) {
638 7434 : if (!qh->NEWtentative) {
639 7434 : if (neighbor->visitid == qh->visit_id) {
640 3717 : if (qh->traceridge == ridge)
641 0 : qh->traceridge= NULL;
642 3717 : qh_setfree(qh, &(ridge->vertices)); /* delete on 2nd visit */
643 3717 : qh_memfree_(qh, ridge, (int)sizeof(ridgeT), freelistp);
644 : }
645 : }
646 : }else { /* neighbor is an horizon facet */
647 82239 : toporient= (ridge->top == visible);
648 82239 : vertices= qh_setnew(qh, qh->hull_dim); /* makes sure this is quick */
649 82239 : qh_setappend(qh, &vertices, apex);
650 82239 : qh_setappend_set(qh, &vertices, ridge->vertices);
651 82239 : newfacet= qh_makenewfacet(qh, vertices, toporient, neighbor);
652 82239 : (*numnew)++;
653 82239 : if (neighbor->coplanarhorizon) {
654 6675 : newfacet->mergehorizon= True;
655 6675 : if (!neighbor->seen) {
656 6675 : newfacet->f.samecycle= newfacet;
657 6675 : neighbor->f.newcycle= newfacet;
658 : }else {
659 0 : samecycle= neighbor->f.newcycle;
660 0 : newfacet->f.samecycle= samecycle->f.samecycle;
661 0 : samecycle->f.samecycle= newfacet;
662 : }
663 : }
664 82239 : if (qh->NEWtentative) {
665 0 : if (!neighbor->simplicial)
666 0 : qh_setappend(qh, &(newfacet->ridges), ridge);
667 : }else { /* qh_attachnewfacets */
668 82239 : if (neighbor->seen) {
669 0 : if (neighbor->simplicial) {
670 0 : qh_fprintf(qh, qh->ferr, 6105, "qhull internal error (qh_makenew_nonsimplicial): simplicial f%d sharing two ridges with f%d\n",
671 : neighbor->id, visible->id);
672 0 : qh_errexit2(qh, qh_ERRqhull, neighbor, visible);
673 : }
674 0 : qh_setappend(qh, &(neighbor->neighbors), newfacet);
675 : }else
676 82239 : qh_setreplace(qh, neighbor->neighbors, visible, newfacet);
677 82239 : if (neighbor->simplicial) {
678 40765 : qh_setdel(neighbor->ridges, ridge);
679 40765 : qh_delridge(qh, ridge);
680 : }else {
681 41474 : qh_setappend(qh, &(newfacet->ridges), ridge);
682 41474 : if (toporient) {
683 20815 : ridge->top= newfacet;
684 20815 : ridge->simplicialtop= True;
685 : }else {
686 20659 : ridge->bottom= newfacet;
687 20659 : ridge->simplicialbot= True;
688 : }
689 : }
690 : }
691 82239 : trace4((qh, qh->ferr, 4048, "qh_makenew_nonsimplicial: created facet f%d from v%d and r%d of horizon f%d\n",
692 : newfacet->id, apex->id, ridgeid, neighbor->id));
693 : }
694 89673 : neighbor->seen= True;
695 : } /* for each ridge */
696 32075 : return newfacet;
697 : } /* makenew_nonsimplicial */
698 :
699 : #else /* qh_NOmerge */
700 : facetT *qh_makenew_nonsimplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew) {
701 : QHULL_UNUSED(qh)
702 : QHULL_UNUSED(visible)
703 : QHULL_UNUSED(apex)
704 : QHULL_UNUSED(numnew)
705 :
706 : return NULL;
707 : }
708 : #endif /* qh_NOmerge */
709 :
710 : /*-<a href="qh-poly_r.htm#TOC"
711 : >-------------------------------</a><a name="makenew_simplicial">-</a>
712 :
713 : qh_makenew_simplicial(qh, visible, apex, numnew )
714 : make new facets for simplicial visible facet and apex
715 :
716 : returns:
717 : attaches new facets if !qh.NEWtentative
718 : neighbors between newfacet and horizon
719 :
720 : notes:
721 : nop if neighbor->seen or neighbor->visible(see qh_makenew_nonsimplicial)
722 :
723 : design:
724 : locate neighboring horizon facet for visible facet
725 : determine vertices and orientation
726 : create new facet
727 : if coplanar,
728 : add new facet to f.samecycle
729 : update horizon facet's neighbor list
730 : */
731 34070 : facetT *qh_makenew_simplicial(qhT *qh, facetT *visible, vertexT *apex, int *numnew) {
732 34070 : facetT *neighbor, **neighborp, *newfacet= NULL;
733 : setT *vertices;
734 : boolT flip, toporient;
735 34070 : int horizonskip= 0, visibleskip= 0;
736 :
737 136280 : FOREACHneighbor_(visible) {
738 102210 : if (!neighbor->seen && !neighbor->visible) {
739 49253 : vertices= qh_facetintersect(qh, neighbor,visible, &horizonskip, &visibleskip, 1);
740 49253 : SETfirst_(vertices)= apex;
741 49253 : flip= ((horizonskip & 0x1) ^ (visibleskip & 0x1));
742 49253 : if (neighbor->toporient)
743 24768 : toporient= horizonskip & 0x1;
744 : else
745 24485 : toporient= (horizonskip & 0x1) ^ 0x1;
746 49253 : newfacet= qh_makenewfacet(qh, vertices, toporient, neighbor);
747 49253 : (*numnew)++;
748 49253 : if (neighbor->coplanarhorizon && (qh->PREmerge || qh->MERGEexact)) {
749 : #ifndef qh_NOmerge
750 13372 : newfacet->f.samecycle= newfacet;
751 13372 : newfacet->mergehorizon= True;
752 : #endif
753 : }
754 49253 : if (!qh->NEWtentative)
755 49253 : SETelem_(neighbor->neighbors, horizonskip)= newfacet;
756 49253 : 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",
757 : newfacet->id, toporient, apex->id, neighbor->id, horizonskip,
758 : neighbor->toporient, visible->id, visibleskip, flip));
759 : }
760 : }
761 34070 : return newfacet;
762 : } /* makenew_simplicial */
763 :
764 : /*-<a href="qh-poly_r.htm#TOC"
765 : >-------------------------------</a><a name="matchneighbor">-</a>
766 :
767 : qh_matchneighbor(qh, newfacet, newskip, hashsize, hashcount )
768 : either match subridge of newfacet with neighbor or add to hash_table
769 :
770 : returns:
771 : matched ridges of newfacet, except for duplicate ridges
772 : duplicate ridges marked by qh_DUPLICATEridge for qh_matchdupridge
773 :
774 : notes:
775 : called by qh_matchnewfacets
776 : assumes newfacet is simplicial
777 : ridge is newfacet->vertices w/o newskip vertex
778 : do not allocate memory (need to free hash_table cleanly)
779 : uses linear hash chains
780 : see qh_matchdupridge (poly2_r.c)
781 :
782 : design:
783 : for each possible matching facet in qh.hash_table
784 : if vertices match
785 : set ismatch, if facets have opposite orientation
786 : if ismatch and matching facet doesn't have a match
787 : match the facets by updating their neighbor sets
788 : else
789 : note: dupridge detected when a match 'f&d skip %d' has already been seen
790 : need to mark all of the dupridges for qh_matchdupridge
791 : indicate a duplicate ridge by qh_DUPLICATEridge and f.dupridge
792 : add facet to hashtable
793 : unless the other facet was already a duplicate ridge
794 : mark both facets with a duplicate ridge
795 : add other facet (if defined) to hash table
796 :
797 : state at "indicate a duplicate ridge":
798 : newfacet@newskip= the argument
799 : facet= the hashed facet@skip that has the same vertices as newfacet@newskip
800 : same= true if matched vertices have the same orientation
801 : matchfacet= neighbor at facet@skip
802 : matchfacet=qh_DUPLICATEridge, matchfacet was previously detected as a dupridge of facet@skip
803 : ismatch if 'vertex orientation (same) matches facet/newfacet orientation (toporient)
804 : unknown facet will match later
805 :
806 : details at "indicate a duplicate ridge":
807 : if !ismatch and matchfacet,
808 : dupridge is between hashed facet@skip/matchfacet@matchskip and arg newfacet@newskip/unknown
809 : set newfacet@newskip, facet@skip, and matchfacet@matchskip to qh_DUPLICATEridge
810 : add newfacet and matchfacet to hash_table
811 : if ismatch and matchfacet,
812 : same as !ismatch and matchfacet -- it matches facet instead of matchfacet
813 : if !ismatch and !matchfacet
814 : dupridge between hashed facet@skip/unknown and arg newfacet@newskip/unknown
815 : set newfacet@newskip and facet@skip to qh_DUPLICATEridge
816 : add newfacet to hash_table
817 : if ismatch and matchfacet==qh_DUPLICATEridge
818 : dupridge with already duplicated hashed facet@skip and arg newfacet@newskip/unknown
819 : set newfacet@newskip to qh_DUPLICATEridge
820 : add newfacet to hash_table
821 : facet's hyperplane already set
822 : */
823 262984 : void qh_matchneighbor(qhT *qh, facetT *newfacet, int newskip, int hashsize, int *hashcount) {
824 262984 : boolT newfound= False; /* True, if new facet is already in hash chain */
825 : boolT same, ismatch;
826 : int hash, scan;
827 : facetT *facet, *matchfacet;
828 : int skip, matchskip;
829 :
830 262984 : hash= qh_gethash(qh, hashsize, newfacet->vertices, qh->hull_dim, 1,
831 262984 : SETelem_(newfacet->vertices, newskip));
832 262984 : trace4((qh, qh->ferr, 4050, "qh_matchneighbor: newfacet f%d skip %d hash %d hashcount %d\n",
833 : newfacet->id, newskip, hash, *hashcount));
834 262984 : zinc_(Zhashlookup);
835 284778 : for (scan=hash; (facet= SETelemt_(qh->hash_table, scan, facetT));
836 21794 : scan= (++scan >= hashsize ? 0 : scan)) {
837 153286 : if (facet == newfacet) {
838 1607 : newfound= True;
839 1607 : continue;
840 : }
841 151679 : zinc_(Zhashtests);
842 151679 : if (qh_matchvertices(qh, 1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
843 131492 : if (SETelem_(newfacet->vertices, newskip) == SETelem_(facet->vertices, skip)) {
844 0 : qh_joggle_restart(qh, "two new facets with the same vertices");
845 : /* duplicated for multiple skips, not easily avoided */
846 0 : qh_fprintf(qh, qh->ferr, 7084, "qhull topology warning (qh_matchneighbor): will merge vertices to undo new facets -- f%d and f%d have the same vertices (skip %d, skip %d) and same horizon ridges to f%d and f%d\n",
847 0 : facet->id, newfacet->id, skip, newskip, SETfirstt_(facet->neighbors, facetT)->id, SETfirstt_(newfacet->neighbors, facetT)->id);
848 : /* will rename a vertex (QH3053). The fault was duplicate ridges (same vertices) in different facets due to a previous rename. Expensive to detect beforehand */
849 : }
850 131492 : ismatch= (same == (boolT)((newfacet->toporient ^ facet->toporient)));
851 131492 : matchfacet= SETelemt_(facet->neighbors, skip, facetT);
852 131492 : if (ismatch && !matchfacet) {
853 131492 : SETelem_(facet->neighbors, skip)= newfacet;
854 131492 : SETelem_(newfacet->neighbors, newskip)= facet;
855 131492 : (*hashcount)--;
856 131492 : trace4((qh, qh->ferr, 4051, "qh_matchneighbor: f%d skip %d matched with new f%d skip %d\n",
857 : facet->id, skip, newfacet->id, newskip));
858 131492 : return;
859 : }
860 0 : if (!qh->PREmerge && !qh->MERGEexact) {
861 0 : qh_joggle_restart(qh, "a ridge with more than two neighbors");
862 0 : qh_fprintf(qh, qh->ferr, 6107, "qhull topology error: facets f%d, f%d and f%d meet at a ridge with more than 2 neighbors. Can not continue due to no qh.PREmerge and no 'Qx' (MERGEexact)\n",
863 0 : facet->id, newfacet->id, getid_(matchfacet));
864 0 : qh_errexit2(qh, qh_ERRtopology, facet, newfacet);
865 : }
866 0 : SETelem_(newfacet->neighbors, newskip)= qh_DUPLICATEridge;
867 0 : newfacet->dupridge= True;
868 0 : qh_addhash(newfacet, qh->hash_table, hashsize, hash);
869 0 : (*hashcount)++;
870 0 : if (matchfacet != qh_DUPLICATEridge) {
871 0 : SETelem_(facet->neighbors, skip)= qh_DUPLICATEridge;
872 0 : facet->dupridge= True;
873 0 : if (matchfacet) {
874 0 : matchskip= qh_setindex(matchfacet->neighbors, facet);
875 0 : if (matchskip<0) {
876 0 : qh_fprintf(qh, qh->ferr, 6260, "qhull topology error (qh_matchneighbor): matchfacet f%d is in f%d neighbors but not vice versa. Can not continue.\n",
877 : matchfacet->id, facet->id);
878 0 : qh_errexit2(qh, qh_ERRtopology, matchfacet, facet);
879 : }
880 : else {
881 0 : SETelem_(matchfacet->neighbors, matchskip)= qh_DUPLICATEridge; /* matchskip>=0 by QH6260 */
882 0 : matchfacet->dupridge= True;
883 0 : qh_addhash(matchfacet, qh->hash_table, hashsize, hash);
884 0 : *hashcount += 2;
885 : }
886 : }
887 : }
888 0 : 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",
889 : newfacet->id, newskip, facet->id, skip,
890 : (matchfacet == qh_DUPLICATEridge ? -2 : getid_(matchfacet)),
891 : ismatch, hash));
892 0 : return; /* end of duplicate ridge */
893 : }
894 : }
895 131492 : if (!newfound)
896 129885 : SETelem_(qh->hash_table, scan)= newfacet; /* same as qh_addhash */
897 131492 : (*hashcount)++;
898 131492 : trace4((qh, qh->ferr, 4053, "qh_matchneighbor: no match for f%d skip %d at hash %d\n",
899 : newfacet->id, newskip, hash));
900 : } /* matchneighbor */
901 :
902 :
903 : /*-<a href="qh-poly_r.htm#TOC"
904 : >-------------------------------</a><a name="matchnewfacets">-</a>
905 :
906 : qh_matchnewfacets(qh )
907 : match new facets in qh.newfacet_list to their newfacet neighbors
908 : all facets are simplicial
909 :
910 : returns:
911 : if dupridges and merging
912 : returns maxdupdist (>=0.0) from vertex to opposite facet
913 : sets facet->dupridge
914 : missing neighbor links identify dupridges to be merged (qh_DUPLICATEridge)
915 : else
916 : qh.newfacet_list with full neighbor sets
917 : vertices for the nth neighbor match all but the nth vertex
918 : if not merging and qh.FORCEoutput
919 : for facets with normals (i.e., with dupridges)
920 : sets facet->flippped for flipped normals, also prevents point partitioning
921 :
922 : notes:
923 : called by qh_buildcone* and qh_triangulate_facet
924 : neighbor[0] of new facets is the horizon facet
925 : if NEWtentative, new facets not attached to the horizon
926 : assumes qh.hash_table is NULL
927 : vertex->neighbors has not been updated yet
928 : do not allocate memory after qh.hash_table (need to free it cleanly)
929 :
930 : design:
931 : truncate neighbor sets to horizon facet for all new facets
932 : initialize a hash table
933 : for all new facets
934 : match facet with neighbors
935 : if unmatched facets (due to duplicate ridges)
936 : for each new facet with a duplicate ridge
937 : try to match facets with the same coplanar horizon
938 : if not all matched
939 : for each new facet with a duplicate ridge
940 : match it with a coplanar facet, or identify a pinched vertex
941 : if not merging and qh.FORCEoutput
942 : check for flipped facets
943 : */
944 29065 : coordT qh_matchnewfacets(qhT *qh /* qh.newfacet_list */) {
945 29065 : int numnew=0, hashcount=0, newskip;
946 : facetT *newfacet, *neighbor;
947 29065 : coordT maxdupdist= 0.0, maxdist2;
948 29065 : int dim= qh->hull_dim, hashsize, neighbor_i, neighbor_n;
949 : setT *neighbors;
950 : #ifndef qh_NOtrace
951 29065 : int facet_i, facet_n, numunused= 0;
952 : facetT *facet;
953 : #endif
954 :
955 29065 : trace1((qh, qh->ferr, 1019, "qh_matchnewfacets: match neighbors for new facets.\n"));
956 160557 : FORALLnew_facets {
957 131492 : numnew++;
958 : { /* inline qh_setzero(qh, newfacet->neighbors, 1, qh->hull_dim); */
959 131492 : neighbors= newfacet->neighbors;
960 131492 : neighbors->e[neighbors->maxsize].i= dim+1; /*may be overwritten*/
961 131492 : memset((char *)SETelemaddr_(neighbors, 1, void), 0, (size_t)(dim * SETelemsize));
962 : }
963 : }
964 :
965 29065 : qh_newhashtable(qh, numnew*(qh->hull_dim-1)); /* twice what is normally needed,
966 : but every ridge could be DUPLICATEridge */
967 29065 : hashsize= qh_setsize(qh, qh->hash_table);
968 29065 : if( hashsize == 0 ) return 0.0; /* make coverity happy */
969 160557 : FORALLnew_facets {
970 131492 : if (!newfacet->simplicial) {
971 0 : qh_fprintf(qh, qh->ferr, 6377, "qhull internal error (qh_matchnewfacets): expecting simplicial facets on qh.newfacet_list f%d for qh_matchneighbors, qh_matchneighbor, and qh_matchdupridge. Got non-simplicial f%d\n",
972 0 : qh->newfacet_list->id, newfacet->id);
973 0 : qh_errexit2(qh, qh_ERRqhull, newfacet, qh->newfacet_list);
974 : }
975 394476 : for (newskip=1; newskip<qh->hull_dim; newskip++) /* furthest/horizon already matched */
976 : /* hashsize>0 because hull_dim>1 and numnew>0 */
977 262984 : qh_matchneighbor(qh, newfacet, newskip, hashsize, &hashcount);
978 : #if 0 /* use the following to trap hashcount errors */
979 : {
980 : int count= 0, k;
981 : facetT *facet, *neighbor;
982 :
983 : count= 0;
984 : FORALLfacet_(qh->newfacet_list) { /* newfacet already in use */
985 : for (k=1; k < qh->hull_dim; k++) {
986 : neighbor= SETelemt_(facet->neighbors, k, facetT);
987 : if (!neighbor || neighbor == qh_DUPLICATEridge)
988 : count++;
989 : }
990 : if (facet == newfacet)
991 : break;
992 : }
993 : if (count != hashcount) {
994 : qh_fprintf(qh, qh->ferr, 6266, "qhull error (qh_matchnewfacets): after adding facet %d, hashcount %d != count %d\n",
995 : newfacet->id, hashcount, count);
996 : qh_errexit(qh, qh_ERRdebug, newfacet, NULL);
997 : }
998 : }
999 : #endif /* end of trap code */
1000 : } /* end FORALLnew_facets */
1001 29065 : if (hashcount) { /* all neighbors matched, except for qh_DUPLICATEridge neighbors */
1002 0 : qh_joggle_restart(qh, "ridge with multiple neighbors");
1003 0 : if (hashcount) {
1004 0 : FORALLnew_facets {
1005 0 : if (newfacet->dupridge) {
1006 0 : FOREACHneighbor_i_(qh, newfacet) {
1007 0 : if (neighbor == qh_DUPLICATEridge) {
1008 0 : maxdist2= qh_matchdupridge(qh, newfacet, neighbor_i, hashsize, &hashcount);
1009 0 : maximize_(maxdupdist, maxdist2);
1010 : }
1011 : }
1012 : }
1013 : }
1014 : }
1015 : }
1016 29065 : if (hashcount) {
1017 0 : qh_fprintf(qh, qh->ferr, 6108, "qhull internal error (qh_matchnewfacets): %d neighbors did not match up\n",
1018 : hashcount);
1019 0 : qh_printhashtable(qh, qh->ferr);
1020 0 : qh_errexit(qh, qh_ERRqhull, NULL, NULL);
1021 : }
1022 : #ifndef qh_NOtrace
1023 29065 : if (qh->IStracing >= 3) {
1024 0 : FOREACHfacet_i_(qh, qh->hash_table) {
1025 0 : if (!facet)
1026 0 : numunused++;
1027 : }
1028 0 : qh_fprintf(qh, qh->ferr, 3063, "qh_matchnewfacets: maxdupdist %2.2g, new facets %d, unused hash entries %d, hashsize %d\n",
1029 : maxdupdist, numnew, numunused, qh_setsize(qh, qh->hash_table));
1030 : }
1031 : #endif /* !qh_NOtrace */
1032 29065 : qh_setfree(qh, &qh->hash_table);
1033 29065 : if (qh->PREmerge || qh->MERGEexact) {
1034 29065 : if (qh->IStracing >= 4)
1035 0 : qh_printfacetlist(qh, qh->newfacet_list, NULL, qh_ALL);
1036 : }
1037 29065 : return maxdupdist;
1038 : } /* matchnewfacets */
1039 :
1040 :
1041 : /*-<a href="qh-poly_r.htm#TOC"
1042 : >-------------------------------</a><a name="matchvertices">-</a>
1043 :
1044 : qh_matchvertices(qh, firstindex, verticesA, skipA, verticesB, skipB, same )
1045 : tests whether vertices match with a single skip
1046 : starts match at firstindex since all new facets have a common vertex
1047 :
1048 : returns:
1049 : true if matched vertices
1050 : skip index for skipB
1051 : sets same iff vertices have the same orientation
1052 :
1053 : notes:
1054 : called by qh_matchneighbor and qh_matchdupridge
1055 : assumes skipA is in A and both sets are the same size
1056 :
1057 : design:
1058 : set up pointers
1059 : scan both sets checking for a match
1060 : test orientation
1061 : */
1062 151679 : boolT qh_matchvertices(qhT *qh, int firstindex, setT *verticesA, int skipA,
1063 : setT *verticesB, int *skipB, boolT *same) {
1064 151679 : vertexT **elemAp, **elemBp, **skipBp=NULL, **skipAp;
1065 :
1066 151679 : elemAp= SETelemaddr_(verticesA, firstindex, vertexT);
1067 151679 : elemBp= SETelemaddr_(verticesB, firstindex, vertexT);
1068 151679 : skipAp= SETelemaddr_(verticesA, skipA, vertexT);
1069 291281 : do if (elemAp != skipAp) {
1070 227025 : while (*elemAp != *elemBp++) {
1071 95533 : if (skipBp)
1072 20187 : return False;
1073 75346 : skipBp= elemBp; /* one extra like FOREACH */
1074 : }
1075 : /* coverity[overrun-local] */
1076 271094 : }while (*(++elemAp));
1077 131492 : if (!skipBp)
1078 76333 : skipBp= ++elemBp;
1079 131492 : *skipB= SETindex_(verticesB, skipB); /* i.e., skipBp - verticesB
1080 : verticesA and verticesB are the same size, otherwise trace4 may segfault */
1081 131492 : *same= !((skipA & 0x1) ^ (*skipB & 0x1)); /* result is 0 or 1 */
1082 : /* coverity[overrun-local] */
1083 131492 : trace4((qh, qh->ferr, 4054, "qh_matchvertices: matched by skip %d(v%d) and skip %d(v%d) same? %d\n",
1084 : skipA, (*skipAp)->id, *skipB, (*(skipBp-1))->id, *same));
1085 131492 : return(True);
1086 : } /* matchvertices */
1087 :
1088 : /*-<a href="qh-poly_r.htm#TOC"
1089 : >-------------------------------</a><a name="newfacet">-</a>
1090 :
1091 : qh_newfacet(qh)
1092 : return a new facet
1093 :
1094 : returns:
1095 : all fields initialized or cleared (NULL)
1096 : preallocates neighbors set
1097 : */
1098 131512 : facetT *qh_newfacet(qhT *qh) {
1099 : facetT *facet;
1100 : void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
1101 :
1102 131512 : qh_memalloc_(qh, (int)sizeof(facetT), freelistp, facet, facetT);
1103 131512 : memset((char *)facet, (size_t)0, sizeof(facetT));
1104 131512 : if (qh->facet_id == qh->tracefacet_id)
1105 0 : qh->tracefacet= facet;
1106 131512 : facet->id= qh->facet_id++;
1107 131512 : facet->neighbors= qh_setnew(qh, qh->hull_dim);
1108 : #if !qh_COMPUTEfurthest
1109 131512 : facet->furthestdist= 0.0;
1110 : #endif
1111 : #if qh_MAXoutside
1112 131512 : if (qh->FORCEoutput && qh->APPROXhull)
1113 0 : facet->maxoutside= qh->MINoutside;
1114 : else
1115 131512 : facet->maxoutside= qh->DISTround; /* same value as test for QH7082 */
1116 : #endif
1117 131512 : facet->simplicial= True;
1118 131512 : facet->good= True;
1119 131512 : facet->newfacet= True;
1120 131512 : trace4((qh, qh->ferr, 4055, "qh_newfacet: created facet f%d\n", facet->id));
1121 131512 : return(facet);
1122 : } /* newfacet */
1123 :
1124 :
1125 : /*-<a href="qh-poly_r.htm#TOC"
1126 : >-------------------------------</a><a name="newridge">-</a>
1127 :
1128 : qh_newridge()
1129 : return a new ridge
1130 : notes:
1131 : caller sets qh.traceridge
1132 : */
1133 64530 : ridgeT *qh_newridge(qhT *qh) {
1134 : ridgeT *ridge;
1135 : void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
1136 :
1137 64530 : qh_memalloc_(qh, (int)sizeof(ridgeT), freelistp, ridge, ridgeT);
1138 64530 : memset((char *)ridge, (size_t)0, sizeof(ridgeT));
1139 64530 : zinc_(Ztotridges);
1140 64530 : if (qh->ridge_id == UINT_MAX) {
1141 0 : qh_fprintf(qh, qh->ferr, 7074, "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");
1142 : }
1143 64530 : ridge->id= qh->ridge_id++;
1144 64530 : trace4((qh, qh->ferr, 4056, "qh_newridge: created ridge r%d\n", ridge->id));
1145 64530 : return(ridge);
1146 : } /* newridge */
1147 :
1148 :
1149 : /*-<a href="qh-poly_r.htm#TOC"
1150 : >-------------------------------</a><a name="pointid">-</a>
1151 :
1152 : qh_pointid(qh, point )
1153 : return id for a point,
1154 : returns qh_IDnone(-3) if null, qh_IDinterior(-2) if interior, or qh_IDunknown(-1) if not known
1155 :
1156 : alternative code if point is in qh.first_point...
1157 : unsigned long id;
1158 : id= ((unsigned long)point - (unsigned long)qh.first_point)/qh.normal_size;
1159 :
1160 : notes:
1161 : Valid points are non-negative
1162 : WARN64 -- id truncated to 32-bits, at most 2G points
1163 : NOerrors returned (QhullPoint::id)
1164 : if point not in point array
1165 : the code does a comparison of unrelated pointers.
1166 : */
1167 159888 : int qh_pointid(qhT *qh, pointT *point) {
1168 : ptr_intT offset, id;
1169 :
1170 159888 : if (!point || !qh)
1171 3 : return qh_IDnone;
1172 159885 : else if (point == qh->interior_point)
1173 0 : return qh_IDinterior;
1174 159885 : else if (point >= qh->first_point
1175 159885 : && point < qh->first_point + qh->num_points * qh->hull_dim) {
1176 159885 : offset= (ptr_intT)(point - qh->first_point);
1177 : /* coverity[divide_arg] */
1178 159885 : id= offset / qh->hull_dim;
1179 0 : }else if ((id= qh_setindex(qh->other_points, point)) != -1)
1180 0 : id += qh->num_points;
1181 : else
1182 0 : return qh_IDunknown;
1183 159885 : return (int)id;
1184 : } /* pointid */
1185 :
1186 : /*-<a href="qh-poly_r.htm#TOC"
1187 : >-------------------------------</a><a name="removefacet">-</a>
1188 :
1189 : qh_removefacet(qh, facet )
1190 : unlinks facet from qh.facet_list,
1191 :
1192 : returns:
1193 : updates qh.facet_list .newfacet_list .facet_next visible_list
1194 : decrements qh.num_facets
1195 :
1196 : see:
1197 : qh_appendfacet
1198 : */
1199 224395 : void qh_removefacet(qhT *qh, facetT *facet) {
1200 224395 : facetT *next= facet->next, *previous= facet->previous; /* next is always defined */
1201 :
1202 224395 : if (facet == qh->newfacet_list)
1203 11390 : qh->newfacet_list= next;
1204 224395 : if (facet == qh->facet_next)
1205 20349 : qh->facet_next= next;
1206 224395 : if (facet == qh->visible_list)
1207 58957 : qh->visible_list= next;
1208 224395 : if (previous) {
1209 224386 : previous->next= next;
1210 224386 : next->previous= previous;
1211 : }else { /* 1st facet in qh->facet_list */
1212 9 : qh->facet_list= next;
1213 9 : qh->facet_list->previous= NULL;
1214 : }
1215 224395 : qh->num_facets--;
1216 224395 : trace4((qh, qh->ferr, 4057, "qh_removefacet: removed f%d from facet_list, newfacet_list, and visible_list\n", facet->id));
1217 224395 : } /* removefacet */
1218 :
1219 :
1220 : /*-<a href="qh-poly_r.htm#TOC"
1221 : >-------------------------------</a><a name="removevertex">-</a>
1222 :
1223 : qh_removevertex(qh, vertex )
1224 : unlinks vertex from qh.vertex_list,
1225 :
1226 : returns:
1227 : updates qh.vertex_list .newvertex_list
1228 : decrements qh.num_vertices
1229 : */
1230 136291 : void qh_removevertex(qhT *qh, vertexT *vertex) {
1231 136291 : vertexT *next= vertex->next, *previous= vertex->previous; /* next is always defined */
1232 :
1233 136291 : trace4((qh, qh->ferr, 4058, "qh_removevertex: remove v%d from qh.vertex_list\n", vertex->id));
1234 136291 : if (vertex == qh->newvertex_list)
1235 0 : qh->newvertex_list= next;
1236 136291 : if (previous) {
1237 136274 : previous->next= next;
1238 136274 : next->previous= previous;
1239 : }else { /* 1st vertex in qh->vertex_list */
1240 17 : qh->vertex_list= next;
1241 17 : qh->vertex_list->previous= NULL;
1242 : }
1243 136291 : qh->num_vertices--;
1244 136291 : } /* removevertex */
1245 :
1246 :
1247 : /*-<a href="qh-poly_r.htm#TOC"
1248 : >-------------------------------</a><a name="update_vertexneighbors">-</a>
1249 :
1250 : qh_update_vertexneighbors(qh )
1251 : update vertex neighbors and delete interior vertices
1252 :
1253 : returns:
1254 : if qh.VERTEXneighbors,
1255 : if qh.newvertex_list,
1256 : removes visible neighbors from vertex neighbors
1257 : if qh.newfacet_list
1258 : adds new facets to vertex neighbors
1259 : if qh.visible_list
1260 : interior vertices added to qh.del_vertices for later partitioning as coplanar points
1261 : if not qh.VERTEXneighbors (not merging)
1262 : interior vertices of visible facets added to qh.del_vertices for later partitioning as coplanar points
1263 :
1264 : notes
1265 : [jan'19] split off qh_update_vertexneighbors_cone. Optimize the remaining cases in a future release
1266 : called by qh_triangulate_facet after triangulating a non-simplicial facet, followed by reset_lists
1267 : called by qh_triangulate after triangulating null and mirror facets
1268 : called by qh_all_vertexmerges after calling qh_merge_pinchedvertices
1269 :
1270 : design:
1271 : if qh.VERTEXneighbors
1272 : for each vertex on newvertex_list (i.e., new vertices and vertices of new facets)
1273 : delete visible facets from vertex neighbors
1274 : for each new facet on newfacet_list
1275 : for each vertex of facet
1276 : append facet to vertex neighbors
1277 : for each visible facet on qh.visible_list
1278 : for each vertex of facet
1279 : if the vertex is not on a new facet and not itself deleted
1280 : if the vertex has a not-visible neighbor (due to merging)
1281 : remove the visible facet from the vertex's neighbors
1282 : otherwise
1283 : add the vertex to qh.del_vertices for later deletion
1284 :
1285 : if not qh.VERTEXneighbors (not merging)
1286 : for each vertex of a visible facet
1287 : if the vertex is not on a new facet and not itself deleted
1288 : add the vertex to qh.del_vertices for later deletion
1289 : */
1290 14408 : void qh_update_vertexneighbors(qhT *qh /* qh.newvertex_list, newfacet_list, visible_list */) {
1291 14408 : facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
1292 : vertexT *vertex, **vertexp;
1293 14408 : int neighborcount= 0;
1294 :
1295 14408 : if (qh->VERTEXneighbors) {
1296 14408 : trace3((qh, qh->ferr, 3013, "qh_update_vertexneighbors: update v.neighbors for qh.newvertex_list (v%d) and qh.newfacet_list (f%d)\n",
1297 : getid_(qh->newvertex_list), getid_(qh->newfacet_list)));
1298 29053 : FORALLvertex_(qh->newvertex_list) {
1299 14645 : neighborcount= 0;
1300 247019 : FOREACHneighbor_(vertex) {
1301 232374 : if (neighbor->visible) {
1302 144518 : neighborcount++;
1303 144518 : SETref_(neighbor)= NULL;
1304 : }
1305 : }
1306 14645 : if (neighborcount) {
1307 14645 : trace4((qh, qh->ferr, 4046, "qh_update_vertexneighbors: delete %d of %d vertex neighbors for v%d. Removes to-be-deleted, visible facets\n",
1308 : neighborcount, qh_setsize(qh, vertex->neighbors), vertex->id));
1309 14645 : qh_setcompact(qh, vertex->neighbors);
1310 : }
1311 : }
1312 72496 : FORALLnew_facets {
1313 58088 : if (qh->first_newfacet && newfacet->id >= qh->first_newfacet) {
1314 232352 : FOREACHvertex_(newfacet->vertices)
1315 174264 : qh_setappend(qh, &vertex->neighbors, newfacet);
1316 : }else { /* called after qh_merge_pinchedvertices. In 7-D, many more neighbors than new facets. qh_setin is expensive */
1317 0 : FOREACHvertex_(newfacet->vertices)
1318 0 : qh_setunique(qh, &vertex->neighbors, newfacet);
1319 : }
1320 : }
1321 14408 : trace3((qh, qh->ferr, 3058, "qh_update_vertexneighbors: delete interior vertices for qh.visible_list (f%d)\n",
1322 : getid_(qh->visible_list)));
1323 14408 : FORALLvisible_facets {
1324 0 : FOREACHvertex_(visible->vertices) {
1325 0 : if (!vertex->newfacet && !vertex->deleted) {
1326 0 : FOREACHneighbor_(vertex) { /* this can happen under merging */
1327 0 : if (!neighbor->visible)
1328 0 : break;
1329 : }
1330 0 : if (neighbor)
1331 0 : qh_setdel(vertex->neighbors, visible);
1332 : else {
1333 0 : vertex->deleted= True;
1334 0 : qh_setappend(qh, &qh->del_vertices, vertex);
1335 0 : trace2((qh, qh->ferr, 2041, "qh_update_vertexneighbors: delete interior vertex p%d(v%d) of visible f%d\n",
1336 : qh_pointid(qh, vertex->point), vertex->id, visible->id));
1337 : }
1338 : }
1339 : }
1340 : }
1341 : }else { /* !VERTEXneighbors */
1342 0 : trace3((qh, qh->ferr, 3058, "qh_update_vertexneighbors: delete old vertices for qh.visible_list (f%d)\n",
1343 : getid_(qh->visible_list)));
1344 0 : FORALLvisible_facets {
1345 0 : FOREACHvertex_(visible->vertices) {
1346 0 : if (!vertex->newfacet && !vertex->deleted) {
1347 0 : vertex->deleted= True;
1348 0 : qh_setappend(qh, &qh->del_vertices, vertex);
1349 0 : trace2((qh, qh->ferr, 2042, "qh_update_vertexneighbors: will delete interior vertex p%d(v%d) of visible f%d\n",
1350 : qh_pointid(qh, vertex->point), vertex->id, visible->id));
1351 : }
1352 : }
1353 : }
1354 : }
1355 14408 : } /* update_vertexneighbors */
1356 :
1357 : /*-<a href="qh-poly_r.htm#TOC"
1358 : >-------------------------------</a><a name="update_vertexneighbors_cone">-</a>
1359 :
1360 : qh_update_vertexneighbors_cone(qh )
1361 : update vertex neighbors for a cone of new facets and delete interior vertices
1362 :
1363 : returns:
1364 : if qh.VERTEXneighbors,
1365 : if qh.newvertex_list,
1366 : removes visible neighbors from vertex neighbors
1367 : if qh.newfacet_list
1368 : adds new facets to vertex neighbors
1369 : if qh.visible_list
1370 : interior vertices added to qh.del_vertices for later partitioning as coplanar points
1371 : if not qh.VERTEXneighbors (not merging)
1372 : interior vertices of visible facets added to qh.del_vertices for later partitioning as coplanar points
1373 :
1374 : notes
1375 : called by qh_addpoint after create cone and before premerge
1376 :
1377 : design:
1378 : if qh.VERTEXneighbors
1379 : for each vertex on newvertex_list (i.e., new vertices and vertices of new facets)
1380 : delete visible facets from vertex neighbors
1381 : for each new facet on newfacet_list
1382 : for each vertex of facet
1383 : append facet to vertex neighbors
1384 : for each visible facet on qh.visible_list
1385 : for each vertex of facet
1386 : if the vertex is not on a new facet and not itself deleted
1387 : if the vertex has a not-visible neighbor (due to merging)
1388 : remove the visible facet from the vertex's neighbors
1389 : otherwise
1390 : add the vertex to qh.del_vertices for later deletion
1391 :
1392 : if not qh.VERTEXneighbors (not merging)
1393 : for each vertex of a visible facet
1394 : if the vertex is not on a new facet and not itself deleted
1395 : add the vertex to qh.del_vertices for later deletion
1396 :
1397 : */
1398 14660 : void qh_update_vertexneighbors_cone(qhT *qh /* qh.newvertex_list, newfacet_list, visible_list */) {
1399 14660 : facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
1400 : vertexT *vertex, **vertexp;
1401 14660 : int delcount= 0;
1402 :
1403 14660 : if (qh->VERTEXneighbors) {
1404 14650 : trace3((qh, qh->ferr, 3059, "qh_update_vertexneighbors_cone: update v.neighbors for qh.newvertex_list (v%d) and qh.newfacet_list (f%d)\n",
1405 : getid_(qh->newvertex_list), getid_(qh->newfacet_list)));
1406 102662 : FORALLvertex_(qh->newvertex_list) {
1407 88012 : delcount= 0;
1408 503720 : FOREACHneighbor_(vertex) {
1409 415708 : if (neighbor->visible) { /* alternative design is a loop over visible facets, but needs qh_setdel() */
1410 121836 : delcount++;
1411 121836 : qh_setdelnth(qh, vertex->neighbors, SETindex_(vertex->neighbors, neighbor));
1412 121836 : neighborp--; /* repeat */
1413 : }
1414 : }
1415 88012 : if (delcount) {
1416 73362 : trace4((qh, qh->ferr, 4021, "qh_update_vertexneighbors_cone: deleted %d visible vertexneighbors of v%d\n",
1417 : delcount, vertex->id));
1418 : }
1419 : }
1420 88012 : FORALLnew_facets {
1421 293448 : FOREACHvertex_(newfacet->vertices)
1422 220086 : qh_setappend(qh, &vertex->neighbors, newfacet);
1423 : }
1424 14650 : trace3((qh, qh->ferr, 3065, "qh_update_vertexneighbors_cone: delete interior vertices, if any, for qh.visible_list (f%d)\n",
1425 : getid_(qh->visible_list)));
1426 53537 : FORALLvisible_facets {
1427 160723 : FOREACHvertex_(visible->vertices) {
1428 121836 : if (!vertex->newfacet && !vertex->deleted) {
1429 0 : FOREACHneighbor_(vertex) { /* this can happen under merging, qh_checkfacet QH4025 */
1430 0 : if (!neighbor->visible)
1431 0 : break;
1432 : }
1433 0 : if (neighbor)
1434 0 : qh_setdel(vertex->neighbors, visible);
1435 : else {
1436 0 : vertex->deleted= True;
1437 0 : qh_setappend(qh, &qh->del_vertices, vertex);
1438 0 : trace2((qh, qh->ferr, 2102, "qh_update_vertexneighbors_cone: will delete interior vertex p%d(v%d) of visible f%d\n",
1439 : qh_pointid(qh, vertex->point), vertex->id, visible->id));
1440 : }
1441 : }
1442 : }
1443 : }
1444 : }else { /* !VERTEXneighbors */
1445 10 : trace3((qh, qh->ferr, 3066, "qh_update_vertexneighbors_cone: delete interior vertices for qh.visible_list (f%d)\n",
1446 : getid_(qh->visible_list)));
1447 32 : FORALLvisible_facets {
1448 88 : FOREACHvertex_(visible->vertices) {
1449 66 : if (!vertex->newfacet && !vertex->deleted) {
1450 0 : vertex->deleted= True;
1451 0 : qh_setappend(qh, &qh->del_vertices, vertex);
1452 0 : trace2((qh, qh->ferr, 2059, "qh_update_vertexneighbors_cone: will delete interior vertex p%d(v%d) of visible f%d\n",
1453 : qh_pointid(qh, vertex->point), vertex->id, visible->id));
1454 : }
1455 : }
1456 : }
1457 : }
1458 14660 : } /* update_vertexneighbors_cone */
1459 :
|
