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