00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include "qhull_a.h"
00027
00028 #ifdef USE_DMALLOC
00029 #include "dmalloc.h"
00030 #endif
00031
00032 #ifndef qh_NOmerge
00033
00034
00035
00036 static int qh_compareangle(const void *p1, const void *p2);
00037 static int qh_comparemerge(const void *p1, const void *p2);
00038 static int qh_comparevisit (const void *p1, const void *p2);
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065 void qh_premerge (vertexT *apex, realT maxcentrum, realT maxangle) {
00066 boolT othermerge= False;
00067 facetT *newfacet;
00068
00069 if (qh ZEROcentrum && qh_checkzero(!qh_ALL))
00070 return;
00071 trace2((qh ferr, "qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
00072 maxcentrum, maxangle, apex->id, getid_(qh newfacet_list)));
00073 if (qh IStracing >= 4 && qh num_facets < 50)
00074 qh_printlists();
00075 qh centrum_radius= maxcentrum;
00076 qh cos_max= maxangle;
00077 qh degen_mergeset= qh_settemp (qh TEMPsize);
00078 qh facet_mergeset= qh_settemp (qh TEMPsize);
00079 if (qh hull_dim >=3) {
00080 qh_mark_dupridges (qh newfacet_list);
00081 qh_mergecycle_all (qh newfacet_list, &othermerge);
00082 qh_forcedmerges (&othermerge );
00083 FORALLnew_facets {
00084 if (!newfacet->simplicial && !newfacet->mergeridge)
00085 qh_degen_redundant_neighbors (newfacet, NULL);
00086 }
00087 if (qh_merge_degenredundant())
00088 othermerge= True;
00089 }else
00090 qh_mergecycle_all (qh newfacet_list, &othermerge);
00091 qh_flippedmerges (qh newfacet_list, &othermerge);
00092 if (!qh MERGEexact || zzval_(Ztotmerge)) {
00093 zinc_(Zpremergetot);
00094 qh POSTmerging= False;
00095 qh_getmergeset_initial (qh newfacet_list);
00096 qh_all_merges (othermerge, False);
00097 }
00098 qh_settempfree(&qh facet_mergeset);
00099 qh_settempfree(&qh degen_mergeset);
00100 }
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138 void qh_postmerge (char *reason, realT maxcentrum, realT maxangle,
00139 boolT vneighbors) {
00140 facetT *newfacet;
00141 boolT othermerges= False;
00142 vertexT *vertex;
00143
00144 if (qh REPORTfreq || qh IStracing) {
00145 qh_buildtracing (NULL, NULL);
00146 qh_printsummary (qh ferr);
00147 if (qh PRINTstatistics)
00148 qh_printallstatistics (qh ferr, "reason");
00149 fprintf (qh ferr, "\n%s with 'C%.2g' and 'A%.2g'\n",
00150 reason, maxcentrum, maxangle);
00151 }
00152 trace2((qh ferr, "qh_postmerge: postmerge. test vneighbors? %d\n",
00153 vneighbors));
00154 qh centrum_radius= maxcentrum;
00155 qh cos_max= maxangle;
00156 qh POSTmerging= True;
00157 qh degen_mergeset= qh_settemp (qh TEMPsize);
00158 qh facet_mergeset= qh_settemp (qh TEMPsize);
00159 if (qh visible_list != qh facet_list) {
00160 qh NEWfacets= True;
00161 qh visible_list= qh newfacet_list= qh facet_list;
00162 FORALLnew_facets {
00163 newfacet->newfacet= True;
00164 if (!newfacet->simplicial)
00165 newfacet->newmerge= True;
00166 zinc_(Zpostfacets);
00167 }
00168 qh newvertex_list= qh vertex_list;
00169 FORALLvertices
00170 vertex->newlist= True;
00171 if (qh VERTEXneighbors) {
00172 FORALLvertices
00173 vertex->delridge= True;
00174 if (qh MERGEexact) {
00175 if (qh hull_dim <= qh_DIMreduceBuild)
00176 qh_reducevertices();
00177 }
00178 }
00179 if (!qh PREmerge && !qh MERGEexact)
00180 qh_flippedmerges (qh newfacet_list, &othermerges);
00181 }
00182 qh_getmergeset_initial (qh newfacet_list);
00183 qh_all_merges (False, vneighbors);
00184 qh_settempfree(&qh facet_mergeset);
00185 qh_settempfree(&qh degen_mergeset);
00186 }
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224 void qh_all_merges (boolT othermerge, boolT vneighbors) {
00225 facetT *facet1, *facet2;
00226 mergeT *merge;
00227 boolT wasmerge= True, isreduce;
00228 void **freelistp;
00229 vertexT *vertex;
00230 mergeType mergetype;
00231 int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
00232
00233 trace2((qh ferr, "qh_all_merges: starting to merge facets beginning from f%d\n",
00234 getid_(qh newfacet_list)));
00235 while (True) {
00236 wasmerge= False;
00237 while (qh_setsize (qh facet_mergeset)) {
00238 while ((merge= (mergeT*)qh_setdellast(qh facet_mergeset))) {
00239 facet1= merge->facet1;
00240 facet2= merge->facet2;
00241 mergetype= merge->type;
00242 qh_memfree_(merge, sizeof(mergeT), freelistp);
00243 if (facet1->visible || facet2->visible)
00244 continue;
00245 if ((facet1->newfacet && !facet1->tested)
00246 || (facet2->newfacet && !facet2->tested)) {
00247 if (qh MERGEindependent && mergetype <= MRGanglecoplanar)
00248 continue;
00249 }
00250 qh_merge_nonconvex (facet1, facet2, mergetype);
00251 numdegenredun += qh_merge_degenredundant();
00252 numnewmerges++;
00253 wasmerge= True;
00254 if (mergetype == MRGconcave)
00255 numconcave++;
00256 else
00257 numcoplanar++;
00258 }
00259 if (qh POSTmerging && qh hull_dim <= qh_DIMreduceBuild
00260 && numnewmerges > qh_MAXnewmerges) {
00261 numnewmerges= 0;
00262 qh_reducevertices();
00263 }
00264 qh_getmergeset (qh newfacet_list);
00265 }
00266 if (qh VERTEXneighbors) {
00267 isreduce= False;
00268 if (qh hull_dim >=4 && qh POSTmerging) {
00269 FORALLvertices
00270 vertex->delridge= True;
00271 isreduce= True;
00272 }
00273 if ((wasmerge || othermerge) && (!qh MERGEexact || qh POSTmerging)
00274 && qh hull_dim <= qh_DIMreduceBuild) {
00275 othermerge= False;
00276 isreduce= True;
00277 }
00278 if (isreduce) {
00279 if (qh_reducevertices()) {
00280 qh_getmergeset (qh newfacet_list);
00281 continue;
00282 }
00283 }
00284 }
00285 if (vneighbors && qh_test_vneighbors())
00286 continue;
00287 break;
00288 }
00289 if (qh CHECKfrequently && !qh MERGEexact) {
00290 qh old_randomdist= qh RANDOMdist;
00291 qh RANDOMdist= False;
00292 qh_checkconvex (qh newfacet_list, qh_ALGORITHMfault);
00293
00294 qh RANDOMdist= qh old_randomdist;
00295 }
00296 trace1((qh ferr, "qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
00297 numcoplanar, numconcave, numdegenredun));
00298 if (qh IStracing >= 4 && qh num_facets < 50)
00299 qh_printlists ();
00300 }
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329 void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle) {
00330 mergeT *merge, *lastmerge;
00331 void **freelistp;
00332
00333 if (facet->redundant)
00334 return;
00335 if (facet->degenerate && mergetype == MRGdegen)
00336 return;
00337 qh_memalloc_(sizeof(mergeT), freelistp, merge, mergeT);
00338 merge->facet1= facet;
00339 merge->facet2= neighbor;
00340 merge->type= mergetype;
00341 if (angle && qh ANGLEmerge)
00342 merge->angle= *angle;
00343 if (mergetype < MRGdegen)
00344 qh_setappend (&(qh facet_mergeset), merge);
00345 else if (mergetype == MRGdegen) {
00346 facet->degenerate= True;
00347 if (!(lastmerge= (mergeT*)qh_setlast (qh degen_mergeset))
00348 || lastmerge->type == MRGdegen)
00349 qh_setappend (&(qh degen_mergeset), merge);
00350 else
00351 qh_setaddnth (&(qh degen_mergeset), 0, merge);
00352 }else {
00353 facet->redundant= True;
00354 qh_setappend (&(qh degen_mergeset), merge);
00355 }
00356 }
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379 setT *qh_basevertices (facetT *samecycle) {
00380 facetT *same;
00381 vertexT *apex, *vertex, **vertexp;
00382 setT *vertices= qh_settemp (qh TEMPsize);
00383
00384 apex= SETfirstt_(samecycle->vertices, vertexT);
00385 apex->visitid= ++qh vertex_visit;
00386 FORALLsame_cycle_(samecycle) {
00387 if (same->mergeridge)
00388 continue;
00389 FOREACHvertex_(same->vertices) {
00390 if (vertex->visitid != qh vertex_visit) {
00391 qh_setappend (&vertices, vertex);
00392 vertex->visitid= qh vertex_visit;
00393 vertex->seen= False;
00394 }
00395 }
00396 }
00397 trace4((qh ferr, "qh_basevertices: found %d vertices\n",
00398 qh_setsize (vertices)));
00399 return vertices;
00400 }
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419
00420 void qh_checkconnect (void ) {
00421 facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;
00422
00423 facet= qh newfacet_list;
00424 qh_removefacet (facet);
00425 qh_appendfacet (facet);
00426 facet->visitid= ++qh visit_id;
00427 FORALLfacet_(facet) {
00428 FOREACHneighbor_(facet) {
00429 if (neighbor->visitid != qh visit_id) {
00430 qh_removefacet (neighbor);
00431 qh_appendfacet (neighbor);
00432 neighbor->visitid= qh visit_id;
00433 }
00434 }
00435 }
00436 FORALLnew_facets {
00437 if (newfacet->visitid == qh visit_id)
00438 break;
00439 fprintf(qh ferr, "qhull error: f%d is not attached to the new facets\n",
00440 newfacet->id);
00441 errfacet= newfacet;
00442 }
00443 if (errfacet)
00444 qh_errexit (qh_ERRqhull, errfacet, NULL);
00445 }
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483 boolT qh_checkzero (boolT testall) {
00484 facetT *facet, *neighbor, **neighborp;
00485 facetT *horizon, *facetlist;
00486 int neighbor_i;
00487 vertexT *vertex, **vertexp;
00488 realT dist;
00489
00490 if (testall)
00491 facetlist= qh facet_list;
00492 else {
00493 facetlist= qh newfacet_list;
00494 FORALLfacet_(facetlist) {
00495 horizon= SETfirstt_(facet->neighbors, facetT);
00496 if (!horizon->simplicial)
00497 goto LABELproblem;
00498 if (facet->flipped || facet->dupridge || !facet->normal)
00499 goto LABELproblem;
00500 }
00501 if (qh MERGEexact && qh ZEROall_ok) {
00502 trace2((qh ferr, "qh_checkzero: skip convexity check until first pre-merge\n"));
00503 return True;
00504 }
00505 }
00506 FORALLfacet_(facetlist) {
00507 qh vertex_visit++;
00508 neighbor_i= 0;
00509 horizon= NULL;
00510 FOREACHneighbor_(facet) {
00511 if (!neighbor_i && !testall) {
00512 horizon= neighbor;
00513 neighbor_i++;
00514 continue;
00515 }
00516 vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
00517 vertex->visitid= qh vertex_visit;
00518 zzinc_(Zdistzero);
00519 qh_distplane (vertex->point, neighbor, &dist);
00520 if (dist >= -qh DISTround) {
00521 qh ZEROall_ok= False;
00522 if (!qh MERGEexact || testall || dist > qh DISTround)
00523 goto LABELnonconvex;
00524 }
00525 }
00526 if (!testall) {
00527 FOREACHvertex_(horizon->vertices) {
00528 if (vertex->visitid != qh vertex_visit) {
00529 zzinc_(Zdistzero);
00530 qh_distplane (vertex->point, facet, &dist);
00531 if (dist >= -qh DISTround) {
00532 qh ZEROall_ok= False;
00533 if (!qh MERGEexact || dist > qh DISTround)
00534 goto LABELnonconvex;
00535 }
00536 break;
00537 }
00538 }
00539 }
00540 }
00541 trace2((qh ferr, "qh_checkzero: facets are %s\n",
00542 (qh MERGEexact && !testall) ?
00543 "not concave, flipped, or duplicate ridged" : "clearly convex"));
00544 return True;
00545
00546 LABELproblem:
00547 qh ZEROall_ok= False;
00548 trace2((qh ferr, "qh_checkzero: facet f%d needs pre-merging\n",
00549 facet->id));
00550 return False;
00551
00552 LABELnonconvex:
00553 trace2((qh ferr, "qh_checkzero: facet f%d and f%d are not clearly convex. v%d dist %.2g\n",
00554 facet->id, neighbor->id, vertex->id, dist));
00555 return False;
00556 }
00557
00558
00559
00560
00561
00562
00563
00564 static int qh_compareangle(const void *p1, const void *p2) {
00565 mergeT *a= *((mergeT **)p1), *b= *((mergeT **)p2);
00566
00567 return ((a->angle > b->angle) ? 1 : -1);
00568 }
00569
00570
00571
00572
00573
00574
00575
00576 static int qh_comparemerge(const void *p1, const void *p2) {
00577 mergeT *a= *((mergeT **)p1), *b= *((mergeT **)p2);
00578
00579 return (a->type - b->type);
00580 }
00581
00582
00583
00584
00585
00586
00587
00588 static int qh_comparevisit (const void *p1, const void *p2) {
00589 vertexT *a= *((vertexT **)p1), *b= *((vertexT **)p2);
00590
00591 return (a->visitid - b->visitid);
00592 }
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608 void qh_copynonconvex (ridgeT *atridge) {
00609 facetT *facet, *otherfacet;
00610 ridgeT *ridge, **ridgep;
00611
00612 facet= atridge->top;
00613 otherfacet= atridge->bottom;
00614 FOREACHridge_(facet->ridges) {
00615 if (otherfacet == otherfacet_(ridge, facet) && ridge != atridge) {
00616 ridge->nonconvex= True;
00617 trace4((qh ferr, "qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",
00618 atridge->id, ridge->id));
00619 break;
00620 }
00621 }
00622 }
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642 void qh_degen_redundant_facet (facetT *facet) {
00643 vertexT *vertex, **vertexp;
00644 facetT *neighbor, **neighborp;
00645
00646 trace4((qh ferr, "qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
00647 facet->id));
00648 FOREACHneighbor_(facet) {
00649 qh vertex_visit++;
00650 FOREACHvertex_(neighbor->vertices)
00651 vertex->visitid= qh vertex_visit;
00652 FOREACHvertex_(facet->vertices) {
00653 if (vertex->visitid != qh vertex_visit)
00654 break;
00655 }
00656 if (!vertex) {
00657 qh_appendmergeset (facet, neighbor, MRGredundant, NULL);
00658 trace2((qh ferr, "qh_degen_redundant_facet: f%d is contained in f%d. merge\n", facet->id, neighbor->id));
00659 return;
00660 }
00661 }
00662 if (qh_setsize (facet->neighbors) < qh hull_dim) {
00663 qh_appendmergeset (facet, facet, MRGdegen, NULL);
00664 trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));
00665 }
00666 }
00667
00668
00669
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698 void qh_degen_redundant_neighbors (facetT *facet, facetT *delfacet) {
00699 vertexT *vertex, **vertexp;
00700 facetT *neighbor, **neighborp;
00701 int size;
00702
00703 trace4((qh ferr, "qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n",
00704 facet->id, getid_(delfacet)));
00705 if ((size= qh_setsize (facet->neighbors)) < qh hull_dim) {
00706 qh_appendmergeset (facet, facet, MRGdegen, NULL);
00707 trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.\n", facet->id, size));
00708 }
00709 if (!delfacet)
00710 delfacet= facet;
00711 qh vertex_visit++;
00712 FOREACHvertex_(facet->vertices)
00713 vertex->visitid= qh vertex_visit;
00714 FOREACHneighbor_(delfacet) {
00715
00716 if (neighbor == facet)
00717 continue;
00718 FOREACHvertex_(neighbor->vertices) {
00719 if (vertex->visitid != qh vertex_visit)
00720 break;
00721 }
00722 if (!vertex) {
00723 qh_appendmergeset (neighbor, facet, MRGredundant, NULL);
00724 trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is contained in f%d. merge\n", neighbor->id, facet->id));
00725 }
00726 }
00727 FOREACHneighbor_(delfacet) {
00728 if (neighbor == facet)
00729 continue;
00730 if ((size= qh_setsize (neighbor->neighbors)) < qh hull_dim) {
00731 qh_appendmergeset (neighbor, neighbor, MRGdegen, NULL);
00732 trace2((qh ferr, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors. Neighbor of f%d.\n", neighbor->id, size, facet->id));
00733 }
00734 }
00735 }
00736
00737
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768 vertexT *qh_find_newvertex (vertexT *oldvertex, setT *vertices, setT *ridges) {
00769 vertexT *vertex, **vertexp;
00770 setT *newridges;
00771 ridgeT *ridge, **ridgep;
00772 int size, hashsize;
00773 int hash;
00774
00775 #ifndef qh_NOtrace
00776 if (qh IStracing >= 4) {
00777 fprintf (qh ferr, "qh_find_newvertex: find new vertex for v%d from ",
00778 oldvertex->id);
00779 FOREACHvertex_(vertices)
00780 fprintf (qh ferr, "v%d ", vertex->id);
00781 FOREACHridge_(ridges)
00782 fprintf (qh ferr, "r%d ", ridge->id);
00783 fprintf (qh ferr, "\n");
00784 }
00785 #endif
00786 FOREACHvertex_(vertices)
00787 vertex->visitid= 0;
00788 FOREACHridge_(ridges) {
00789 FOREACHvertex_(ridge->vertices)
00790 vertex->visitid++;
00791 }
00792 FOREACHvertex_(vertices) {
00793 if (!vertex->visitid) {
00794 qh_setdelnth (vertices, SETindex_(vertices,vertex));
00795 vertexp--;
00796 }
00797 }
00798 qh vertex_visit += qh_setsize (ridges);
00799 if (!qh_setsize (vertices)) {
00800 trace4((qh ferr, "qh_find_newvertex: vertices not in ridges for v%d\n",
00801 oldvertex->id));
00802 return NULL;
00803 }
00804 qsort (SETaddr_(vertices, vertexT), qh_setsize (vertices),
00805 sizeof (vertexT *), qh_comparevisit);
00806
00807 if (qh PRINTstatistics) {
00808 size= qh_setsize (vertices);
00809 zinc_(Zintersect);
00810 zadd_(Zintersecttot, size);
00811 zmax_(Zintersectmax, size);
00812 }
00813 hashsize= qh_newhashtable (qh_setsize (ridges));
00814 FOREACHridge_(ridges)
00815 qh_hashridge (qh hash_table, hashsize, ridge, oldvertex);
00816 FOREACHvertex_(vertices) {
00817 newridges= qh_vertexridges (vertex);
00818 FOREACHridge_(newridges) {
00819 if (qh_hashridge_find (qh hash_table, hashsize, ridge, vertex, oldvertex, &hash)) {
00820 zinc_(Zdupridge);
00821 break;
00822 }
00823 }
00824 qh_settempfree (&newridges);
00825 if (!ridge)
00826 break;
00827 }
00828 if (vertex) {
00829
00830 trace2((qh ferr, "qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
00831 vertex->id, oldvertex->id, qh_setsize (vertices), qh_setsize (ridges)));
00832 }else {
00833 zinc_(Zfindfail);
00834 trace0((qh ferr, "qh_find_newvertex: no vertex for renaming v%d (all duplicated ridges) during p%d\n",
00835 oldvertex->id, qh furthest_id));
00836 }
00837 qh_setfree (&qh hash_table);
00838 return vertex;
00839 }
00840
00841
00842
00843
00844
00845
00846
00847
00848
00849
00850
00851
00852
00853
00854
00855 void qh_findbest_test (boolT testcentrum, facetT *facet, facetT *neighbor,
00856 facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp) {
00857 realT dist=0.0, mindist=0.0, maxdist=0.0;
00858
00859 if (testcentrum) {
00860 zzinc_(Zbestdist);
00861 qh_distplane(facet->center, neighbor, &dist);
00862 dist *= qh hull_dim;
00863 if (dist < 0) {
00864 maxdist= 0;
00865 mindist= dist;
00866 dist= -dist;
00867 }else {
00868 maxdist= dist;
00869 }
00870 }else {
00871 dist= qh_getdistance (facet, neighbor, &mindist, &maxdist);
00872 }
00873 if (dist < *distp) {
00874 *bestfacet= neighbor;
00875 *mindistp= mindist;
00876 *maxdistp= maxdist;
00877 *distp= dist;
00878 }
00879 }
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907 facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp) {
00908 facetT *neighbor, **neighborp, *bestfacet= NULL;
00909 ridgeT *ridge, **ridgep;
00910 boolT nonconvex= True, testcentrum= False;
00911 int size= qh_setsize (facet->vertices);
00912
00913 *distp= REALmax;
00914 if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {
00915 testcentrum= True;
00916 zinc_(Zbestcentrum);
00917 if (!facet->center)
00918 facet->center= qh_getcentrum (facet);
00919 }
00920 if (size > qh hull_dim + qh_BESTnonconvex) {
00921 FOREACHridge_(facet->ridges) {
00922 if (ridge->nonconvex) {
00923 neighbor= otherfacet_(ridge, facet);
00924 qh_findbest_test (testcentrum, facet, neighbor,
00925 &bestfacet, distp, mindistp, maxdistp);
00926 }
00927 }
00928 }
00929 if (!bestfacet) {
00930 nonconvex= False;
00931 FOREACHneighbor_(facet)
00932 qh_findbest_test (testcentrum, facet, neighbor,
00933 &bestfacet, distp, mindistp, maxdistp);
00934 }
00935 if (!bestfacet) {
00936 fprintf (qh ferr, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);
00937
00938 qh_errexit (qh_ERRqhull, facet, NULL);
00939 }
00940 if (testcentrum)
00941 qh_getdistance (facet, bestfacet, mindistp, maxdistp);
00942 trace3((qh ferr, "qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
00943 bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
00944 return(bestfacet);
00945 }
00946
00947
00948
00949
00950
00951
00952
00953
00954
00955
00956
00957
00958
00959
00960
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971
00972 void qh_flippedmerges(facetT *facetlist, boolT *wasmerge) {
00973 facetT *facet, *neighbor, *facet1;
00974 realT dist, mindist, maxdist;
00975 mergeT *merge, **mergep;
00976 setT *othermerges;
00977 int nummerge=0;
00978
00979 trace4((qh ferr, "qh_flippedmerges: begin\n"));
00980 FORALLfacet_(facetlist) {
00981 if (facet->flipped && !facet->visible)
00982 qh_appendmergeset (facet, facet, MRGflip, NULL);
00983 }
00984 othermerges= qh_settemppop();
00985 qh facet_mergeset= qh_settemp (qh TEMPsize);
00986 qh_settemppush (othermerges);
00987 FOREACHmerge_(othermerges) {
00988 facet1= merge->facet1;
00989 if (merge->type != MRGflip || facet1->visible)
00990 continue;
00991 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
00992 qhmem.IStracing= qh IStracing= qh TRACElevel;
00993 neighbor= qh_findbestneighbor (facet1, &dist, &mindist, &maxdist);
00994 trace0((qh ferr, "qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
00995 facet1->id, neighbor->id, dist, qh furthest_id));
00996 qh_mergefacet (facet1, neighbor, &mindist, &maxdist, !qh_MERGEapex);
00997 nummerge++;
00998 if (qh PRINTstatistics) {
00999 zinc_(Zflipped);
01000 wadd_(Wflippedtot, dist);
01001 wmax_(Wflippedmax, dist);
01002 }
01003 qh_merge_degenredundant();
01004 }
01005 FOREACHmerge_(othermerges) {
01006 if (merge->facet1->visible || merge->facet2->visible)
01007 qh_memfree (merge, sizeof(mergeT));
01008 else
01009 qh_setappend (&qh facet_mergeset, merge);
01010 }
01011 qh_settempfree (&othermerges);
01012 if (nummerge)
01013 *wasmerge= True;
01014 trace1((qh ferr, "qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
01015 }
01016
01017
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044
01045 void qh_forcedmerges(boolT *wasmerge) {
01046 facetT *facet1, *facet2;
01047 mergeT *merge, **mergep;
01048 realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
01049 setT *othermerges;
01050 int nummerge=0, numflip=0;
01051
01052 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01053 qhmem.IStracing= qh IStracing= qh TRACElevel;
01054 trace4((qh ferr, "qh_forcedmerges: begin\n"));
01055 othermerges= qh_settemppop();
01056 qh facet_mergeset= qh_settemp (qh TEMPsize);
01057 qh_settemppush (othermerges);
01058 FOREACHmerge_(othermerges) {
01059 if (merge->type != MRGridge)
01060 continue;
01061 facet1= merge->facet1;
01062 facet2= merge->facet2;
01063 while (facet1->visible)
01064 facet1= facet1->f.replace;
01065 while (facet2->visible)
01066 facet2= facet2->f.replace;
01067 if (facet1 == facet2)
01068 continue;
01069 if (!qh_setin (facet2->neighbors, facet1)) {
01070 fprintf (qh ferr, "qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
01071 merge->facet1->id, merge->facet2->id, facet1->id, facet2->id);
01072 qh_errexit2 (qh_ERRqhull, facet1, facet2);
01073 }
01074 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01075 qhmem.IStracing= qh IStracing= qh TRACElevel;
01076 dist1= qh_getdistance (facet1, facet2, &mindist1, &maxdist1);
01077 dist2= qh_getdistance (facet2, facet1, &mindist2, &maxdist2);
01078 trace0((qh ferr, "qh_forcedmerges: duplicate ridge between f%d and f%d, dist %2.2g and reverse dist %2.2g during p%d\n",
01079 facet1->id, facet2->id, dist1, dist2, qh furthest_id));
01080 if (dist1 < dist2)
01081 qh_mergefacet (facet1, facet2, &mindist1, &maxdist1, !qh_MERGEapex);
01082 else {
01083 qh_mergefacet (facet2, facet1, &mindist2, &maxdist2, !qh_MERGEapex);
01084 dist1= dist2;
01085 facet1= facet2;
01086 }
01087 if (facet1->flipped) {
01088 zinc_(Zmergeflipdup);
01089 numflip++;
01090 }else
01091 nummerge++;
01092 if (qh PRINTstatistics) {
01093 zinc_(Zduplicate);
01094 wadd_(Wduplicatetot, dist1);
01095 wmax_(Wduplicatemax, dist1);
01096 }
01097 }
01098 FOREACHmerge_(othermerges) {
01099 if (merge->type == MRGridge)
01100 qh_memfree (merge, sizeof(mergeT));
01101 else
01102 qh_setappend (&qh facet_mergeset, merge);
01103 }
01104 qh_settempfree (&othermerges);
01105 if (nummerge)
01106 *wasmerge= True;
01107 trace1((qh ferr, "qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
01108 nummerge, numflip));
01109 }
01110
01111
01112
01113
01114
01115
01116
01117
01118
01119
01120
01121
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
01136
01137
01138
01139
01140
01141 void qh_getmergeset(facetT *facetlist) {
01142 facetT *facet, *neighbor, **neighborp;
01143 ridgeT *ridge, **ridgep;
01144 int nummerges;
01145
01146 nummerges= qh_setsize (qh facet_mergeset);
01147 trace4((qh ferr, "qh_getmergeset: started.\n"));
01148 qh visit_id++;
01149 FORALLfacet_(facetlist) {
01150 if (facet->tested)
01151 continue;
01152 facet->visitid= qh visit_id;
01153 facet->tested= True;
01154 FOREACHneighbor_(facet)
01155 neighbor->seen= False;
01156 FOREACHridge_(facet->ridges) {
01157 if (ridge->tested && !ridge->nonconvex)
01158 continue;
01159
01160 neighbor= otherfacet_(ridge, facet);
01161 if (neighbor->seen) {
01162 ridge->tested= True;
01163 ridge->nonconvex= False;
01164 }else if (neighbor->visitid != qh visit_id) {
01165 ridge->tested= True;
01166 ridge->nonconvex= False;
01167 neighbor->seen= True;
01168 if (qh_test_appendmerge (facet, neighbor))
01169 ridge->nonconvex= True;
01170 }
01171 }
01172 }
01173 nummerges= qh_setsize (qh facet_mergeset);
01174 if (qh ANGLEmerge)
01175 qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_compareangle);
01176 else
01177 qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_comparemerge);
01178 if (qh POSTmerging) {
01179 zadd_(Zmergesettot2, nummerges);
01180 }else {
01181 zadd_(Zmergesettot, nummerges);
01182 zmax_(Zmergesetmax, nummerges);
01183 }
01184 trace2((qh ferr, "qh_getmergeset: %d merges found\n", nummerges));
01185 }
01186
01187
01188
01189
01190
01191
01192
01193
01194
01195
01196
01197
01198
01199
01200
01201
01202
01203
01204
01205
01206
01207
01208
01209
01210
01211
01212
01213
01214 void qh_getmergeset_initial (facetT *facetlist) {
01215 facetT *facet, *neighbor, **neighborp;
01216 ridgeT *ridge, **ridgep;
01217 int nummerges;
01218
01219 qh visit_id++;
01220 FORALLfacet_(facetlist) {
01221 facet->visitid= qh visit_id;
01222 facet->tested= True;
01223 FOREACHneighbor_(facet) {
01224 if (neighbor->visitid != qh visit_id) {
01225 if (qh_test_appendmerge (facet, neighbor)) {
01226 FOREACHridge_(neighbor->ridges) {
01227 if (facet == otherfacet_(ridge, neighbor)) {
01228 ridge->nonconvex= True;
01229 break;
01230 }
01231 }
01232 }
01233 }
01234 }
01235 FOREACHridge_(facet->ridges)
01236 ridge->tested= True;
01237 }
01238 nummerges= qh_setsize (qh facet_mergeset);
01239 if (qh ANGLEmerge)
01240 qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_compareangle);
01241 else
01242 qsort(SETaddr_(qh facet_mergeset, mergeT), nummerges,sizeof(mergeT *),qh_comparemerge);
01243 if (qh POSTmerging) {
01244 zadd_(Zmergeinittot2, nummerges);
01245 }else {
01246 zadd_(Zmergeinittot, nummerges);
01247 zmax_(Zmergeinitmax, nummerges);
01248 }
01249 trace2((qh ferr, "qh_getmergeset_initial: %d merges found\n", nummerges));
01250 }
01251
01252
01253
01254
01255
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265
01266 void qh_hashridge (setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex) {
01267 int hash;
01268 ridgeT *ridgeA;
01269
01270 hash= (int)qh_gethash (hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
01271 while (True) {
01272 if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
01273 SETelem_(hashtable, hash)= ridge;
01274 break;
01275 }else if (ridgeA == ridge)
01276 break;
01277 if (++hash == hashsize)
01278 hash= 0;
01279 }
01280 }
01281
01282
01283
01284
01285
01286
01287
01288
01289
01290
01291
01292
01293
01294
01295
01296
01297
01298
01299
01300
01301
01302
01303
01304
01305
01306
01307
01308
01309 ridgeT *qh_hashridge_find (setT *hashtable, int hashsize, ridgeT *ridge,
01310 vertexT *vertex, vertexT *oldvertex, int *hashslot) {
01311 int hash;
01312 ridgeT *ridgeA;
01313
01314 *hashslot= 0;
01315 zinc_(Zhashridge);
01316 hash= (int)qh_gethash (hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
01317 while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
01318 if (ridgeA == ridge)
01319 *hashslot= -1;
01320 else {
01321 zinc_(Zhashridgetest);
01322 if (qh_setequal_except (ridge->vertices, vertex, ridgeA->vertices, oldvertex))
01323 return ridgeA;
01324 }
01325 if (++hash == hashsize)
01326 hash= 0;
01327 }
01328 if (!*hashslot)
01329 *hashslot= hash;
01330 return NULL;
01331 }
01332
01333
01334
01335
01336
01337
01338
01339
01340
01341
01342
01343
01344
01345
01346
01347
01348
01349
01350
01351
01352
01353
01354
01355
01356
01357
01358
01359
01360 void qh_makeridges(facetT *facet) {
01361 facetT *neighbor, **neighborp;
01362 ridgeT *ridge, **ridgep;
01363 int neighbor_i, neighbor_n;
01364 boolT toporient, mergeridge= False;
01365
01366 if (!facet->simplicial)
01367 return;
01368 trace4((qh ferr, "qh_makeridges: make ridges for f%d\n", facet->id));
01369 facet->simplicial= False;
01370 FOREACHneighbor_(facet) {
01371 if (neighbor == qh_MERGEridge)
01372 mergeridge= True;
01373 else
01374 neighbor->seen= False;
01375 }
01376 FOREACHridge_(facet->ridges)
01377 otherfacet_(ridge, facet)->seen= True;
01378 FOREACHneighbor_i_(facet) {
01379 if (neighbor == qh_MERGEridge)
01380 continue;
01381 else if (!neighbor->seen) {
01382 ridge= qh_newridge();
01383 ridge->vertices= qh_setnew_delnthsorted (facet->vertices, qh hull_dim,
01384 neighbor_i, 0);
01385 toporient= facet->toporient ^ (neighbor_i & 0x1);
01386 if (toporient) {
01387 ridge->top= facet;
01388 ridge->bottom= neighbor;
01389 }else {
01390 ridge->top= neighbor;
01391 ridge->bottom= facet;
01392 }
01393 #if 0
01394 flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
01395 if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
01396 ridge->top= neighbor;
01397 ridge->bottom= facet;
01398 }else {
01399 ridge->top= facet;
01400 ridge->bottom= neighbor;
01401 }
01402 #endif
01403 qh_setappend(&(facet->ridges), ridge);
01404 qh_setappend(&(neighbor->ridges), ridge);
01405 }
01406 }
01407 if (mergeridge) {
01408 while (qh_setdel (facet->neighbors, qh_MERGEridge))
01409 ;
01410 }
01411 }
01412
01413
01414
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426
01427
01428
01429
01430
01431
01432
01433
01434
01435
01436
01437
01438
01439
01440
01441
01442
01443
01444
01445
01446
01447
01448
01449
01450 void qh_mark_dupridges(facetT *facetlist) {
01451 facetT *facet, *neighbor, **neighborp;
01452 int nummerge=0;
01453 mergeT *merge, **mergep;
01454
01455
01456 trace4((qh ferr, "qh_mark_dupridges: identify duplicate ridges\n"));
01457 FORALLfacet_(facetlist) {
01458 if (facet->dupridge) {
01459 FOREACHneighbor_(facet) {
01460 if (neighbor == qh_MERGEridge) {
01461 facet->mergeridge= True;
01462 continue;
01463 }
01464 if (neighbor->dupridge
01465 && !qh_setin (neighbor->neighbors, facet)) {
01466 qh_appendmergeset (facet, neighbor, MRGridge, NULL);
01467 facet->mergeridge2= True;
01468 facet->mergeridge= True;
01469 nummerge++;
01470 }
01471 }
01472 }
01473 }
01474 if (!nummerge)
01475 return;
01476 FORALLfacet_(facetlist) {
01477 if (facet->mergeridge && !facet->mergeridge2)
01478 qh_makeridges (facet);
01479 }
01480 FOREACHmerge_(qh facet_mergeset) {
01481 if (merge->type == MRGridge) {
01482 qh_setappend (&merge->facet2->neighbors, merge->facet1);
01483 qh_makeridges (merge->facet1);
01484 }
01485 }
01486 trace1((qh ferr, "qh_mark_dupridges: found %d duplicated ridges\n",
01487 nummerge));
01488 }
01489
01490
01491
01492
01493
01494
01495
01496
01497
01498
01499
01500
01501
01502
01503
01504
01505
01506
01507
01508
01509
01510
01511
01512
01513
01514 void qh_maydropneighbor (facetT *facet) {
01515 ridgeT *ridge, **ridgep;
01516 realT angledegen= qh_ANGLEdegen;
01517 facetT *neighbor, **neighborp;
01518
01519 qh visit_id++;
01520 trace4((qh ferr, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
01521 facet->id));
01522 FOREACHridge_(facet->ridges) {
01523 ridge->top->visitid= qh visit_id;
01524 ridge->bottom->visitid= qh visit_id;
01525 }
01526 FOREACHneighbor_(facet) {
01527 if (neighbor->visitid != qh visit_id) {
01528 trace0((qh ferr, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
01529 facet->id, neighbor->id, qh furthest_id));
01530 zinc_(Zdropneighbor);
01531 qh_setdel (facet->neighbors, neighbor);
01532 neighborp--;
01533 qh_setdel (neighbor->neighbors, facet);
01534 if (qh_setsize (neighbor->neighbors) < qh hull_dim) {
01535 zinc_(Zdropdegen);
01536 qh_appendmergeset (neighbor, neighbor, MRGdegen, &angledegen);
01537 trace2((qh ferr, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
01538 }
01539 }
01540 }
01541 if (qh_setsize (facet->neighbors) < qh hull_dim) {
01542 zinc_(Zdropdegen);
01543 qh_appendmergeset (facet, facet, MRGdegen, &angledegen);
01544 trace2((qh ferr, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
01545 }
01546 }
01547
01548
01549
01550
01551
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561
01562
01563
01564
01565
01566
01567
01568
01569
01570
01571
01572
01573
01574 int qh_merge_degenredundant (void) {
01575 int size;
01576 mergeT *merge;
01577 facetT *bestneighbor, *facet1, *facet2;
01578 realT dist, mindist, maxdist;
01579 vertexT *vertex, **vertexp;
01580 int nummerges= 0;
01581 mergeType mergetype;
01582
01583 while ((merge= (mergeT*)qh_setdellast (qh degen_mergeset))) {
01584 facet1= merge->facet1;
01585 facet2= merge->facet2;
01586 mergetype= merge->type;
01587 qh_memfree (merge, sizeof(mergeT));
01588 if (facet1->visible)
01589 continue;
01590 facet1->degenerate= False;
01591 facet1->redundant= False;
01592 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01593 qhmem.IStracing= qh IStracing= qh TRACElevel;
01594 if (mergetype == MRGredundant) {
01595 zinc_(Zneighbor);
01596 while (facet2->visible) {
01597 if (!facet2->f.replace) {
01598 fprintf (qh ferr, "qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
01599 facet1->id, facet2->id);
01600 qh_errexit2 (qh_ERRqhull, facet1, facet2);
01601 }
01602 facet2= facet2->f.replace;
01603 }
01604 if (facet1 == facet2) {
01605 qh_degen_redundant_facet (facet1);
01606 continue;
01607 }
01608 trace2((qh ferr, "qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
01609 facet1->id, facet2->id));
01610 qh_mergefacet(facet1, facet2, NULL, NULL, !qh_MERGEapex);
01611
01612 nummerges++;
01613 }else {
01614 if (!(size= qh_setsize (facet1->neighbors))) {
01615 zinc_(Zdelfacetdup);
01616 trace2((qh ferr, "qh_merge_degenredundant: facet f%d has no neighbors. Deleted\n", facet1->id));
01617 qh_willdelete (facet1, NULL);
01618 FOREACHvertex_(facet1->vertices) {
01619 qh_setdel (vertex->neighbors, facet1);
01620 if (!SETfirst_(vertex->neighbors)) {
01621 zinc_(Zdegenvertex);
01622 trace2((qh ferr, "qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
01623 vertex->id, facet1->id));
01624 vertex->deleted= True;
01625 qh_setappend (&qh del_vertices, vertex);
01626 }
01627 }
01628 nummerges++;
01629 }else if (size < qh hull_dim) {
01630 bestneighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
01631 trace2((qh ferr, "qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
01632 facet1->id, size, bestneighbor->id, dist));
01633 qh_mergefacet(facet1, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01634 nummerges++;
01635 if (qh PRINTstatistics) {
01636 zinc_(Zdegen);
01637 wadd_(Wdegentot, dist);
01638 wmax_(Wdegenmax, dist);
01639 }
01640 }
01641 }
01642 }
01643 return nummerges;
01644 }
01645
01646
01647
01648
01649
01650
01651
01652
01653
01654
01655
01656
01657
01658
01659
01660
01661
01662
01663 void qh_merge_nonconvex (facetT *facet1, facetT *facet2, mergeType mergetype) {
01664 facetT *bestfacet, *bestneighbor, *neighbor;
01665 realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
01666
01667 if (qh TRACEmerge-1 == zzval_(Ztotmerge))
01668 qhmem.IStracing= qh IStracing= qh TRACElevel;
01669 trace3((qh ferr, "qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
01670 zzval_(Ztotmerge) + 1, facet1->id, facet2->id, mergetype));
01671
01672 if (!facet1->newfacet) {
01673 bestfacet= facet2;
01674 facet2= facet1;
01675 facet1= bestfacet;
01676 }else
01677 bestfacet= facet1;
01678 bestneighbor= qh_findbestneighbor(bestfacet, &dist, &mindist, &maxdist);
01679 neighbor= qh_findbestneighbor(facet2, &dist2, &mindist2, &maxdist2);
01680 if (dist < dist2) {
01681 qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01682 }else if (qh AVOIDold && !facet2->newfacet
01683 && ((mindist >= -qh MAXcoplanar && maxdist <= qh max_outside)
01684 || dist * 1.5 < dist2)) {
01685 zinc_(Zavoidold);
01686 wadd_(Wavoidoldtot, dist);
01687 wmax_(Wavoidoldmax, dist);
01688 trace2((qh ferr, "qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g. Use f%d dist %2.2g instead\n",
01689 facet2->id, dist2, facet1->id, dist2));
01690 qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
01691 }else {
01692 qh_mergefacet(facet2, neighbor, &mindist2, &maxdist2, !qh_MERGEapex);
01693 dist= dist2;
01694 }
01695 if (qh PRINTstatistics) {
01696 if (mergetype == MRGanglecoplanar) {
01697 zinc_(Zacoplanar);
01698 wadd_(Wacoplanartot, dist);
01699 wmax_(Wacoplanarmax, dist);
01700 }else if (mergetype == MRGconcave) {
01701 zinc_(Zconcave);
01702 wadd_(Wconcavetot, dist);
01703 wmax_(Wconcavemax, dist);
01704 }else {
01705 zinc_(Zcoplanar);
01706 wadd_(Wcoplanartot, dist);
01707 wmax_(Wcoplanarmax, dist);
01708 }
01709 }
01710 }
01711
01712
01713
01714
01715
01716
01717
01718
01719
01720
01721
01722
01723
01724
01725
01726
01727
01728
01729
01730
01731
01732
01733
01734
01735
01736
01737
01738
01739
01740 void qh_mergecycle (facetT *samecycle, facetT *newfacet) {
01741 int traceonce= False, tracerestore= 0;
01742 vertexT *apex;
01743 #ifndef qh_NOtrace
01744 facetT *same;
01745 #endif
01746
01747 if (!qh VERTEXneighbors)
01748 qh_vertexneighbors();
01749 zzinc_(Ztotmerge);
01750 if (qh REPORTfreq2 && qh POSTmerging) {
01751 if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
01752 qh_tracemerging();
01753 }
01754 #ifndef qh_NOtrace
01755 if (qh TRACEmerge == zzval_(Ztotmerge))
01756 qhmem.IStracing= qh IStracing= qh TRACElevel;
01757 trace2((qh ferr, "qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
01758 zzval_(Ztotmerge), samecycle->id, newfacet->id));
01759 if (newfacet == qh tracefacet) {
01760 tracerestore= qh IStracing;
01761 qh IStracing= 4;
01762 fprintf (qh ferr, "qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
01763 zzval_(Ztotmerge), samecycle->id, newfacet->id, qh furthest_id);
01764 traceonce= True;
01765 }
01766 if (qh IStracing >=4) {
01767 fprintf (qh ferr, " same cycle:");
01768 FORALLsame_cycle_(samecycle)
01769 fprintf(qh ferr, " f%d", same->id);
01770 fprintf (qh ferr, "\n");
01771 }
01772 if (qh IStracing >=4)
01773 qh_errprint ("MERGING CYCLE", samecycle, newfacet, NULL, NULL);
01774 #endif
01775 apex= SETfirstt_(samecycle->vertices, vertexT);
01776 qh_makeridges (newfacet);
01777 qh_mergecycle_neighbors (samecycle, newfacet);
01778 qh_mergecycle_ridges (samecycle, newfacet);
01779 qh_mergecycle_vneighbors (samecycle, newfacet);
01780 if (SETfirstt_(newfacet->vertices, vertexT) != apex)
01781 qh_setaddnth (&newfacet->vertices, 0, apex);
01782 if (!newfacet->newfacet)
01783 qh_newvertices (newfacet->vertices);
01784 qh_mergecycle_facets (samecycle, newfacet);
01785 qh_tracemerge (samecycle, newfacet);
01786
01787 if (traceonce) {
01788 fprintf (qh ferr, "qh_mergecycle: end of trace facet\n");
01789 qh IStracing= tracerestore;
01790 }
01791 }
01792
01793
01794
01795
01796
01797
01798
01799
01800
01801
01802
01803
01804
01805
01806
01807
01808
01809
01810
01811
01812
01813
01814
01815
01816
01817
01818 void qh_mergecycle_all (facetT *facetlist, boolT *wasmerge) {
01819 facetT *facet, *same, *prev, *horizon;
01820 facetT *samecycle= NULL, *nextfacet, *nextsame;
01821 int cycles=0, total=0, facets, nummerge;
01822
01823 trace2((qh ferr, "qh_mergecycle_all: begin\n"));
01824 for (facet= facetlist; facet && (nextfacet= facet->next); facet= nextfacet) {
01825 if (facet->normal)
01826 continue;
01827 if (!facet->mergehorizon) {
01828 fprintf (qh ferr, "qh_mergecycle_all: f%d without normal\n", facet->id);
01829 qh_errexit (qh_ERRqhull, facet, NULL);
01830 }
01831 horizon= SETfirstt_(facet->neighbors, facetT);
01832 if (facet->f.samecycle == facet) {
01833 zinc_(Zonehorizon);
01834
01835 horizon->f.newcycle= NULL;
01836 qh_mergefacet (facet, horizon, NULL, NULL, qh_MERGEapex);
01837 }else {
01838 samecycle= facet;
01839 facets= 0;
01840 prev= facet;
01841 for (same= facet->f.samecycle; same;
01842 same= (same == facet ? NULL :nextsame)) {
01843 nextsame= same->f.samecycle;
01844 if (same->cycledone || same->visible)
01845 qh_infiniteloop (same);
01846 same->cycledone= True;
01847 if (same->normal) {
01848 prev->f.samecycle= same->f.samecycle;
01849 same->f.samecycle= NULL;
01850 }else {
01851 prev= same;
01852 facets++;
01853 }
01854 }
01855 while (nextfacet && nextfacet->cycledone)
01856 nextfacet= nextfacet->next;
01857 horizon->f.newcycle= NULL;
01858 qh_mergecycle (samecycle, horizon);
01859 nummerge= horizon->nummerge + facets;
01860 if (nummerge > qh_MAXnummerge)
01861 horizon->nummerge= qh_MAXnummerge;
01862 else
01863 horizon->nummerge= nummerge;
01864 zzinc_(Zcyclehorizon);
01865 total += facets;
01866 zzadd_(Zcyclefacettot, facets);
01867 zmax_(Zcyclefacetmax, facets);
01868 }
01869 cycles++;
01870 }
01871 if (cycles)
01872 *wasmerge= True;
01873 trace1((qh ferr, "qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
01874 }
01875
01876
01877
01878
01879
01880
01881
01882
01883
01884
01885
01886
01887
01888
01889
01890
01891
01892
01893
01894
01895
01896
01897
01898
01899
01900 void qh_mergecycle_facets (facetT *samecycle, facetT *newfacet) {
01901 facetT *same, *next;
01902
01903 trace4((qh ferr, "qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
01904 qh_removefacet(newfacet);
01905 qh_appendfacet(newfacet);
01906 newfacet->newfacet= True;
01907 newfacet->simplicial= False;
01908 newfacet->newmerge= True;
01909
01910 for (same= samecycle->f.samecycle; same; same= (same == samecycle ? NULL : next)) {
01911 next= same->f.samecycle;
01912 qh_willdelete (same, newfacet);
01913 }
01914 if (newfacet->center
01915 && qh_setsize (newfacet->vertices) <= qh hull_dim + qh_MAXnewcentrum) {
01916 qh_memfree (newfacet->center, qh normal_size);
01917 newfacet->center= NULL;
01918 }
01919 trace3((qh ferr, "qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
01920 samecycle->id, newfacet->id));
01921 }
01922
01923
01924
01925
01926
01927
01928
01929
01930
01931
01932
01933
01934
01935
01936
01937
01938
01939
01940
01941
01942
01943
01944
01945
01946
01947
01948
01949
01950
01951
01952
01953
01954
01955
01956
01957
01958 void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet) {
01959 facetT *same, *neighbor, **neighborp;
01960 int delneighbors= 0, newneighbors= 0;
01961 unsigned int samevisitid;
01962 ridgeT *ridge, **ridgep;
01963
01964 samevisitid= ++qh visit_id;
01965 FORALLsame_cycle_(samecycle) {
01966 if (same->visitid == samevisitid || same->visible)
01967 qh_infiniteloop (samecycle);
01968 same->visitid= samevisitid;
01969 }
01970 newfacet->visitid= ++qh visit_id;
01971 trace4((qh ferr, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
01972 FOREACHneighbor_(newfacet) {
01973 if (neighbor->visitid == samevisitid) {
01974 SETref_(neighbor)= NULL;
01975 delneighbors++;
01976 }else
01977 neighbor->visitid= qh visit_id;
01978 }
01979 qh_setcompact (newfacet->neighbors);
01980
01981 trace4((qh ferr, "qh_mergecycle_neighbors: update neighbors\n"));
01982 FORALLsame_cycle_(samecycle) {
01983 FOREACHneighbor_(same) {
01984 if (neighbor->visitid == samevisitid)
01985 continue;
01986 if (neighbor->simplicial) {
01987 if (neighbor->visitid != qh visit_id) {
01988 qh_setappend (&newfacet->neighbors, neighbor);
01989 qh_setreplace (neighbor->neighbors, same, newfacet);
01990 newneighbors++;
01991 neighbor->visitid= qh visit_id;
01992 FOREACHridge_(neighbor->ridges) {
01993 if (ridge->top == same) {
01994 ridge->top= newfacet;
01995 break;
01996 }else if (ridge->bottom == same) {
01997 ridge->bottom= newfacet;
01998 break;
01999 }
02000 }
02001 }else {
02002 qh_makeridges (neighbor);
02003 qh_setdel (neighbor->neighbors, same);
02004
02005 }
02006 }else {
02007 qh_setdel (neighbor->neighbors, same);
02008 if (neighbor->visitid != qh visit_id) {
02009 qh_setappend (&neighbor->neighbors, newfacet);
02010 qh_setappend (&newfacet->neighbors, neighbor);
02011 neighbor->visitid= qh visit_id;
02012 newneighbors++;
02013 }
02014 }
02015 }
02016 }
02017 trace2((qh ferr, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
02018 delneighbors, newneighbors));
02019 }
02020
02021
02022
02023
02024
02025
02026
02027
02028
02029
02030
02031
02032
02033
02034
02035
02036
02037
02038
02039
02040
02041
02042
02043
02044
02045
02046
02047
02048
02049
02050
02051
02052
02053
02054
02055 void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet) {
02056 facetT *same, *neighbor= NULL;
02057 int numold=0, numnew=0;
02058 int neighbor_i, neighbor_n;
02059 unsigned int samevisitid;
02060 ridgeT *ridge, **ridgep;
02061 boolT toporient;
02062 void **freelistp;
02063
02064 trace4((qh ferr, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
02065 samevisitid= qh visit_id -1;
02066 FOREACHridge_(newfacet->ridges) {
02067 neighbor= otherfacet_(ridge, newfacet);
02068 if (neighbor->visitid == samevisitid)
02069 SETref_(ridge)= NULL;
02070 }
02071 qh_setcompact (newfacet->ridges);
02072
02073 trace4((qh ferr, "qh_mergecycle_ridges: add ridges to newfacet\n"));
02074 FORALLsame_cycle_(samecycle) {
02075 FOREACHridge_(same->ridges) {
02076 if (ridge->top == same) {
02077 ridge->top= newfacet;
02078 neighbor= ridge->bottom;
02079 }else if (ridge->bottom == same) {
02080 ridge->bottom= newfacet;
02081 neighbor= ridge->top;
02082 }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
02083 qh_setappend (&newfacet->ridges, ridge);
02084 numold++;
02085 continue;
02086 }else {
02087 fprintf (qh ferr, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
02088 qh_errexit (qh_ERRqhull, NULL, ridge);
02089 }
02090 if (neighbor == newfacet) {
02091 qh_setfree(&(ridge->vertices));
02092 qh_memfree_(ridge, sizeof(ridgeT), freelistp);
02093 numold++;
02094 }else if (neighbor->visitid == samevisitid) {
02095 qh_setdel (neighbor->ridges, ridge);
02096 qh_setfree(&(ridge->vertices));
02097 qh_memfree_(ridge, sizeof(ridgeT), freelistp);
02098 numold++;
02099 }else {
02100 qh_setappend (&newfacet->ridges, ridge);
02101 numold++;
02102 }
02103 }
02104 if (same->ridges)
02105 qh_settruncate (same->ridges, 0);
02106 if (!same->simplicial)
02107 continue;
02108 FOREACHneighbor_i_(same) {
02109 if (neighbor->visitid != samevisitid && neighbor->simplicial) {
02110 ridge= qh_newridge();
02111 ridge->vertices= qh_setnew_delnthsorted (same->vertices, qh hull_dim,
02112 neighbor_i, 0);
02113 toporient= same->toporient ^ (neighbor_i & 0x1);
02114 if (toporient) {
02115 ridge->top= newfacet;
02116 ridge->bottom= neighbor;
02117 }else {
02118 ridge->top= neighbor;
02119 ridge->bottom= newfacet;
02120 }
02121 qh_setappend(&(newfacet->ridges), ridge);
02122 qh_setappend(&(neighbor->ridges), ridge);
02123 numnew++;
02124 }
02125 }
02126 }
02127
02128 trace2((qh ferr, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
02129 numold, numnew));
02130 }
02131
02132
02133
02134
02135
02136
02137
02138
02139
02140
02141
02142
02143
02144
02145
02146
02147
02148
02149
02150
02151
02152
02153
02154
02155
02156
02157 void qh_mergecycle_vneighbors (facetT *samecycle, facetT *newfacet) {
02158 facetT *neighbor, **neighborp;
02159 unsigned int mergeid;
02160 vertexT *vertex, **vertexp, *apex;
02161 setT *vertices;
02162
02163 trace4((qh ferr, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
02164 mergeid= qh visit_id - 1;
02165 newfacet->visitid= mergeid;
02166 vertices= qh_basevertices (samecycle);
02167 apex= SETfirstt_(samecycle->vertices, vertexT);
02168 qh_setappend (&vertices, apex);
02169 FOREACHvertex_(vertices) {
02170 vertex->delridge= True;
02171 FOREACHneighbor_(vertex) {
02172 if (neighbor->visitid == mergeid)
02173 SETref_(neighbor)= NULL;
02174 }
02175 qh_setcompact (vertex->neighbors);
02176 qh_setappend (&vertex->neighbors, newfacet);
02177 if (!SETsecond_(vertex->neighbors)) {
02178 zinc_(Zcyclevertex);
02179 trace2((qh ferr, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
02180 vertex->id, samecycle->id, newfacet->id));
02181 qh_setdelsorted (newfacet->vertices, vertex);
02182 vertex->deleted= True;
02183 qh_setappend (&qh del_vertices, vertex);
02184 }
02185 }
02186 qh_settempfree (&vertices);
02187 trace3((qh ferr, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
02188 samecycle->id, newfacet->id));
02189 }
02190
02191
02192
02193
02194
02195
02196
02197
02198
02199
02200
02201
02202
02203
02204
02205
02206
02207
02208
02209
02210
02211
02212
02213
02214
02215
02216
02217
02218
02219
02220
02221
02222
02223
02224
02225
02226
02227
02228
02229
02230
02231
02232
02233
02234
02235
02236
02237
02238
02239
02240
02241
02242 void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex) {
02243 boolT traceonce= False;
02244 vertexT *vertex, **vertexp;
02245 int tracerestore=0, nummerge;
02246
02247 zzinc_(Ztotmerge);
02248 if (qh REPORTfreq2 && qh POSTmerging) {
02249 if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
02250 qh_tracemerging();
02251 }
02252 #ifndef qh_NOtrace
02253 if (qh build_cnt >= qh RERUN) {
02254 if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
02255 tracerestore= 0;
02256 qh IStracing= qh TRACElevel;
02257 traceonce= True;
02258 fprintf (qh ferr, "qh_mergefacet: ========= trace wide merge #%d (%2.2g) for f%d into f%d, last point was p%d\n", zzval_(Ztotmerge),
02259 fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
02260 }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
02261 tracerestore= qh IStracing;
02262 qh IStracing= 4;
02263 traceonce= True;
02264 fprintf (qh ferr, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
02265 zzval_(Ztotmerge), qh tracefacet_id, qh furthest_id);
02266 }
02267 }
02268 if (qh IStracing >= 2) {
02269 realT mergemin= -2;
02270 realT mergemax= -2;
02271
02272 if (mindist) {
02273 mergemin= *mindist;
02274 mergemax= *maxdist;
02275 }
02276 fprintf (qh ferr, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
02277 zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
02278 }
02279 #endif
02280 if (facet1 == facet2 || facet1->visible || facet2->visible) {
02281 fprintf (qh ferr, "qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
02282 facet1->id, facet2->id);
02283 qh_errexit2 (qh_ERRqhull, facet1, facet2);
02284 }
02285 if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
02286 fprintf(qh ferr, "\n\
02287 qhull precision error: Only %d facets remain. Can not merge another\n\
02288 pair. The convexity constraints may be too strong. Reduce the\n\
02289 magnitude of 'Cn' or increase the magnitude of 'An'. For example,\n\
02290 try 'C-0.001' instead of 'C-0.1' or 'A-0.999' instead of 'A-0.9'.\n",
02291 qh hull_dim+1);
02292 if (qh hull_dim >= 5 && !qh MERGEexact)
02293 fprintf(qh ferr, "Option 'Qx' may avoid this problem.\n");
02294 qh_errexit(qh_ERRinput, NULL, NULL);
02295 }
02296 if (!qh VERTEXneighbors)
02297 qh_vertexneighbors();
02298 qh_makeridges(facet1);
02299 qh_makeridges(facet2);
02300 if (qh IStracing >=4)
02301 qh_errprint ("MERGING", facet1, facet2, NULL, NULL);
02302 if (mindist) {
02303 maximize_(qh max_outside, *maxdist);
02304 maximize_(qh max_vertex, *maxdist);
02305 #if qh_MAXoutside
02306 maximize_(facet2->maxoutside, *maxdist);
02307 #endif
02308 minimize_(qh min_vertex, *mindist);
02309 if (!facet2->keepcentrum
02310 && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
02311 facet2->keepcentrum= True;
02312 zinc_(Zwidefacet);
02313 }
02314 }
02315 nummerge= facet1->nummerge + facet2->nummerge + 1;
02316 if (nummerge >= qh_MAXnummerge)
02317 facet2->nummerge= qh_MAXnummerge;
02318 else
02319 facet2->nummerge= nummerge;
02320 facet2->newmerge= True;
02321 facet2->dupridge= False;
02322 qh_updatetested (facet1, facet2);
02323 if (qh hull_dim > 2 && qh_setsize (facet1->vertices) == qh hull_dim)
02324 qh_mergesimplex (facet1, facet2, mergeapex);
02325 else {
02326 qh vertex_visit++;
02327 FOREACHvertex_(facet2->vertices)
02328 vertex->visitid= qh vertex_visit;
02329 if (qh hull_dim == 2)
02330 qh_mergefacet2d(facet1, facet2);
02331 else {
02332 qh_mergeneighbors(facet1, facet2);
02333 qh_mergevertices(facet1->vertices, &facet2->vertices);
02334 }
02335 qh_mergeridges(facet1, facet2);
02336 qh_mergevertex_neighbors(facet1, facet2);
02337 if (!facet2->newfacet)
02338 qh_newvertices (facet2->vertices);
02339 }
02340 if (!mergeapex)
02341 qh_degen_redundant_neighbors (facet2, facet1);
02342 if (facet2->coplanar || !facet2->newfacet) {
02343 zinc_(Zmergeintohorizon);
02344 }else if (!facet1->newfacet && facet2->newfacet) {
02345 zinc_(Zmergehorizon);
02346 }else {
02347 zinc_(Zmergenew);
02348 }
02349 qh_willdelete (facet1, facet2);
02350 qh_removefacet(facet2);
02351 qh_appendfacet(facet2);
02352 facet2->newfacet= True;
02353 facet2->tested= False;
02354 qh_tracemerge (facet1, facet2);
02355 if (traceonce) {
02356 fprintf (qh ferr, "qh_mergefacet: end of wide tracing\n");
02357 qh IStracing= tracerestore;
02358 }
02359 }
02360
02361
02362
02363
02364
02365
02366
02367
02368
02369
02370
02371
02372
02373
02374
02375
02376
02377
02378
02379
02380
02381
02382
02383
02384
02385 void qh_mergefacet2d (facetT *facet1, facetT *facet2) {
02386 vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
02387 facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
02388
02389 vertex1A= SETfirstt_(facet1->vertices, vertexT);
02390 vertex1B= SETsecondt_(facet1->vertices, vertexT);
02391 vertex2A= SETfirstt_(facet2->vertices, vertexT);
02392 vertex2B= SETsecondt_(facet2->vertices, vertexT);
02393 neighbor1A= SETfirstt_(facet1->neighbors, facetT);
02394 neighbor1B= SETsecondt_(facet1->neighbors, facetT);
02395 neighbor2A= SETfirstt_(facet2->neighbors, facetT);
02396 neighbor2B= SETsecondt_(facet2->neighbors, facetT);
02397 if (vertex1A == vertex2A) {
02398 vertexA= vertex1B;
02399 vertexB= vertex2B;
02400 neighborA= neighbor2A;
02401 neighborB= neighbor1A;
02402 }else if (vertex1A == vertex2B) {
02403 vertexA= vertex1B;
02404 vertexB= vertex2A;
02405 neighborA= neighbor2B;
02406 neighborB= neighbor1A;
02407 }else if (vertex1B == vertex2A) {
02408 vertexA= vertex1A;
02409 vertexB= vertex2B;
02410 neighborA= neighbor2A;
02411 neighborB= neighbor1B;
02412 }else {
02413 vertexA= vertex1A;
02414 vertexB= vertex2A;
02415 neighborA= neighbor2B;
02416 neighborB= neighbor1B;
02417 }
02418
02419 if (vertexA->id > vertexB->id) {
02420 SETfirst_(facet2->vertices)= vertexA;
02421 SETsecond_(facet2->vertices)= vertexB;
02422 if (vertexB == vertex2A)
02423 facet2->toporient= !facet2->toporient;
02424 SETfirst_(facet2->neighbors)= neighborA;
02425 SETsecond_(facet2->neighbors)= neighborB;
02426 }else {
02427 SETfirst_(facet2->vertices)= vertexB;
02428 SETsecond_(facet2->vertices)= vertexA;
02429 if (vertexB == vertex2B)
02430 facet2->toporient= !facet2->toporient;
02431 SETfirst_(facet2->neighbors)= neighborB;
02432 SETsecond_(facet2->neighbors)= neighborA;
02433 }
02434 qh_makeridges (neighborB);
02435 qh_setreplace(neighborB->neighbors, facet1, facet2);
02436 trace4((qh ferr, "qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
02437 vertexA->id, neighborB->id, facet1->id, facet2->id));
02438 }
02439
02440
02441
02442
02443
02444
02445
02446
02447
02448
02449
02450
02451
02452
02453
02454
02455
02456
02457
02458
02459
02460 void qh_mergeneighbors(facetT *facet1, facetT *facet2) {
02461 facetT *neighbor, **neighborp;
02462
02463 trace4((qh ferr, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
02464 facet1->id, facet2->id));
02465 qh visit_id++;
02466 FOREACHneighbor_(facet2) {
02467 neighbor->visitid= qh visit_id;
02468 }
02469 FOREACHneighbor_(facet1) {
02470 if (neighbor->visitid == qh visit_id) {
02471 if (neighbor->simplicial)
02472 qh_makeridges (neighbor);
02473 if (SETfirstt_(neighbor->neighbors, facetT) != facet1)
02474 qh_setdel (neighbor->neighbors, facet1);
02475 else {
02476 qh_setdel(neighbor->neighbors, facet2);
02477 qh_setreplace(neighbor->neighbors, facet1, facet2);
02478 }
02479 }else if (neighbor != facet2) {
02480 qh_setappend(&(facet2->neighbors), neighbor);
02481 qh_setreplace(neighbor->neighbors, facet1, facet2);
02482 }
02483 }
02484 qh_setdel(facet1->neighbors, facet2);
02485 qh_setdel(facet2->neighbors, facet1);
02486 }
02487
02488
02489
02490
02491
02492
02493
02494
02495
02496
02497
02498
02499
02500
02501
02502
02503
02504
02505
02506
02507
02508 void qh_mergeridges(facetT *facet1, facetT *facet2) {
02509 ridgeT *ridge, **ridgep;
02510 vertexT *vertex, **vertexp;
02511
02512 trace4((qh ferr, "qh_mergeridges: merge ridges of f%d and f%d\n",
02513 facet1->id, facet2->id));
02514 FOREACHridge_(facet2->ridges) {
02515 if ((ridge->top == facet1) || (ridge->bottom == facet1)) {
02516 FOREACHvertex_(ridge->vertices)
02517 vertex->delridge= True;
02518 qh_delridge(ridge);
02519 ridgep--;
02520 }
02521 }
02522 FOREACHridge_(facet1->ridges) {
02523 if (ridge->top == facet1)
02524 ridge->top= facet2;
02525 else
02526 ridge->bottom= facet2;
02527 qh_setappend(&(facet2->ridges), ridge);
02528 }
02529 }
02530
02531
02532
02533
02534
02535
02536
02537
02538
02539
02540
02541
02542
02543
02544
02545
02546
02547
02548
02549
02550
02551
02552
02553
02554
02555
02556
02557
02558
02559
02560
02561
02562
02563
02564
02565
02566
02567
02568
02569
02570
02571
02572
02573
02574
02575 void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex) {
02576 vertexT *vertex, **vertexp, *apex;
02577 ridgeT *ridge, **ridgep;
02578 boolT issubset= False;
02579 int vertex_i= -1, vertex_n;
02580 facetT *neighbor, **neighborp, *otherfacet;
02581
02582 if (mergeapex) {
02583 if (!facet2->newfacet)
02584 qh_newvertices (facet2->vertices);
02585 apex= SETfirstt_(facet1->vertices, vertexT);
02586 if (SETfirstt_(facet2->vertices, vertexT) != apex)
02587 qh_setaddnth (&facet2->vertices, 0, apex);
02588 else
02589 issubset= True;
02590 }else {
02591 zinc_(Zmergesimplex);
02592 FOREACHvertex_(facet1->vertices)
02593 vertex->seen= False;
02594 FOREACHridge_(facet1->ridges) {
02595 if (otherfacet_(ridge, facet1) == facet2) {
02596 FOREACHvertex_(ridge->vertices) {
02597 vertex->seen= True;
02598 vertex->delridge= True;
02599 }
02600 break;
02601 }
02602 }
02603 FOREACHvertex_(facet1->vertices) {
02604 if (!vertex->seen)
02605 break;
02606 }
02607 apex= vertex;
02608 trace4((qh ferr, "qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
02609 apex->id, facet1->id, facet2->id));
02610 FOREACHvertex_i_(facet2->vertices) {
02611 if (vertex->id < apex->id) {
02612 break;
02613 }else if (vertex->id == apex->id) {
02614 issubset= True;
02615 break;
02616 }
02617 }
02618 if (!issubset)
02619 qh_setaddnth (&facet2->vertices, vertex_i, apex);
02620 if (!facet2->newfacet)
02621 qh_newvertices (facet2->vertices);
02622 else if (!apex->newlist) {
02623 qh_removevertex (apex);
02624 qh_appendvertex (apex);
02625 }
02626 }
02627 trace4((qh ferr, "qh_mergesimplex: update vertex neighbors of f%d\n",
02628 facet1->id));
02629 FOREACHvertex_(facet1->vertices) {
02630 if (vertex == apex && !issubset)
02631 qh_setreplace (vertex->neighbors, facet1, facet2);
02632 else {
02633 qh_setdel (vertex->neighbors, facet1);
02634 if (!SETsecond_(vertex->neighbors))
02635 qh_mergevertex_del (vertex, facet1, facet2);
02636 }
02637 }
02638 trace4((qh ferr, "qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
02639 facet1->id, facet2->id));
02640 qh visit_id++;
02641 FOREACHneighbor_(facet2)
02642 neighbor->visitid= qh visit_id;
02643 FOREACHridge_(facet1->ridges) {
02644 otherfacet= otherfacet_(ridge, facet1);
02645 if (otherfacet == facet2) {
02646 qh_setdel (facet2->ridges, ridge);
02647 qh_setfree(&(ridge->vertices));
02648 qh_memfree (ridge, sizeof(ridgeT));
02649 qh_setdel (facet2->neighbors, facet1);
02650 }else {
02651 qh_setappend (&facet2->ridges, ridge);
02652 if (otherfacet->visitid != qh visit_id) {
02653 qh_setappend (&facet2->neighbors, otherfacet);
02654 qh_setreplace (otherfacet->neighbors, facet1, facet2);
02655 otherfacet->visitid= qh visit_id;
02656 }else {
02657 if (otherfacet->simplicial)
02658 qh_makeridges (otherfacet);
02659 if (SETfirstt_(otherfacet->neighbors, facetT) != facet1)
02660 qh_setdel (otherfacet->neighbors, facet1);
02661 else {
02662 qh_setdel(otherfacet->neighbors, facet2);
02663 qh_setreplace(otherfacet->neighbors, facet1, facet2);
02664 }
02665 }
02666 if (ridge->top == facet1)
02667 ridge->top= facet2;
02668 else
02669 ridge->bottom= facet2;
02670 }
02671 }
02672 SETfirst_(facet1->ridges)= NULL;
02673 trace3((qh ferr, "qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
02674 facet1->id, getid_(apex), facet2->id));
02675 }
02676
02677
02678
02679
02680
02681
02682
02683
02684
02685
02686
02687 void qh_mergevertex_del (vertexT *vertex, facetT *facet1, facetT *facet2) {
02688
02689 zinc_(Zmergevertex);
02690 trace2((qh ferr, "qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
02691 vertex->id, facet1->id, facet2->id));
02692 qh_setdelsorted (facet2->vertices, vertex);
02693 vertex->deleted= True;
02694 qh_setappend (&qh del_vertices, vertex);
02695 }
02696
02697
02698
02699
02700
02701
02702
02703
02704
02705
02706
02707
02708
02709
02710
02711
02712
02713 void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2) {
02714 vertexT *vertex, **vertexp;
02715
02716 trace4((qh ferr, "qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
02717 facet1->id, facet2->id));
02718 if (qh tracevertex) {
02719 fprintf (qh ferr, "qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
02720 facet1->id, facet2->id, qh furthest_id, qh tracevertex->neighbors->e[0].p);
02721 qh_errprint ("TRACE", NULL, NULL, NULL, qh tracevertex);
02722 }
02723 FOREACHvertex_(facet1->vertices) {
02724 if (vertex->visitid != qh vertex_visit)
02725 qh_setreplace(vertex->neighbors, facet1, facet2);
02726 else {
02727 qh_setdel(vertex->neighbors, facet1);
02728 if (!SETsecond_(vertex->neighbors))
02729 qh_mergevertex_del (vertex, facet1, facet2);
02730 }
02731 }
02732 if (qh tracevertex)
02733 qh_errprint ("TRACE", NULL, NULL, NULL, qh tracevertex);
02734 }
02735
02736
02737
02738
02739
02740
02741
02742
02743
02744
02745
02746
02747
02748
02749
02750
02751 void qh_mergevertices(setT *vertices1, setT **vertices2) {
02752 int newsize= qh_setsize(vertices1)+qh_setsize(*vertices2) - qh hull_dim + 1;
02753 setT *mergedvertices;
02754 vertexT *vertex, **vertexp, **vertex2= SETaddr_(*vertices2, vertexT);
02755
02756 mergedvertices= qh_settemp (newsize);
02757 FOREACHvertex_(vertices1) {
02758 if (!*vertex2 || vertex->id > (*vertex2)->id)
02759 qh_setappend (&mergedvertices, vertex);
02760 else {
02761 while (*vertex2 && (*vertex2)->id > vertex->id)
02762 qh_setappend (&mergedvertices, *vertex2++);
02763 if (!*vertex2 || (*vertex2)->id < vertex->id)
02764 qh_setappend (&mergedvertices, vertex);
02765 else
02766 qh_setappend (&mergedvertices, *vertex2++);
02767 }
02768 }
02769 while (*vertex2)
02770 qh_setappend (&mergedvertices, *vertex2++);
02771 if (newsize < qh_setsize (mergedvertices)) {
02772 fprintf (qh ferr, "qhull internal error (qh_mergevertices): facets did not share a ridge\n");
02773 qh_errexit (qh_ERRqhull, NULL, NULL);
02774 }
02775 qh_setfree(vertices2);
02776 *vertices2= mergedvertices;
02777 qh_settemppop ();
02778 }
02779
02780
02781
02782
02783
02784
02785
02786
02787
02788
02789
02790
02791
02792
02793
02794
02795
02796
02797
02798
02799
02800
02801
02802
02803
02804 setT *qh_neighbor_intersections (vertexT *vertex) {
02805 facetT *neighbor, **neighborp, *neighborA, *neighborB;
02806 setT *intersect;
02807 int neighbor_i, neighbor_n;
02808
02809 FOREACHneighbor_(vertex) {
02810 if (neighbor->simplicial)
02811 return NULL;
02812 }
02813 neighborA= SETfirstt_(vertex->neighbors, facetT);
02814 neighborB= SETsecondt_(vertex->neighbors, facetT);
02815 zinc_(Zintersectnum);
02816 if (!neighborA)
02817 return NULL;
02818 if (!neighborB)
02819 intersect= qh_setcopy (neighborA->vertices, 0);
02820 else
02821 intersect= qh_vertexintersect_new (neighborA->vertices, neighborB->vertices);
02822 qh_settemppush (intersect);
02823 qh_setdelsorted (intersect, vertex);
02824 FOREACHneighbor_i_(vertex) {
02825 if (neighbor_i >= 2) {
02826 zinc_(Zintersectnum);
02827 qh_vertexintersect (&intersect, neighbor->vertices);
02828 if (!SETfirst_(intersect)) {
02829 zinc_(Zintersectfail);
02830 qh_settempfree (&intersect);
02831 return NULL;
02832 }
02833 }
02834 }
02835 trace3((qh ferr, "qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
02836 qh_setsize (intersect), vertex->id));
02837 return intersect;
02838 }
02839
02840
02841
02842
02843
02844
02845
02846
02847
02848
02849
02850 void qh_newvertices (setT *vertices) {
02851 vertexT *vertex, **vertexp;
02852
02853 FOREACHvertex_(vertices) {
02854 if (!vertex->newlist) {
02855 qh_removevertex (vertex);
02856 qh_appendvertex (vertex);
02857 }
02858 }
02859 }
02860
02861
02862
02863
02864
02865
02866
02867
02868
02869
02870
02871
02872
02873
02874
02875
02876
02877
02878
02879
02880
02881
02882
02883
02884
02885
02886
02887
02888 boolT qh_reducevertices (void) {
02889 int numshare=0, numrename= 0;
02890 boolT degenredun= False;
02891 facetT *newfacet;
02892 vertexT *vertex, **vertexp;
02893
02894 if (qh hull_dim == 2)
02895 return False;
02896 if (qh_merge_degenredundant())
02897 degenredun= True;
02898 LABELrestart:
02899 FORALLnew_facets {
02900 if (newfacet->newmerge) {
02901 if (!qh MERGEvertices)
02902 newfacet->newmerge= False;
02903 qh_remove_extravertices (newfacet);
02904 }
02905 }
02906 if (!qh MERGEvertices)
02907 return False;
02908 FORALLnew_facets {
02909 if (newfacet->newmerge) {
02910 newfacet->newmerge= False;
02911 FOREACHvertex_(newfacet->vertices) {
02912 if (vertex->delridge) {
02913 if (qh_rename_sharedvertex (vertex, newfacet)) {
02914 numshare++;
02915 vertexp--;
02916 }
02917 }
02918 }
02919 }
02920 }
02921 FORALLvertex_(qh newvertex_list) {
02922 if (vertex->delridge && !vertex->deleted) {
02923 vertex->delridge= False;
02924 if (qh hull_dim >= 4 && qh_redundant_vertex (vertex)) {
02925 numrename++;
02926 if (qh_merge_degenredundant()) {
02927 degenredun= True;
02928 goto LABELrestart;
02929 }
02930 }
02931 }
02932 }
02933 trace1((qh ferr, "qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
02934 numshare, numrename, degenredun));
02935 return degenredun;
02936 }
02937
02938
02939
02940
02941
02942
02943
02944
02945
02946
02947
02948
02949
02950
02951
02952
02953
02954
02955
02956
02957
02958
02959
02960 vertexT *qh_redundant_vertex (vertexT *vertex) {
02961 vertexT *newvertex= NULL;
02962 setT *vertices, *ridges;
02963
02964 trace3((qh ferr, "qh_redundant_vertex: check if v%d can be renamed\n", vertex->id));
02965 if ((vertices= qh_neighbor_intersections (vertex))) {
02966 ridges= qh_vertexridges (vertex);
02967 if ((newvertex= qh_find_newvertex (vertex, vertices, ridges)))
02968 qh_renamevertex (vertex, newvertex, ridges, NULL, NULL);
02969 qh_settempfree (&ridges);
02970 qh_settempfree (&vertices);
02971 }
02972 return newvertex;
02973 }
02974
02975
02976
02977
02978
02979
02980
02981
02982
02983
02984
02985
02986
02987
02988
02989
02990
02991
02992 boolT qh_remove_extravertices (facetT *facet) {
02993 ridgeT *ridge, **ridgep;
02994 vertexT *vertex, **vertexp;
02995 boolT foundrem= False;
02996
02997 trace4((qh ferr, "qh_remove_extravertices: test f%d for extra vertices\n",
02998 facet->id));
02999 FOREACHvertex_(facet->vertices)
03000 vertex->seen= False;
03001 FOREACHridge_(facet->ridges) {
03002 FOREACHvertex_(ridge->vertices)
03003 vertex->seen= True;
03004 }
03005 FOREACHvertex_(facet->vertices) {
03006 if (!vertex->seen) {
03007 foundrem= True;
03008 zinc_(Zremvertex);
03009 qh_setdelsorted (facet->vertices, vertex);
03010 qh_setdel (vertex->neighbors, facet);
03011 if (!qh_setsize (vertex->neighbors)) {
03012 vertex->deleted= True;
03013 qh_setappend (&qh del_vertices, vertex);
03014 zinc_(Zremvertexdel);
03015 trace2((qh ferr, "qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->id));
03016 }else
03017 trace3((qh ferr, "qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->id, facet->id));
03018 vertexp--;
03019 }
03020 }
03021 return foundrem;
03022 }
03023
03024
03025
03026
03027
03028
03029
03030
03031
03032
03033
03034
03035
03036
03037
03038
03039
03040
03041
03042
03043
03044
03045
03046
03047
03048
03049
03050
03051 vertexT *qh_rename_sharedvertex (vertexT *vertex, facetT *facet) {
03052 facetT *neighbor, **neighborp, *neighborA= NULL;
03053 setT *vertices, *ridges;
03054 vertexT *newvertex;
03055
03056 if (qh_setsize (vertex->neighbors) == 2) {
03057 neighborA= SETfirstt_(vertex->neighbors, facetT);
03058 if (neighborA == facet)
03059 neighborA= SETsecondt_(vertex->neighbors, facetT);
03060 }else if (qh hull_dim == 3)
03061 return NULL;
03062 else {
03063 qh visit_id++;
03064 FOREACHneighbor_(facet)
03065 neighbor->visitid= qh visit_id;
03066 FOREACHneighbor_(vertex) {
03067 if (neighbor->visitid == qh visit_id) {
03068 if (neighborA)
03069 return NULL;
03070 neighborA= neighbor;
03071 }
03072 }
03073 if (!neighborA) {
03074 fprintf (qh ferr, "qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
03075 vertex->id, facet->id);
03076 qh_errprint ("ERRONEOUS", facet, NULL, NULL, vertex);
03077 qh_errexit (qh_ERRqhull, NULL, NULL);
03078 }
03079 }
03080
03081 ridges= qh_settemp (qh TEMPsize);
03082 neighborA->visitid= ++qh visit_id;
03083 qh_vertexridges_facet (vertex, facet, &ridges);
03084 trace2((qh ferr, "qh_rename_sharedvertex: p%d (v%d) is shared by f%d (%d ridges) and f%d\n",
03085 qh_pointid(vertex->point), vertex->id, facet->id, qh_setsize (ridges), neighborA->id));
03086 zinc_(Zintersectnum);
03087 vertices= qh_vertexintersect_new (facet->vertices, neighborA->vertices);
03088 qh_setdel (vertices, vertex);
03089 qh_settemppush (vertices);
03090 if ((newvertex= qh_find_newvertex (vertex, vertices, ridges)))
03091 qh_renamevertex (vertex, newvertex, ridges, facet, neighborA);
03092 qh_settempfree (&vertices);
03093 qh_settempfree (&ridges);
03094 return newvertex;
03095 }
03096
03097
03098
03099
03100
03101
03102
03103
03104
03105
03106
03107
03108
03109
03110
03111
03112
03113
03114 void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex) {
03115 int nth= 0, oldnth;
03116 facetT *temp;
03117 vertexT *vertex, **vertexp;
03118
03119 oldnth= qh_setindex (ridge->vertices, oldvertex);
03120 qh_setdelnthsorted (ridge->vertices, oldnth);
03121 FOREACHvertex_(ridge->vertices) {
03122 if (vertex == newvertex) {
03123 zinc_(Zdelridge);
03124 if (ridge->nonconvex)
03125 qh_copynonconvex (ridge);
03126 qh_delridge (ridge);
03127 trace2((qh ferr, "qh_renameridgevertex: ridge r%d deleted. It contained both v%d and v%d\n",
03128 ridge->id, oldvertex->id, newvertex->id));
03129 return;
03130 }
03131 if (vertex->id < newvertex->id)
03132 break;
03133 nth++;
03134 }
03135 qh_setaddnth(&ridge->vertices, nth, newvertex);
03136 if (abs(oldnth - nth)%2) {
03137 trace3((qh ferr, "qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
03138 ridge->id));
03139 temp= ridge->top;
03140 ridge->top= ridge->bottom;
03141 ridge->bottom= temp;
03142 }
03143 }
03144
03145
03146
03147
03148
03149
03150
03151
03152
03153
03154
03155
03156
03157
03158
03159
03160
03161
03162
03163
03164
03165
03166
03167
03168
03169
03170
03171
03172
03173
03174
03175
03176 void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, facetT *oldfacet, facetT *neighborA) {
03177 facetT *neighbor, **neighborp;
03178 ridgeT *ridge, **ridgep;
03179 boolT istrace= False;
03180
03181 if (qh IStracing >= 2 || oldvertex->id == qh tracevertex_id ||
03182 newvertex->id == qh tracevertex_id)
03183 istrace= True;
03184 FOREACHridge_(ridges)
03185 qh_renameridgevertex (ridge, oldvertex, newvertex);
03186 if (!oldfacet) {
03187 zinc_(Zrenameall);
03188 if (istrace)
03189 fprintf (qh ferr, "qh_renamevertex: renamed v%d to v%d in several facets\n",
03190 oldvertex->id, newvertex->id);
03191 FOREACHneighbor_(oldvertex) {
03192 qh_maydropneighbor (neighbor);
03193 qh_setdelsorted (neighbor->vertices, oldvertex);
03194 if (qh_remove_extravertices (neighbor))
03195 neighborp--;
03196 }
03197 if (!oldvertex->deleted) {
03198 oldvertex->deleted= True;
03199 qh_setappend (&qh del_vertices, oldvertex);
03200 }
03201 }else if (qh_setsize (oldvertex->neighbors) == 2) {
03202 zinc_(Zrenameshare);
03203 if (istrace)
03204 fprintf (qh ferr, "qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
03205 oldvertex->id, newvertex->id, oldfacet->id);
03206 FOREACHneighbor_(oldvertex)
03207 qh_setdelsorted (neighbor->vertices, oldvertex);
03208 oldvertex->deleted= True;
03209 qh_setappend (&qh del_vertices, oldvertex);
03210 }else {
03211 zinc_(Zrenamepinch);
03212 if (istrace || qh IStracing)
03213 fprintf (qh ferr, "qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
03214 oldvertex->id, newvertex->id, oldfacet->id, neighborA->id);
03215 qh_setdelsorted (oldfacet->vertices, oldvertex);
03216 qh_setdel (oldvertex->neighbors, oldfacet);
03217 qh_remove_extravertices (neighborA);
03218 }
03219 }
03220
03221
03222
03223
03224
03225
03226
03227
03228
03229
03230
03231
03232
03233
03234
03235
03236
03237
03238
03239
03240
03241
03242
03243
03244
03245
03246
03247
03248
03249
03250
03251
03252
03253
03254
03255
03256 boolT qh_test_appendmerge (facetT *facet, facetT *neighbor) {
03257 realT dist, dist2= -REALmax, angle= -REALmax;
03258 boolT isconcave= False, iscoplanar= False, okangle= False;
03259
03260 if (qh SKIPconvex && !qh POSTmerging)
03261 return False;
03262 if ((!qh MERGEexact || qh POSTmerging) && qh cos_max < REALmax/2) {
03263 angle= qh_getangle(facet->normal, neighbor->normal);
03264 zinc_(Zangletests);
03265 if (angle > qh cos_max) {
03266 zinc_(Zcoplanarangle);
03267 qh_appendmergeset(facet, neighbor, MRGanglecoplanar, &angle);
03268 trace2((qh ferr, "qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
03269 angle, facet->id, neighbor->id));
03270 return True;
03271 }else
03272 okangle= True;
03273 }
03274 if (!facet->center)
03275 facet->center= qh_getcentrum (facet);
03276 zzinc_(Zcentrumtests);
03277 qh_distplane(facet->center, neighbor, &dist);
03278 if (dist > qh centrum_radius)
03279 isconcave= True;
03280 else {
03281 if (dist > -qh centrum_radius)
03282 iscoplanar= True;
03283 if (!neighbor->center)
03284 neighbor->center= qh_getcentrum (neighbor);
03285 zzinc_(Zcentrumtests);
03286 qh_distplane(neighbor->center, facet, &dist2);
03287 if (dist2 > qh centrum_radius)
03288 isconcave= True;
03289 else if (!iscoplanar && dist2 > -qh centrum_radius)
03290 iscoplanar= True;
03291 }
03292 if (!isconcave && (!iscoplanar || (qh MERGEexact && !qh POSTmerging)))
03293 return False;
03294 if (!okangle && qh ANGLEmerge) {
03295 angle= qh_getangle(facet->normal, neighbor->normal);
03296 zinc_(Zangletests);
03297 }
03298 if (isconcave) {
03299 zinc_(Zconcaveridge);
03300 if (qh ANGLEmerge)
03301 angle += qh_ANGLEconcave + 0.5;
03302 qh_appendmergeset(facet, neighbor, MRGconcave, &angle);
03303 trace0((qh ferr, "qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
03304 facet->id, neighbor->id, dist, dist2, angle, qh furthest_id));
03305 }else {
03306 zinc_(Zcoplanarcentrum);
03307 qh_appendmergeset(facet, neighbor, MRGcoplanar, &angle);
03308 trace2((qh ferr, "qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
03309 facet->id, neighbor->id, dist, dist2, angle));
03310 }
03311 return True;
03312 }
03313
03314
03315
03316
03317
03318
03319
03320
03321
03322
03323
03324
03325
03326
03327
03328
03329
03330
03331
03332
03333
03334
03335
03336
03337
03338
03339 boolT qh_test_vneighbors (void ) {
03340 facetT *newfacet, *neighbor, **neighborp;
03341 vertexT *vertex, **vertexp;
03342 int nummerges= 0;
03343
03344 trace1((qh ferr, "qh_test_vneighbors: testing vertex neighbors for convexity\n"));
03345 if (!qh VERTEXneighbors)
03346 qh_vertexneighbors();
03347 FORALLnew_facets
03348 newfacet->seen= False;
03349 FORALLnew_facets {
03350 newfacet->seen= True;
03351 newfacet->visitid= qh visit_id++;
03352 FOREACHneighbor_(newfacet)
03353 newfacet->visitid= qh visit_id;
03354 FOREACHvertex_(newfacet->vertices) {
03355 FOREACHneighbor_(vertex) {
03356 if (neighbor->seen || neighbor->visitid == qh visit_id)
03357 continue;
03358 if (qh_test_appendmerge (newfacet, neighbor))
03359 nummerges++;
03360 }
03361 }
03362 }
03363 zadd_(Ztestvneighbor, nummerges);
03364 trace1((qh ferr, "qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
03365 nummerges));
03366 return (nummerges > 0);
03367 }
03368
03369
03370
03371
03372
03373
03374
03375 void qh_tracemerge (facetT *facet1, facetT *facet2) {
03376 boolT waserror= False;
03377
03378 #ifndef qh_NOtrace
03379 if (qh IStracing >= 4)
03380 qh_errprint ("MERGED", facet2, NULL, NULL, NULL);
03381 if (facet2 == qh tracefacet || (qh tracevertex && qh tracevertex->newlist)) {
03382 fprintf (qh ferr, "qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->id, facet2->id, qh furthest_id);
03383 if (facet2 != qh tracefacet)
03384 qh_errprint ("TRACE", qh tracefacet,
03385 (qh tracevertex && qh tracevertex->neighbors) ?
03386 SETfirstt_(qh tracevertex->neighbors, facetT) : NULL,
03387 NULL, qh tracevertex);
03388 }
03389 if (qh tracevertex) {
03390 if (qh tracevertex->deleted)
03391 fprintf (qh ferr, "qh_tracemerge: trace vertex deleted at furthest p%d\n",
03392 qh furthest_id);
03393 else
03394 qh_checkvertex (qh tracevertex);
03395 }
03396 if (qh tracefacet) {
03397 qh_checkfacet (qh tracefacet, True, &waserror);
03398 if (waserror)
03399 qh_errexit (qh_ERRqhull, qh tracefacet, NULL);
03400 }
03401 #endif
03402 if (qh CHECKfrequently || qh IStracing >= 4) {
03403 qh_checkfacet (facet2, True, &waserror);
03404 if (waserror)
03405 qh_errexit(qh_ERRqhull, NULL, NULL);
03406 }
03407 }
03408
03409
03410
03411
03412
03413
03414
03415
03416
03417
03418
03419
03420
03421
03422
03423
03424 void qh_tracemerging (void) {
03425 realT cpu;
03426 int total;
03427 time_t timedata;
03428 struct tm *tp;
03429
03430 qh mergereport= zzval_(Ztotmerge);
03431 time (&timedata);
03432 tp= localtime (&timedata);
03433 cpu= qh_CPUclock;
03434 cpu /= qh_SECticks;
03435 total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
03436 fprintf (qh ferr, "\n\
03437 At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets. The hull\n\
03438 contains %d facets and %d vertices.\n",
03439 tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
03440 total, qh num_facets - qh num_visible,
03441 qh num_vertices-qh_setsize (qh del_vertices));
03442 }
03443
03444
03445
03446
03447
03448
03449
03450
03451
03452
03453
03454
03455
03456
03457
03458
03459
03460
03461
03462
03463
03464
03465
03466 void qh_updatetested (facetT *facet1, facetT *facet2) {
03467 ridgeT *ridge, **ridgep;
03468 int size;
03469
03470 facet2->tested= False;
03471 FOREACHridge_(facet1->ridges)
03472 ridge->tested= False;
03473 if (!facet2->center)
03474 return;
03475 size= qh_setsize (facet2->vertices);
03476 if (!facet2->keepcentrum) {
03477 if (size > qh hull_dim + qh_MAXnewcentrum) {
03478 facet2->keepcentrum= True;
03479 zinc_(Zwidevertices);
03480 }
03481 }else if (size <= qh hull_dim + qh_MAXnewcentrum) {
03482
03483 if (size == qh hull_dim || qh POSTmerging)
03484 facet2->keepcentrum= False;
03485 }
03486 if (!facet2->keepcentrum) {
03487 qh_memfree (facet2->center, qh normal_size);
03488 facet2->center= NULL;
03489 FOREACHridge_(facet2->ridges)
03490 ridge->tested= False;
03491 }
03492 }
03493
03494
03495
03496
03497
03498
03499
03500
03501
03502
03503
03504
03505
03506
03507
03508
03509 setT *qh_vertexridges (vertexT *vertex) {
03510 facetT *neighbor, **neighborp;
03511 setT *ridges= qh_settemp (qh TEMPsize);
03512 int size;
03513
03514 qh visit_id++;
03515 FOREACHneighbor_(vertex)
03516 neighbor->visitid= qh visit_id;
03517 FOREACHneighbor_(vertex) {
03518 if (*neighborp)
03519 qh_vertexridges_facet (vertex, neighbor, &ridges);
03520 }
03521 if (qh PRINTstatistics || qh IStracing) {
03522 size= qh_setsize (ridges);
03523 zinc_(Zvertexridge);
03524 zadd_(Zvertexridgetot, size);
03525 zmax_(Zvertexridgemax, size);
03526 trace3((qh ferr, "qh_vertexridges: found %d ridges for v%d\n",
03527 size, vertex->id));
03528 }
03529 return ridges;
03530 }
03531
03532
03533
03534
03535
03536
03537
03538
03539
03540
03541
03542
03543
03544
03545
03546
03547
03548
03549
03550 void qh_vertexridges_facet (vertexT *vertex, facetT *facet, setT **ridges) {
03551 ridgeT *ridge, **ridgep;
03552 facetT *neighbor;
03553
03554 FOREACHridge_(facet->ridges) {
03555 neighbor= otherfacet_(ridge, facet);
03556 if (neighbor->visitid == qh visit_id
03557 && qh_setin (ridge->vertices, vertex))
03558 qh_setappend (ridges, ridge);
03559 }
03560 facet->visitid= qh visit_id-1;
03561 }
03562
03563
03564
03565
03566
03567
03568
03569
03570
03571
03572
03573 void qh_willdelete (facetT *facet, facetT *replace) {
03574
03575 qh_removefacet(facet);
03576 qh_prependfacet (facet, &qh visible_list);
03577 qh num_visible++;
03578 facet->visible= True;
03579 facet->f.replace= replace;
03580 }
03581
03582 #else
03583 void qh_premerge (vertexT *apex, realT maxcentrum, realT maxangle) {
03584 }
03585 void qh_postmerge (char *reason, realT maxcentrum, realT maxangle,
03586 boolT vneighbors) {
03587 }
03588 boolT qh_checkzero (boolT testall) {
03589 }
03590 #endif
03591
