00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #include "qhull_a.h"
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 void qh_appendfacet(facetT *facet) {
00039 facetT *tail= qh facet_tail;
00040
00041 if (tail == qh newfacet_list)
00042 qh newfacet_list= facet;
00043 if (tail == qh facet_next)
00044 qh facet_next= facet;
00045 facet->previous= tail->previous;
00046 facet->next= tail;
00047 if (tail->previous)
00048 tail->previous->next= facet;
00049 else
00050 qh facet_list= facet;
00051 tail->previous= facet;
00052 qh num_facets++;
00053 trace4((qh ferr, 4044, "qh_appendfacet: append f%d to facet_list\n", facet->id));
00054 }
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072 void qh_appendvertex(vertexT *vertex) {
00073 vertexT *tail= qh vertex_tail;
00074
00075 if (tail == qh newvertex_list)
00076 qh newvertex_list= vertex;
00077 vertex->newlist= True;
00078 vertex->previous= tail->previous;
00079 vertex->next= tail;
00080 if (tail->previous)
00081 tail->previous->next= vertex;
00082 else
00083 qh vertex_list= vertex;
00084 tail->previous= vertex;
00085 qh num_vertices++;
00086 trace4((qh ferr, 4045, "qh_appendvertex: append v%d to vertex_list\n", vertex->id));
00087 }
00088
00089
00090
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_attachnewfacets(void ) {
00130 facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
00131 ridgeT *ridge, **ridgep;
00132
00133 qh NEWfacets= True;
00134 trace3((qh ferr, 3012, "qh_attachnewfacets: delete interior ridges\n"));
00135 qh visit_id++;
00136 FORALLvisible_facets {
00137 visible->visitid= qh visit_id;
00138 if (visible->ridges) {
00139 FOREACHridge_(visible->ridges) {
00140 neighbor= otherfacet_(ridge, visible);
00141 if (neighbor->visitid == qh visit_id
00142 || (!neighbor->visible && neighbor->simplicial)) {
00143 if (!neighbor->visible)
00144 qh_setdel(neighbor->ridges, ridge);
00145 qh_setfree(&(ridge->vertices));
00146 qh_memfree(ridge, (int)sizeof(ridgeT));
00147 }
00148 }
00149 SETfirst_(visible->ridges)= NULL;
00150 }
00151 SETfirst_(visible->neighbors)= NULL;
00152 }
00153 trace1((qh ferr, 1017, "qh_attachnewfacets: attach horizon facets to new facets\n"));
00154 FORALLnew_facets {
00155 horizon= SETfirstt_(newfacet->neighbors, facetT);
00156 if (horizon->simplicial) {
00157 visible= NULL;
00158 FOREACHneighbor_(horizon) {
00159 if (neighbor->visible) {
00160 if (visible) {
00161 if (qh_setequal_skip(newfacet->vertices, 0, horizon->vertices,
00162 SETindex_(horizon->neighbors, neighbor))) {
00163 visible= neighbor;
00164 break;
00165 }
00166 }else
00167 visible= neighbor;
00168 }
00169 }
00170 if (visible) {
00171 visible->f.replace= newfacet;
00172 qh_setreplace(horizon->neighbors, visible, newfacet);
00173 }else {
00174 qh_fprintf(qh ferr, 6102, "qhull internal error (qh_attachnewfacets): couldn't find visible facet for horizon f%d of newfacet f%d\n",
00175 horizon->id, newfacet->id);
00176 qh_errexit2 (qh_ERRqhull, horizon, newfacet);
00177 }
00178 }else {
00179 FOREACHneighbor_(horizon) {
00180 if (neighbor->visible) {
00181 neighbor->f.replace= newfacet;
00182 qh_setdelnth(horizon->neighbors,
00183 SETindex_(horizon->neighbors, neighbor));
00184 neighborp--;
00185 }
00186 }
00187 qh_setappend(&horizon->neighbors, newfacet);
00188 ridge= SETfirstt_(newfacet->ridges, ridgeT);
00189 if (ridge->top == horizon)
00190 ridge->bottom= newfacet;
00191 else
00192 ridge->top= newfacet;
00193 }
00194 }
00195 if (qh PRINTstatistics) {
00196 FORALLvisible_facets {
00197 if (!visible->f.replace)
00198 zinc_(Zinsidevisible);
00199 }
00200 }
00201 }
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218 boolT qh_checkflipped(facetT *facet, realT *distp, boolT allerror) {
00219 realT dist;
00220
00221 if (facet->flipped && !distp)
00222 return False;
00223 zzinc_(Zdistcheck);
00224 qh_distplane(qh interior_point, facet, &dist);
00225 if (distp)
00226 *distp= dist;
00227 if ((allerror && dist > -qh DISTround)|| (!allerror && dist >= 0.0)) {
00228 facet->flipped= True;
00229 zzinc_(Zflippedfacets);
00230 trace0((qh ferr, 19, "qh_checkflipped: facet f%d is flipped, distance= %6.12g during p%d\n",
00231 facet->id, dist, qh furthest_id));
00232 qh_precision("flipped facet");
00233 return False;
00234 }
00235 return True;
00236 }
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247 void qh_delfacet(facetT *facet) {
00248 void **freelistp;
00249
00250 trace4((qh ferr, 4046, "qh_delfacet: delete f%d\n", facet->id));
00251 if (facet == qh tracefacet)
00252 qh tracefacet= NULL;
00253 if (facet == qh GOODclosest)
00254 qh GOODclosest= NULL;
00255 qh_removefacet(facet);
00256 if (!facet->tricoplanar || facet->keepcentrum) {
00257 qh_memfree_(facet->normal, qh normal_size, freelistp);
00258 if (qh CENTERtype == qh_ASvoronoi) {
00259 qh_memfree_(facet->center, qh center_size, freelistp);
00260 }else {
00261 qh_memfree_(facet->center, qh normal_size, freelistp);
00262 }
00263 }
00264 qh_setfree(&(facet->neighbors));
00265 if (facet->ridges)
00266 qh_setfree(&(facet->ridges));
00267 qh_setfree(&(facet->vertices));
00268 if (facet->outsideset)
00269 qh_setfree(&(facet->outsideset));
00270 if (facet->coplanarset)
00271 qh_setfree(&(facet->coplanarset));
00272 qh_memfree_(facet, (int)sizeof(facetT), freelistp);
00273 }
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289
00290
00291
00292 void qh_deletevisible(void ) {
00293 facetT *visible, *nextfacet;
00294 vertexT *vertex, **vertexp;
00295 int numvisible= 0, numdel= qh_setsize(qh del_vertices);
00296
00297 trace1((qh ferr, 1018, "qh_deletevisible: delete %d visible facets and %d vertices\n",
00298 qh num_visible, numdel));
00299 for (visible= qh visible_list; visible && visible->visible;
00300 visible= nextfacet) {
00301 nextfacet= visible->next;
00302 numvisible++;
00303 qh_delfacet(visible);
00304 }
00305 if (numvisible != qh num_visible) {
00306 qh_fprintf(qh ferr, 6103, "qhull internal error (qh_deletevisible): qh num_visible %d is not number of visible facets %d\n",
00307 qh num_visible, numvisible);
00308 qh_errexit(qh_ERRqhull, NULL, NULL);
00309 }
00310 qh num_visible= 0;
00311 zadd_(Zvisfacettot, numvisible);
00312 zmax_(Zvisfacetmax, numvisible);
00313 zzadd_(Zdelvertextot, numdel);
00314 zmax_(Zdelvertexmax, numdel);
00315 FOREACHvertex_(qh del_vertices)
00316 qh_delvertex(vertex);
00317 qh_settruncate(qh del_vertices, 0);
00318 }
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343 setT *qh_facetintersect(facetT *facetA, facetT *facetB,
00344 int *skipA,int *skipB, int prepend) {
00345 setT *intersect;
00346 int dim= qh hull_dim, i, j;
00347 facetT **neighborsA, **neighborsB;
00348
00349 neighborsA= SETaddr_(facetA->neighbors, facetT);
00350 neighborsB= SETaddr_(facetB->neighbors, facetT);
00351 i= j= 0;
00352 if (facetB == *neighborsA++)
00353 *skipA= 0;
00354 else if (facetB == *neighborsA++)
00355 *skipA= 1;
00356 else if (facetB == *neighborsA++)
00357 *skipA= 2;
00358 else {
00359 for (i=3; i < dim; i++) {
00360 if (facetB == *neighborsA++) {
00361 *skipA= i;
00362 break;
00363 }
00364 }
00365 }
00366 if (facetA == *neighborsB++)
00367 *skipB= 0;
00368 else if (facetA == *neighborsB++)
00369 *skipB= 1;
00370 else if (facetA == *neighborsB++)
00371 *skipB= 2;
00372 else {
00373 for (j=3; j < dim; j++) {
00374 if (facetA == *neighborsB++) {
00375 *skipB= j;
00376 break;
00377 }
00378 }
00379 }
00380 if (i >= dim || j >= dim) {
00381 qh_fprintf(qh ferr, 6104, "qhull internal error (qh_facetintersect): f%d or f%d not in others neighbors\n",
00382 facetA->id, facetB->id);
00383 qh_errexit2 (qh_ERRqhull, facetA, facetB);
00384 }
00385 intersect= qh_setnew_delnthsorted(facetA->vertices, qh hull_dim, *skipA, prepend);
00386 trace4((qh ferr, 4047, "qh_facetintersect: f%d skip %d matches f%d skip %d\n",
00387 facetA->id, *skipA, facetB->id, *skipB));
00388 return(intersect);
00389 }
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405 int qh_gethash(int hashsize, setT *set, int size, int firstindex, void *skipelem) {
00406 void **elemp= SETelemaddr_(set, firstindex, void);
00407 ptr_intT hash = 0, elem;
00408 unsigned result;
00409 int i;
00410 #ifdef _MSC_VER
00411 #pragma warning( push)
00412 #pragma warning( disable : 4311)
00413 #endif
00414
00415 switch (size-firstindex) {
00416 case 1:
00417 hash= (ptr_intT)(*elemp) - (ptr_intT) skipelem;
00418 break;
00419 case 2:
00420 hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] - (ptr_intT) skipelem;
00421 break;
00422 case 3:
00423 hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00424 - (ptr_intT) skipelem;
00425 break;
00426 case 4:
00427 hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00428 + (ptr_intT)elemp[3] - (ptr_intT) skipelem;
00429 break;
00430 case 5:
00431 hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00432 + (ptr_intT)elemp[3] + (ptr_intT)elemp[4] - (ptr_intT) skipelem;
00433 break;
00434 case 6:
00435 hash= (ptr_intT)(*elemp) + (ptr_intT)elemp[1] + (ptr_intT)elemp[2]
00436 + (ptr_intT)elemp[3] + (ptr_intT)elemp[4]+ (ptr_intT)elemp[5]
00437 - (ptr_intT) skipelem;
00438 break;
00439 default:
00440 hash= 0;
00441 i= 3;
00442 do {
00443 if ((elem= (ptr_intT)*elemp++) != (ptr_intT)skipelem) {
00444 hash ^= (elem << i) + (elem >> (32-i));
00445 i += 3;
00446 if (i >= 32)
00447 i -= 32;
00448 }
00449 }while (*elemp);
00450 break;
00451 }
00452 if (hashsize<0) {
00453 qh_fprintf(qh ferr, 6232, "qhull internal error: negative hashsize %d passed to qh_gethash [poly.c]\n", hashsize);
00454 qh_errexit2 (qh_ERRqhull, NULL, NULL);
00455 }
00456 result= (unsigned)hash;
00457 result %= (unsigned)hashsize;
00458
00459 return result;
00460 #ifdef _MSC_VER
00461 #pragma warning( pop)
00462 #endif
00463 }
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479 facetT *qh_makenewfacet(setT *vertices, boolT toporient,facetT *horizon) {
00480 facetT *newfacet;
00481 vertexT *vertex, **vertexp;
00482
00483 FOREACHvertex_(vertices) {
00484 if (!vertex->newlist) {
00485 qh_removevertex(vertex);
00486 qh_appendvertex(vertex);
00487 }
00488 }
00489 newfacet= qh_newfacet();
00490 newfacet->vertices= vertices;
00491 newfacet->toporient= (unsigned char)toporient;
00492 if (horizon)
00493 qh_setappend(&(newfacet->neighbors), horizon);
00494 qh_appendfacet(newfacet);
00495 return(newfacet);
00496 }
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513 void qh_makenewplanes(void ) {
00514 facetT *newfacet;
00515
00516 FORALLnew_facets {
00517 if (!newfacet->mergehorizon)
00518 qh_setfacetplane(newfacet);
00519 }
00520 if (qh JOGGLEmax < REALmax/2)
00521 minimize_(qh min_vertex, -wwval_(Wnewvertexmax));
00522 }
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562 #ifndef qh_NOmerge
00563 facetT *qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew) {
00564 void **freelistp;
00565 ridgeT *ridge, **ridgep;
00566 facetT *neighbor, *newfacet= NULL, *samecycle;
00567 setT *vertices;
00568 boolT toporient;
00569 int ridgeid;
00570
00571 FOREACHridge_(visible->ridges) {
00572 ridgeid= ridge->id;
00573 neighbor= otherfacet_(ridge, visible);
00574 if (neighbor->visible) {
00575 if (!qh ONLYgood) {
00576 if (neighbor->visitid == qh visit_id) {
00577 qh_setfree(&(ridge->vertices));
00578 qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
00579 }
00580 }
00581 }else {
00582 toporient= (ridge->top == visible);
00583 vertices= qh_setnew(qh hull_dim);
00584 qh_setappend(&vertices, apex);
00585 qh_setappend_set(&vertices, ridge->vertices);
00586 newfacet= qh_makenewfacet(vertices, toporient, neighbor);
00587 (*numnew)++;
00588 if (neighbor->coplanar) {
00589 newfacet->mergehorizon= True;
00590 if (!neighbor->seen) {
00591 newfacet->f.samecycle= newfacet;
00592 neighbor->f.newcycle= newfacet;
00593 }else {
00594 samecycle= neighbor->f.newcycle;
00595 newfacet->f.samecycle= samecycle->f.samecycle;
00596 samecycle->f.samecycle= newfacet;
00597 }
00598 }
00599 if (qh ONLYgood) {
00600 if (!neighbor->simplicial)
00601 qh_setappend(&(newfacet->ridges), ridge);
00602 }else {
00603 if (neighbor->seen) {
00604 if (neighbor->simplicial) {
00605 qh_fprintf(qh ferr, 6105, "qhull internal error (qh_makenew_nonsimplicial): simplicial f%d sharing two ridges with f%d\n",
00606 neighbor->id, visible->id);
00607 qh_errexit2 (qh_ERRqhull, neighbor, visible);
00608 }
00609 qh_setappend(&(neighbor->neighbors), newfacet);
00610 }else
00611 qh_setreplace(neighbor->neighbors, visible, newfacet);
00612 if (neighbor->simplicial) {
00613 qh_setdel(neighbor->ridges, ridge);
00614 qh_setfree(&(ridge->vertices));
00615 qh_memfree(ridge, (int)sizeof(ridgeT));
00616 }else {
00617 qh_setappend(&(newfacet->ridges), ridge);
00618 if (toporient)
00619 ridge->top= newfacet;
00620 else
00621 ridge->bottom= newfacet;
00622 }
00623 trace4((qh ferr, 4048, "qh_makenew_nonsimplicial: created facet f%d from v%d and r%d of horizon f%d\n",
00624 newfacet->id, apex->id, ridgeid, neighbor->id));
00625 }
00626 }
00627 neighbor->seen= True;
00628 }
00629 if (!qh ONLYgood)
00630 SETfirst_(visible->ridges)= NULL;
00631 return newfacet;
00632 }
00633 #else
00634 facetT *qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew) {
00635 return NULL;
00636 }
00637 #endif
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660 facetT *qh_makenew_simplicial(facetT *visible, vertexT *apex, int *numnew) {
00661 facetT *neighbor, **neighborp, *newfacet= NULL;
00662 setT *vertices;
00663 boolT flip, toporient;
00664 int horizonskip, visibleskip;
00665
00666 FOREACHneighbor_(visible) {
00667 if (!neighbor->seen && !neighbor->visible) {
00668 vertices= qh_facetintersect(neighbor,visible, &horizonskip, &visibleskip, 1);
00669 SETfirst_(vertices)= apex;
00670 flip= ((horizonskip & 0x1) ^ (visibleskip & 0x1));
00671 if (neighbor->toporient)
00672 toporient= horizonskip & 0x1;
00673 else
00674 toporient= (horizonskip & 0x1) ^ 0x1;
00675 newfacet= qh_makenewfacet(vertices, toporient, neighbor);
00676 (*numnew)++;
00677 if (neighbor->coplanar && (qh PREmerge || qh MERGEexact)) {
00678 #ifndef qh_NOmerge
00679 newfacet->f.samecycle= newfacet;
00680 newfacet->mergehorizon= True;
00681 #endif
00682 }
00683 if (!qh ONLYgood)
00684 SETelem_(neighbor->neighbors, horizonskip)= newfacet;
00685 trace4((qh ferr, 4049, "qh_makenew_simplicial: create facet f%d top %d from v%d and horizon f%d skip %d top %d and visible f%d skip %d, flip? %d\n",
00686 newfacet->id, toporient, apex->id, neighbor->id, horizonskip,
00687 neighbor->toporient, visible->id, visibleskip, flip));
00688 }
00689 }
00690 return newfacet;
00691 }
00692
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724 void qh_matchneighbor(facetT *newfacet, int newskip, int hashsize, int *hashcount) {
00725 boolT newfound= False;
00726 boolT same, ismatch;
00727 int hash, scan;
00728 facetT *facet, *matchfacet;
00729 int skip, matchskip;
00730
00731 hash= qh_gethash(hashsize, newfacet->vertices, qh hull_dim, 1,
00732 SETelem_(newfacet->vertices, newskip));
00733 trace4((qh ferr, 4050, "qh_matchneighbor: newfacet f%d skip %d hash %d hashcount %d\n",
00734 newfacet->id, newskip, hash, *hashcount));
00735 zinc_(Zhashlookup);
00736 for (scan= hash; (facet= SETelemt_(qh hash_table, scan, facetT));
00737 scan= (++scan >= hashsize ? 0 : scan)) {
00738 if (facet == newfacet) {
00739 newfound= True;
00740 continue;
00741 }
00742 zinc_(Zhashtests);
00743 if (qh_matchvertices(1, newfacet->vertices, newskip, facet->vertices, &skip, &same)) {
00744 if (SETelem_(newfacet->vertices, newskip) ==
00745 SETelem_(facet->vertices, skip)) {
00746 qh_precision("two facets with the same vertices");
00747 qh_fprintf(qh ferr, 6106, "qhull precision error: Vertex sets are the same for f%d and f%d. Can not force output.\n",
00748 facet->id, newfacet->id);
00749 qh_errexit2 (qh_ERRprec, facet, newfacet);
00750 }
00751 ismatch= (same == (boolT)((newfacet->toporient ^ facet->toporient)));
00752 matchfacet= SETelemt_(facet->neighbors, skip, facetT);
00753 if (ismatch && !matchfacet) {
00754 SETelem_(facet->neighbors, skip)= newfacet;
00755 SETelem_(newfacet->neighbors, newskip)= facet;
00756 (*hashcount)--;
00757 trace4((qh ferr, 4051, "qh_matchneighbor: f%d skip %d matched with new f%d skip %d\n",
00758 facet->id, skip, newfacet->id, newskip));
00759 return;
00760 }
00761 if (!qh PREmerge && !qh MERGEexact) {
00762 qh_precision("a ridge with more than two neighbors");
00763 qh_fprintf(qh ferr, 6107, "qhull precision error: facets f%d, f%d and f%d meet at a ridge with more than 2 neighbors. Can not continue.\n",
00764 facet->id, newfacet->id, getid_(matchfacet));
00765 qh_errexit2 (qh_ERRprec, facet, newfacet);
00766 }
00767 SETelem_(newfacet->neighbors, newskip)= qh_DUPLICATEridge;
00768 newfacet->dupridge= True;
00769 if (!newfacet->normal)
00770 qh_setfacetplane(newfacet);
00771 qh_addhash(newfacet, qh hash_table, hashsize, hash);
00772 (*hashcount)++;
00773 if (!facet->normal)
00774 qh_setfacetplane(facet);
00775 if (matchfacet != qh_DUPLICATEridge) {
00776 SETelem_(facet->neighbors, skip)= qh_DUPLICATEridge;
00777 facet->dupridge= True;
00778 if (!facet->normal)
00779 qh_setfacetplane(facet);
00780 if (matchfacet) {
00781 matchskip= qh_setindex(matchfacet->neighbors, facet);
00782 SETelem_(matchfacet->neighbors, matchskip)= qh_DUPLICATEridge;
00783 matchfacet->dupridge= True;
00784 if (!matchfacet->normal)
00785 qh_setfacetplane(matchfacet);
00786 qh_addhash(matchfacet, qh hash_table, hashsize, hash);
00787 *hashcount += 2;
00788 }
00789 }
00790 trace4((qh ferr, 4052, "qh_matchneighbor: new f%d skip %d duplicates ridge for f%d skip %d matching f%d ismatch %d at hash %d\n",
00791 newfacet->id, newskip, facet->id, skip,
00792 (matchfacet == qh_DUPLICATEridge ? -2 : getid_(matchfacet)),
00793 ismatch, hash));
00794 return;
00795 }
00796 }
00797 if (!newfound)
00798 SETelem_(qh hash_table, scan)= newfacet;
00799 (*hashcount)++;
00800 trace4((qh ferr, 4053, "qh_matchneighbor: no match for f%d skip %d at hash %d\n",
00801 newfacet->id, newskip, hash));
00802 }
00803
00804
00805
00806
00807
00808
00809
00810
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830
00831
00832
00833
00834
00835
00836 void qh_matchnewfacets(void ) {
00837 int numnew=0, hashcount=0, newskip;
00838 facetT *newfacet, *neighbor;
00839 int dim= qh hull_dim, hashsize, neighbor_i, neighbor_n;
00840 setT *neighbors;
00841 #ifndef qh_NOtrace
00842 int facet_i, facet_n, numfree= 0;
00843 facetT *facet;
00844 #endif
00845
00846 trace1((qh ferr, 1019, "qh_matchnewfacets: match neighbors for new facets.\n"));
00847 FORALLnew_facets {
00848 numnew++;
00849 {
00850 neighbors= newfacet->neighbors;
00851 neighbors->e[neighbors->maxsize].i= dim+1;
00852 memset((char *)SETelemaddr_(neighbors, 1, void), 0, dim * SETelemsize);
00853 }
00854 }
00855
00856 qh_newhashtable(numnew*(qh hull_dim-1));
00857
00858 hashsize= qh_setsize(qh hash_table);
00859 FORALLnew_facets {
00860 for (newskip=1; newskip<qh hull_dim; newskip++)
00861 qh_matchneighbor(newfacet, newskip, hashsize, &hashcount);
00862 #if 0
00863 {
00864 int count= 0, k;
00865 facetT *facet, *neighbor;
00866
00867 count= 0;
00868 FORALLfacet_(qh newfacet_list) {
00869 for (k=1; k < qh hull_dim; k++) {
00870 neighbor= SETelemt_(facet->neighbors, k, facetT);
00871 if (!neighbor || neighbor == qh_DUPLICATEridge)
00872 count++;
00873 }
00874 if (facet == newfacet)
00875 break;
00876 }
00877 if (count != hashcount) {
00878 qh_fprintf(qh ferr, 8088, "qh_matchnewfacets: after adding facet %d, hashcount %d != count %d\n",
00879 newfacet->id, hashcount, count);
00880 qh_errexit(qh_ERRqhull, newfacet, NULL);
00881 }
00882 }
00883 #endif
00884 }
00885 if (hashcount) {
00886 FORALLnew_facets {
00887 if (newfacet->dupridge) {
00888 FOREACHneighbor_i_(newfacet) {
00889 if (neighbor == qh_DUPLICATEridge) {
00890 qh_matchduplicates(newfacet, neighbor_i, hashsize, &hashcount);
00891
00892 }
00893 }
00894 }
00895 }
00896 }
00897 if (hashcount) {
00898 qh_fprintf(qh ferr, 6108, "qhull internal error (qh_matchnewfacets): %d neighbors did not match up\n",
00899 hashcount);
00900 qh_printhashtable(qh ferr);
00901 qh_errexit(qh_ERRqhull, NULL, NULL);
00902 }
00903 #ifndef qh_NOtrace
00904 if (qh IStracing >= 2) {
00905 FOREACHfacet_i_(qh hash_table) {
00906 if (!facet)
00907 numfree++;
00908 }
00909 qh_fprintf(qh ferr, 8089, "qh_matchnewfacets: %d new facets, %d unused hash entries . hashsize %d\n",
00910 numnew, numfree, qh_setsize(qh hash_table));
00911 }
00912 #endif
00913 qh_setfree(&qh hash_table);
00914 if (qh PREmerge || qh MERGEexact) {
00915 if (qh IStracing >= 4)
00916 qh_printfacetlist(qh newfacet_list, NULL, qh_ALL);
00917 FORALLnew_facets {
00918 if (newfacet->normal)
00919 qh_checkflipped(newfacet, NULL, qh_ALL);
00920 }
00921 }else if (qh FORCEoutput)
00922 qh_checkflipped_all(qh newfacet_list);
00923 }
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944
00945
00946 boolT qh_matchvertices(int firstindex, setT *verticesA, int skipA,
00947 setT *verticesB, int *skipB, boolT *same) {
00948 vertexT **elemAp, **elemBp, **skipBp=NULL, **skipAp;
00949
00950 elemAp= SETelemaddr_(verticesA, firstindex, vertexT);
00951 elemBp= SETelemaddr_(verticesB, firstindex, vertexT);
00952 skipAp= SETelemaddr_(verticesA, skipA, vertexT);
00953 do if (elemAp != skipAp) {
00954 while (*elemAp != *elemBp++) {
00955 if (skipBp)
00956 return False;
00957 skipBp= elemBp;
00958 }
00959 }while (*(++elemAp));
00960 if (!skipBp)
00961 skipBp= ++elemBp;
00962 *skipB= SETindex_(verticesB, skipB);
00963 *same= !((skipA & 0x1) ^ (*skipB & 0x1));
00964 trace4((qh ferr, 4054, "qh_matchvertices: matched by skip %d(v%d) and skip %d(v%d) same? %d\n",
00965 skipA, (*skipAp)->id, *skipB, (*(skipBp-1))->id, *same));
00966 return(True);
00967 }
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979 facetT *qh_newfacet(void) {
00980 facetT *facet;
00981 void **freelistp;
00982
00983 qh_memalloc_((int)sizeof(facetT), freelistp, facet, facetT);
00984 memset((char *)facet, (size_t)0, sizeof(facetT));
00985 if (qh facet_id == qh tracefacet_id)
00986 qh tracefacet= facet;
00987 facet->id= qh facet_id++;
00988 facet->neighbors= qh_setnew(qh hull_dim);
00989 #if !qh_COMPUTEfurthest
00990 facet->furthestdist= 0.0;
00991 #endif
00992 #if qh_MAXoutside
00993 if (qh FORCEoutput && qh APPROXhull)
00994 facet->maxoutside= qh MINoutside;
00995 else
00996 facet->maxoutside= qh DISTround;
00997 #endif
00998 facet->simplicial= True;
00999 facet->good= True;
01000 facet->newfacet= True;
01001 trace4((qh ferr, 4055, "qh_newfacet: created facet f%d\n", facet->id));
01002 return(facet);
01003 }
01004
01005
01006
01007
01008
01009
01010
01011
01012 ridgeT *qh_newridge(void) {
01013 ridgeT *ridge;
01014 void **freelistp;
01015
01016 qh_memalloc_((int)sizeof(ridgeT), freelistp, ridge, ridgeT);
01017 memset((char *)ridge, (size_t)0, sizeof(ridgeT));
01018 zinc_(Ztotridges);
01019 if (qh ridge_id == 0xFFFFFF) {
01020 qh_fprintf(qh ferr, 7074, "\
01021 qhull warning: more than %d ridges. ID field overflows and two ridges\n\
01022 may have the same identifier. Otherwise output ok.\n", 0xFFFFFF);
01023 }
01024 ridge->id= qh ridge_id++;
01025 trace4((qh ferr, 4056, "qh_newridge: created ridge r%d\n", ridge->id));
01026 return(ridge);
01027 }
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044
01045
01046
01047 int qh_pointid(pointT *point) {
01048 ptr_intT offset, id;
01049
01050 if (!point)
01051 return -3;
01052 else if (point == qh interior_point)
01053 return -2;
01054 else if (point >= qh first_point
01055 && point < qh first_point + qh num_points * qh hull_dim) {
01056 offset= (ptr_intT)(point - qh first_point);
01057 id= offset / qh hull_dim;
01058 }else if ((id= qh_setindex(qh other_points, point)) != -1)
01059 id += qh num_points;
01060 else
01061 return -1;
01062 return (int)id;
01063 }
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077
01078 void qh_removefacet(facetT *facet) {
01079 facetT *next= facet->next, *previous= facet->previous;
01080
01081 if (facet == qh newfacet_list)
01082 qh newfacet_list= next;
01083 if (facet == qh facet_next)
01084 qh facet_next= next;
01085 if (facet == qh visible_list)
01086 qh visible_list= next;
01087 if (previous) {
01088 previous->next= next;
01089 next->previous= previous;
01090 }else {
01091 qh facet_list= next;
01092 qh facet_list->previous= NULL;
01093 }
01094 qh num_facets--;
01095 trace4((qh ferr, 4057, "qh_removefacet: remove f%d from facet_list\n", facet->id));
01096 }
01097
01098
01099
01100
01101
01102
01103
01104
01105
01106
01107
01108
01109 void qh_removevertex(vertexT *vertex) {
01110 vertexT *next= vertex->next, *previous= vertex->previous;
01111
01112 if (vertex == qh newvertex_list)
01113 qh newvertex_list= next;
01114 if (previous) {
01115 previous->next= next;
01116 next->previous= previous;
01117 }else {
01118 qh vertex_list= vertex->next;
01119 qh vertex_list->previous= NULL;
01120 }
01121 qh num_vertices--;
01122 trace4((qh ferr, 4058, "qh_removevertex: remove v%d from vertex_list\n", vertex->id));
01123 }
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
01136
01137
01138
01139
01140
01141
01142
01143
01144
01145
01146
01147
01148
01149 void qh_updatevertices(void ) {
01150 facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
01151 vertexT *vertex, **vertexp;
01152
01153 trace3((qh ferr, 3013, "qh_updatevertices: delete interior vertices and update vertex->neighbors\n"));
01154 if (qh VERTEXneighbors) {
01155 FORALLvertex_(qh newvertex_list) {
01156 FOREACHneighbor_(vertex) {
01157 if (neighbor->visible)
01158 SETref_(neighbor)= NULL;
01159 }
01160 qh_setcompact(vertex->neighbors);
01161 }
01162 FORALLnew_facets {
01163 FOREACHvertex_(newfacet->vertices)
01164 qh_setappend(&vertex->neighbors, newfacet);
01165 }
01166 FORALLvisible_facets {
01167 FOREACHvertex_(visible->vertices) {
01168 if (!vertex->newlist && !vertex->deleted) {
01169 FOREACHneighbor_(vertex) {
01170 if (!neighbor->visible)
01171 break;
01172 }
01173 if (neighbor)
01174 qh_setdel(vertex->neighbors, visible);
01175 else {
01176 vertex->deleted= True;
01177 qh_setappend(&qh del_vertices, vertex);
01178 trace2((qh ferr, 2041, "qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
01179 qh_pointid(vertex->point), vertex->id, visible->id));
01180 }
01181 }
01182 }
01183 }
01184 }else {
01185 FORALLvisible_facets {
01186 FOREACHvertex_(visible->vertices) {
01187 if (!vertex->newlist && !vertex->deleted) {
01188 vertex->deleted= True;
01189 qh_setappend(&qh del_vertices, vertex);
01190 trace2((qh ferr, 2042, "qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
01191 qh_pointid(vertex->point), vertex->id, visible->id));
01192 }
01193 }
01194 }
01195 }
01196 }
01197
01198
01199