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