| 1 | /*<html><pre> -<a href="qh-merge.htm#TOC"
|
|---|
| 2 | >-------------------------------</a><a name="TOP">-</a>
|
|---|
| 3 |
|
|---|
| 4 | merge.c
|
|---|
| 5 | merges non-convex facets
|
|---|
| 6 |
|
|---|
| 7 | see qh-merge.htm and merge.h
|
|---|
| 8 |
|
|---|
| 9 | other modules call qh_premerge() and qh_postmerge()
|
|---|
| 10 |
|
|---|
| 11 | the user may call qh_postmerge() to perform additional merges.
|
|---|
| 12 |
|
|---|
| 13 | To remove deleted facets and vertices (qhull() in libqhull.c):
|
|---|
| 14 | qh_partitionvisible(!qh_ALL, &numoutside); // visible_list, newfacet_list
|
|---|
| 15 | qh_deletevisible(); // qh.visible_list
|
|---|
| 16 | qh_resetlists(False, qh_RESETvisible); // qh.visible_list newvertex_list newfacet_list
|
|---|
| 17 |
|
|---|
| 18 | assumes qh.CENTERtype= centrum
|
|---|
| 19 |
|
|---|
| 20 | merges occur in qh_mergefacet and in qh_mergecycle
|
|---|
| 21 | vertex->neighbors not set until the first merge occurs
|
|---|
| 22 |
|
|---|
| 23 | Copyright (c) 1993-2012 C.B. Barber.
|
|---|
| 24 | $Id: //main/2011/qhull/src/libqhull/merge.c#4 $$Change: 1490 $
|
|---|
| 25 | $DateTime: 2012/02/19 20:27:01 $$Author: bbarber $
|
|---|
| 26 | */
|
|---|
| 27 |
|
|---|
| 28 | #include "qhull_a.h"
|
|---|
| 29 |
|
|---|
| 30 | #ifndef qh_NOmerge
|
|---|
| 31 |
|
|---|
| 32 | /*===== functions(alphabetical after premerge and postmerge) ======*/
|
|---|
| 33 |
|
|---|
| 34 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 35 | >-------------------------------</a><a name="premerge">-</a>
|
|---|
| 36 |
|
|---|
| 37 | qh_premerge( apex, maxcentrum )
|
|---|
| 38 | pre-merge nonconvex facets in qh.newfacet_list for apex
|
|---|
| 39 | maxcentrum defines coplanar and concave (qh_test_appendmerge)
|
|---|
| 40 |
|
|---|
| 41 | returns:
|
|---|
| 42 | deleted facets added to qh.visible_list with facet->visible set
|
|---|
| 43 |
|
|---|
| 44 | notes:
|
|---|
| 45 | uses globals, qh.MERGEexact, qh.PREmerge
|
|---|
| 46 |
|
|---|
| 47 | design:
|
|---|
| 48 | mark duplicate ridges in qh.newfacet_list
|
|---|
| 49 | merge facet cycles in qh.newfacet_list
|
|---|
| 50 | merge duplicate ridges and concave facets in qh.newfacet_list
|
|---|
| 51 | check merged facet cycles for degenerate and redundant facets
|
|---|
| 52 | merge degenerate and redundant facets
|
|---|
| 53 | collect coplanar and concave facets
|
|---|
| 54 | merge concave, coplanar, degenerate, and redundant facets
|
|---|
| 55 | */
|
|---|
| 56 | void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
|
|---|
| 57 | boolT othermerge= False;
|
|---|
| 58 | facetT *newfacet;
|
|---|
| 59 |
|
|---|
| 60 | if (qh ZEROcentrum && qh_checkzero(!qh_ALL))
|
|---|
| 61 | return;
|
|---|
| 62 | trace2((qh ferr, 2008, "qh_premerge: premerge centrum %2.2g angle %2.2g for apex v%d facetlist f%d\n",
|
|---|
| 63 | maxcentrum, maxangle, apex->id, getid_(qh newfacet_list)));
|
|---|
| 64 | if (qh IStracing >= 4 && qh num_facets < 50)
|
|---|
| 65 | qh_printlists();
|
|---|
| 66 | qh centrum_radius= maxcentrum;
|
|---|
| 67 | qh cos_max= maxangle;
|
|---|
| 68 | qh degen_mergeset= qh_settemp(qh TEMPsize);
|
|---|
| 69 | qh facet_mergeset= qh_settemp(qh TEMPsize);
|
|---|
| 70 | if (qh hull_dim >=3) {
|
|---|
| 71 | qh_mark_dupridges(qh newfacet_list); /* facet_mergeset */
|
|---|
| 72 | qh_mergecycle_all(qh newfacet_list, &othermerge);
|
|---|
| 73 | qh_forcedmerges(&othermerge /* qh facet_mergeset */);
|
|---|
| 74 | FORALLnew_facets { /* test samecycle merges */
|
|---|
| 75 | if (!newfacet->simplicial && !newfacet->mergeridge)
|
|---|
| 76 | qh_degen_redundant_neighbors(newfacet, NULL);
|
|---|
| 77 | }
|
|---|
| 78 | if (qh_merge_degenredundant())
|
|---|
| 79 | othermerge= True;
|
|---|
| 80 | }else /* qh hull_dim == 2 */
|
|---|
| 81 | qh_mergecycle_all(qh newfacet_list, &othermerge);
|
|---|
| 82 | qh_flippedmerges(qh newfacet_list, &othermerge);
|
|---|
| 83 | if (!qh MERGEexact || zzval_(Ztotmerge)) {
|
|---|
| 84 | zinc_(Zpremergetot);
|
|---|
| 85 | qh POSTmerging= False;
|
|---|
| 86 | qh_getmergeset_initial(qh newfacet_list);
|
|---|
| 87 | qh_all_merges(othermerge, False);
|
|---|
| 88 | }
|
|---|
| 89 | qh_settempfree(&qh facet_mergeset);
|
|---|
| 90 | qh_settempfree(&qh degen_mergeset);
|
|---|
| 91 | } /* premerge */
|
|---|
| 92 |
|
|---|
| 93 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 94 | >-------------------------------</a><a name="postmerge">-</a>
|
|---|
| 95 |
|
|---|
| 96 | qh_postmerge( reason, maxcentrum, maxangle, vneighbors )
|
|---|
| 97 | post-merge nonconvex facets as defined by maxcentrum and maxangle
|
|---|
| 98 | 'reason' is for reporting progress
|
|---|
| 99 | if vneighbors,
|
|---|
| 100 | calls qh_test_vneighbors at end of qh_all_merge
|
|---|
| 101 | if firstmerge,
|
|---|
| 102 | calls qh_reducevertices before qh_getmergeset
|
|---|
| 103 |
|
|---|
| 104 | returns:
|
|---|
| 105 | if first call (qh.visible_list != qh.facet_list),
|
|---|
| 106 | builds qh.facet_newlist, qh.newvertex_list
|
|---|
| 107 | deleted facets added to qh.visible_list with facet->visible
|
|---|
| 108 | qh.visible_list == qh.facet_list
|
|---|
| 109 |
|
|---|
| 110 | notes:
|
|---|
| 111 |
|
|---|
| 112 |
|
|---|
| 113 | design:
|
|---|
| 114 | if first call
|
|---|
| 115 | set qh.visible_list and qh.newfacet_list to qh.facet_list
|
|---|
| 116 | add all facets to qh.newfacet_list
|
|---|
| 117 | mark non-simplicial facets, facet->newmerge
|
|---|
| 118 | set qh.newvertext_list to qh.vertex_list
|
|---|
| 119 | add all vertices to qh.newvertex_list
|
|---|
| 120 | if a pre-merge occured
|
|---|
| 121 | set vertex->delridge {will retest the ridge}
|
|---|
| 122 | if qh.MERGEexact
|
|---|
| 123 | call qh_reducevertices()
|
|---|
| 124 | if no pre-merging
|
|---|
| 125 | merge flipped facets
|
|---|
| 126 | determine non-convex facets
|
|---|
| 127 | merge all non-convex facets
|
|---|
| 128 | */
|
|---|
| 129 | void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
|
|---|
| 130 | boolT vneighbors) {
|
|---|
| 131 | facetT *newfacet;
|
|---|
| 132 | boolT othermerges= False;
|
|---|
| 133 | vertexT *vertex;
|
|---|
| 134 |
|
|---|
| 135 | if (qh REPORTfreq || qh IStracing) {
|
|---|
| 136 | qh_buildtracing(NULL, NULL);
|
|---|
| 137 | qh_printsummary(qh ferr);
|
|---|
| 138 | if (qh PRINTstatistics)
|
|---|
| 139 | qh_printallstatistics(qh ferr, "reason");
|
|---|
| 140 | qh_fprintf(qh ferr, 8062, "\n%s with 'C%.2g' and 'A%.2g'\n",
|
|---|
| 141 | reason, maxcentrum, maxangle);
|
|---|
| 142 | }
|
|---|
| 143 | trace2((qh ferr, 2009, "qh_postmerge: postmerge. test vneighbors? %d\n",
|
|---|
| 144 | vneighbors));
|
|---|
| 145 | qh centrum_radius= maxcentrum;
|
|---|
| 146 | qh cos_max= maxangle;
|
|---|
| 147 | qh POSTmerging= True;
|
|---|
| 148 | qh degen_mergeset= qh_settemp(qh TEMPsize);
|
|---|
| 149 | qh facet_mergeset= qh_settemp(qh TEMPsize);
|
|---|
| 150 | if (qh visible_list != qh facet_list) { /* first call */
|
|---|
| 151 | qh NEWfacets= True;
|
|---|
| 152 | qh visible_list= qh newfacet_list= qh facet_list;
|
|---|
| 153 | FORALLnew_facets {
|
|---|
| 154 | newfacet->newfacet= True;
|
|---|
| 155 | if (!newfacet->simplicial)
|
|---|
| 156 | newfacet->newmerge= True;
|
|---|
| 157 | zinc_(Zpostfacets);
|
|---|
| 158 | }
|
|---|
| 159 | qh newvertex_list= qh vertex_list;
|
|---|
| 160 | FORALLvertices
|
|---|
| 161 | vertex->newlist= True;
|
|---|
| 162 | if (qh VERTEXneighbors) { /* a merge has occurred */
|
|---|
| 163 | FORALLvertices
|
|---|
| 164 | vertex->delridge= True; /* test for redundant, needed? */
|
|---|
| 165 | if (qh MERGEexact) {
|
|---|
| 166 | if (qh hull_dim <= qh_DIMreduceBuild)
|
|---|
| 167 | qh_reducevertices(); /* was skipped during pre-merging */
|
|---|
| 168 | }
|
|---|
| 169 | }
|
|---|
| 170 | if (!qh PREmerge && !qh MERGEexact)
|
|---|
| 171 | qh_flippedmerges(qh newfacet_list, &othermerges);
|
|---|
| 172 | }
|
|---|
| 173 | qh_getmergeset_initial(qh newfacet_list);
|
|---|
| 174 | qh_all_merges(False, vneighbors);
|
|---|
| 175 | qh_settempfree(&qh facet_mergeset);
|
|---|
| 176 | qh_settempfree(&qh degen_mergeset);
|
|---|
| 177 | } /* post_merge */
|
|---|
| 178 |
|
|---|
| 179 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 180 | >-------------------------------</a><a name="all_merges">-</a>
|
|---|
| 181 |
|
|---|
| 182 | qh_all_merges( othermerge, vneighbors )
|
|---|
| 183 | merge all non-convex facets
|
|---|
| 184 |
|
|---|
| 185 | set othermerge if already merged facets (for qh_reducevertices)
|
|---|
| 186 | if vneighbors
|
|---|
| 187 | tests vertex neighbors for convexity at end
|
|---|
| 188 | qh.facet_mergeset lists the non-convex ridges in qh_newfacet_list
|
|---|
| 189 | qh.degen_mergeset is defined
|
|---|
| 190 | if qh.MERGEexact && !qh.POSTmerging,
|
|---|
| 191 | does not merge coplanar facets
|
|---|
| 192 |
|
|---|
| 193 | returns:
|
|---|
| 194 | deleted facets added to qh.visible_list with facet->visible
|
|---|
| 195 | deleted vertices added qh.delvertex_list with vertex->delvertex
|
|---|
| 196 |
|
|---|
| 197 | notes:
|
|---|
| 198 | unless !qh.MERGEindependent,
|
|---|
| 199 | merges facets in independent sets
|
|---|
| 200 | uses qh.newfacet_list as argument since merges call qh_removefacet()
|
|---|
| 201 |
|
|---|
| 202 | design:
|
|---|
| 203 | while merges occur
|
|---|
| 204 | for each merge in qh.facet_mergeset
|
|---|
| 205 | unless one of the facets was already merged in this pass
|
|---|
| 206 | merge the facets
|
|---|
| 207 | test merged facets for additional merges
|
|---|
| 208 | add merges to qh.facet_mergeset
|
|---|
| 209 | if vertices record neighboring facets
|
|---|
| 210 | rename redundant vertices
|
|---|
| 211 | update qh.facet_mergeset
|
|---|
| 212 | if vneighbors ??
|
|---|
| 213 | tests vertex neighbors for convexity at end
|
|---|
| 214 | */
|
|---|
| 215 | void qh_all_merges(boolT othermerge, boolT vneighbors) {
|
|---|
| 216 | facetT *facet1, *facet2;
|
|---|
| 217 | mergeT *merge;
|
|---|
| 218 | boolT wasmerge= True, isreduce;
|
|---|
| 219 | void **freelistp; /* used !qh_NOmem */
|
|---|
| 220 | vertexT *vertex;
|
|---|
| 221 | mergeType mergetype;
|
|---|
| 222 | int numcoplanar=0, numconcave=0, numdegenredun= 0, numnewmerges= 0;
|
|---|
| 223 |
|
|---|
| 224 | trace2((qh ferr, 2010, "qh_all_merges: starting to merge facets beginning from f%d\n",
|
|---|
| 225 | getid_(qh newfacet_list)));
|
|---|
| 226 | while (True) {
|
|---|
| 227 | wasmerge= False;
|
|---|
| 228 | while (qh_setsize(qh facet_mergeset)) {
|
|---|
| 229 | while ((merge= (mergeT*)qh_setdellast(qh facet_mergeset))) {
|
|---|
| 230 | facet1= merge->facet1;
|
|---|
| 231 | facet2= merge->facet2;
|
|---|
| 232 | mergetype= merge->type;
|
|---|
| 233 | qh_memfree_(merge, (int)sizeof(mergeT), freelistp);
|
|---|
| 234 | if (facet1->visible || facet2->visible) /*deleted facet*/
|
|---|
| 235 | continue;
|
|---|
| 236 | if ((facet1->newfacet && !facet1->tested)
|
|---|
| 237 | || (facet2->newfacet && !facet2->tested)) {
|
|---|
| 238 | if (qh MERGEindependent && mergetype <= MRGanglecoplanar)
|
|---|
| 239 | continue; /* perform independent sets of merges */
|
|---|
| 240 | }
|
|---|
| 241 | qh_merge_nonconvex(facet1, facet2, mergetype);
|
|---|
| 242 | numdegenredun += qh_merge_degenredundant();
|
|---|
| 243 | numnewmerges++;
|
|---|
| 244 | wasmerge= True;
|
|---|
| 245 | if (mergetype == MRGconcave)
|
|---|
| 246 | numconcave++;
|
|---|
| 247 | else /* MRGcoplanar or MRGanglecoplanar */
|
|---|
| 248 | numcoplanar++;
|
|---|
| 249 | } /* while setdellast */
|
|---|
| 250 | if (qh POSTmerging && qh hull_dim <= qh_DIMreduceBuild
|
|---|
| 251 | && numnewmerges > qh_MAXnewmerges) {
|
|---|
| 252 | numnewmerges= 0;
|
|---|
| 253 | qh_reducevertices(); /* otherwise large post merges too slow */
|
|---|
| 254 | }
|
|---|
| 255 | qh_getmergeset(qh newfacet_list); /* facet_mergeset */
|
|---|
| 256 | } /* while mergeset */
|
|---|
| 257 | if (qh VERTEXneighbors) {
|
|---|
| 258 | isreduce= False;
|
|---|
| 259 | if (qh hull_dim >=4 && qh POSTmerging) {
|
|---|
| 260 | FORALLvertices
|
|---|
| 261 | vertex->delridge= True;
|
|---|
| 262 | isreduce= True;
|
|---|
| 263 | }
|
|---|
| 264 | if ((wasmerge || othermerge) && (!qh MERGEexact || qh POSTmerging)
|
|---|
| 265 | && qh hull_dim <= qh_DIMreduceBuild) {
|
|---|
| 266 | othermerge= False;
|
|---|
| 267 | isreduce= True;
|
|---|
| 268 | }
|
|---|
| 269 | if (isreduce) {
|
|---|
| 270 | if (qh_reducevertices()) {
|
|---|
| 271 | qh_getmergeset(qh newfacet_list); /* facet_mergeset */
|
|---|
| 272 | continue;
|
|---|
| 273 | }
|
|---|
| 274 | }
|
|---|
| 275 | }
|
|---|
| 276 | if (vneighbors && qh_test_vneighbors(/* qh newfacet_list */))
|
|---|
| 277 | continue;
|
|---|
| 278 | break;
|
|---|
| 279 | } /* while (True) */
|
|---|
| 280 | if (qh CHECKfrequently && !qh MERGEexact) {
|
|---|
| 281 | qh old_randomdist= qh RANDOMdist;
|
|---|
| 282 | qh RANDOMdist= False;
|
|---|
| 283 | qh_checkconvex(qh newfacet_list, qh_ALGORITHMfault);
|
|---|
| 284 | /* qh_checkconnect(); [this is slow and it changes the facet order] */
|
|---|
| 285 | qh RANDOMdist= qh old_randomdist;
|
|---|
| 286 | }
|
|---|
| 287 | trace1((qh ferr, 1009, "qh_all_merges: merged %d coplanar facets %d concave facets and %d degen or redundant facets.\n",
|
|---|
| 288 | numcoplanar, numconcave, numdegenredun));
|
|---|
| 289 | if (qh IStracing >= 4 && qh num_facets < 50)
|
|---|
| 290 | qh_printlists();
|
|---|
| 291 | } /* all_merges */
|
|---|
| 292 |
|
|---|
| 293 |
|
|---|
| 294 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 295 | >-------------------------------</a><a name="appendmergeset">-</a>
|
|---|
| 296 |
|
|---|
| 297 | qh_appendmergeset( facet, neighbor, mergetype, angle )
|
|---|
| 298 | appends an entry to qh.facet_mergeset or qh.degen_mergeset
|
|---|
| 299 |
|
|---|
| 300 | angle ignored if NULL or !qh.ANGLEmerge
|
|---|
| 301 |
|
|---|
| 302 | returns:
|
|---|
| 303 | merge appended to facet_mergeset or degen_mergeset
|
|---|
| 304 | sets ->degenerate or ->redundant if degen_mergeset
|
|---|
| 305 |
|
|---|
| 306 | see:
|
|---|
| 307 | qh_test_appendmerge()
|
|---|
| 308 |
|
|---|
| 309 | design:
|
|---|
| 310 | allocate merge entry
|
|---|
| 311 | if regular merge
|
|---|
| 312 | append to qh.facet_mergeset
|
|---|
| 313 | else if degenerate merge and qh.facet_mergeset is all degenerate
|
|---|
| 314 | append to qh.degen_mergeset
|
|---|
| 315 | else if degenerate merge
|
|---|
| 316 | prepend to qh.degen_mergeset
|
|---|
| 317 | else if redundant merge
|
|---|
| 318 | append to qh.degen_mergeset
|
|---|
| 319 | */
|
|---|
| 320 | void qh_appendmergeset(facetT *facet, facetT *neighbor, mergeType mergetype, realT *angle) {
|
|---|
| 321 | mergeT *merge, *lastmerge;
|
|---|
| 322 | void **freelistp; /* used !qh_NOmem */
|
|---|
| 323 |
|
|---|
| 324 | if (facet->redundant)
|
|---|
| 325 | return;
|
|---|
| 326 | if (facet->degenerate && mergetype == MRGdegen)
|
|---|
| 327 | return;
|
|---|
| 328 | qh_memalloc_((int)sizeof(mergeT), freelistp, merge, mergeT);
|
|---|
| 329 | merge->facet1= facet;
|
|---|
| 330 | merge->facet2= neighbor;
|
|---|
| 331 | merge->type= mergetype;
|
|---|
| 332 | if (angle && qh ANGLEmerge)
|
|---|
| 333 | merge->angle= *angle;
|
|---|
| 334 | if (mergetype < MRGdegen)
|
|---|
| 335 | qh_setappend(&(qh facet_mergeset), merge);
|
|---|
| 336 | else if (mergetype == MRGdegen) {
|
|---|
| 337 | facet->degenerate= True;
|
|---|
| 338 | if (!(lastmerge= (mergeT*)qh_setlast(qh degen_mergeset))
|
|---|
| 339 | || lastmerge->type == MRGdegen)
|
|---|
| 340 | qh_setappend(&(qh degen_mergeset), merge);
|
|---|
| 341 | else
|
|---|
| 342 | qh_setaddnth(&(qh degen_mergeset), 0, merge);
|
|---|
| 343 | }else if (mergetype == MRGredundant) {
|
|---|
| 344 | facet->redundant= True;
|
|---|
| 345 | qh_setappend(&(qh degen_mergeset), merge);
|
|---|
| 346 | }else /* mergetype == MRGmirror */ {
|
|---|
| 347 | if (facet->redundant || neighbor->redundant) {
|
|---|
| 348 | qh_fprintf(qh ferr, 6092, "qhull error (qh_appendmergeset): facet f%d or f%d is already a mirrored facet\n",
|
|---|
| 349 | facet->id, neighbor->id);
|
|---|
| 350 | qh_errexit2 (qh_ERRqhull, facet, neighbor);
|
|---|
| 351 | }
|
|---|
| 352 | if (!qh_setequal(facet->vertices, neighbor->vertices)) {
|
|---|
| 353 | qh_fprintf(qh ferr, 6093, "qhull error (qh_appendmergeset): mirrored facets f%d and f%d do not have the same vertices\n",
|
|---|
| 354 | facet->id, neighbor->id);
|
|---|
| 355 | qh_errexit2 (qh_ERRqhull, facet, neighbor);
|
|---|
| 356 | }
|
|---|
| 357 | facet->redundant= True;
|
|---|
| 358 | neighbor->redundant= True;
|
|---|
| 359 | qh_setappend(&(qh degen_mergeset), merge);
|
|---|
| 360 | }
|
|---|
| 361 | } /* appendmergeset */
|
|---|
| 362 |
|
|---|
| 363 |
|
|---|
| 364 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 365 | >-------------------------------</a><a name="basevertices">-</a>
|
|---|
| 366 |
|
|---|
| 367 | qh_basevertices( samecycle )
|
|---|
| 368 | return temporary set of base vertices for samecycle
|
|---|
| 369 | samecycle is first facet in the cycle
|
|---|
| 370 | assumes apex is SETfirst_( samecycle->vertices )
|
|---|
| 371 |
|
|---|
| 372 | returns:
|
|---|
| 373 | vertices(settemp)
|
|---|
| 374 | all ->seen are cleared
|
|---|
| 375 |
|
|---|
| 376 | notes:
|
|---|
| 377 | uses qh_vertex_visit;
|
|---|
| 378 |
|
|---|
| 379 | design:
|
|---|
| 380 | for each facet in samecycle
|
|---|
| 381 | for each unseen vertex in facet->vertices
|
|---|
| 382 | append to result
|
|---|
| 383 | */
|
|---|
| 384 | setT *qh_basevertices(facetT *samecycle) {
|
|---|
| 385 | facetT *same;
|
|---|
| 386 | vertexT *apex, *vertex, **vertexp;
|
|---|
| 387 | setT *vertices= qh_settemp(qh TEMPsize);
|
|---|
| 388 |
|
|---|
| 389 | apex= SETfirstt_(samecycle->vertices, vertexT);
|
|---|
| 390 | apex->visitid= ++qh vertex_visit;
|
|---|
| 391 | FORALLsame_cycle_(samecycle) {
|
|---|
| 392 | if (same->mergeridge)
|
|---|
| 393 | continue;
|
|---|
| 394 | FOREACHvertex_(same->vertices) {
|
|---|
| 395 | if (vertex->visitid != qh vertex_visit) {
|
|---|
| 396 | qh_setappend(&vertices, vertex);
|
|---|
| 397 | vertex->visitid= qh vertex_visit;
|
|---|
| 398 | vertex->seen= False;
|
|---|
| 399 | }
|
|---|
| 400 | }
|
|---|
| 401 | }
|
|---|
| 402 | trace4((qh ferr, 4019, "qh_basevertices: found %d vertices\n",
|
|---|
| 403 | qh_setsize(vertices)));
|
|---|
| 404 | return vertices;
|
|---|
| 405 | } /* basevertices */
|
|---|
| 406 |
|
|---|
| 407 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 408 | >-------------------------------</a><a name="checkconnect">-</a>
|
|---|
| 409 |
|
|---|
| 410 | qh_checkconnect()
|
|---|
| 411 | check that new facets are connected
|
|---|
| 412 | new facets are on qh.newfacet_list
|
|---|
| 413 |
|
|---|
| 414 | notes:
|
|---|
| 415 | this is slow and it changes the order of the facets
|
|---|
| 416 | uses qh.visit_id
|
|---|
| 417 |
|
|---|
| 418 | design:
|
|---|
| 419 | move first new facet to end of qh.facet_list
|
|---|
| 420 | for all newly appended facets
|
|---|
| 421 | append unvisited neighbors to end of qh.facet_list
|
|---|
| 422 | for all new facets
|
|---|
| 423 | report error if unvisited
|
|---|
| 424 | */
|
|---|
| 425 | void qh_checkconnect(void /* qh newfacet_list */) {
|
|---|
| 426 | facetT *facet, *newfacet, *errfacet= NULL, *neighbor, **neighborp;
|
|---|
| 427 |
|
|---|
| 428 | facet= qh newfacet_list;
|
|---|
| 429 | qh_removefacet(facet);
|
|---|
| 430 | qh_appendfacet(facet);
|
|---|
| 431 | facet->visitid= ++qh visit_id;
|
|---|
| 432 | FORALLfacet_(facet) {
|
|---|
| 433 | FOREACHneighbor_(facet) {
|
|---|
| 434 | if (neighbor->visitid != qh visit_id) {
|
|---|
| 435 | qh_removefacet(neighbor);
|
|---|
| 436 | qh_appendfacet(neighbor);
|
|---|
| 437 | neighbor->visitid= qh visit_id;
|
|---|
| 438 | }
|
|---|
| 439 | }
|
|---|
| 440 | }
|
|---|
| 441 | FORALLnew_facets {
|
|---|
| 442 | if (newfacet->visitid == qh visit_id)
|
|---|
| 443 | break;
|
|---|
| 444 | qh_fprintf(qh ferr, 6094, "qhull error: f%d is not attached to the new facets\n",
|
|---|
| 445 | newfacet->id);
|
|---|
| 446 | errfacet= newfacet;
|
|---|
| 447 | }
|
|---|
| 448 | if (errfacet)
|
|---|
| 449 | qh_errexit(qh_ERRqhull, errfacet, NULL);
|
|---|
| 450 | } /* checkconnect */
|
|---|
| 451 |
|
|---|
| 452 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 453 | >-------------------------------</a><a name="checkzero">-</a>
|
|---|
| 454 |
|
|---|
| 455 | qh_checkzero( testall )
|
|---|
| 456 | check that facets are clearly convex for qh.DISTround with qh.MERGEexact
|
|---|
| 457 |
|
|---|
| 458 | if testall,
|
|---|
| 459 | test all facets for qh.MERGEexact post-merging
|
|---|
| 460 | else
|
|---|
| 461 | test qh.newfacet_list
|
|---|
| 462 |
|
|---|
| 463 | if qh.MERGEexact,
|
|---|
| 464 | allows coplanar ridges
|
|---|
| 465 | skips convexity test while qh.ZEROall_ok
|
|---|
| 466 |
|
|---|
| 467 | returns:
|
|---|
| 468 | True if all facets !flipped, !dupridge, normal
|
|---|
| 469 | if all horizon facets are simplicial
|
|---|
| 470 | if all vertices are clearly below neighbor
|
|---|
| 471 | if all opposite vertices of horizon are below
|
|---|
| 472 | clears qh.ZEROall_ok if any problems or coplanar facets
|
|---|
| 473 |
|
|---|
| 474 | notes:
|
|---|
| 475 | uses qh.vertex_visit
|
|---|
| 476 | horizon facets may define multiple new facets
|
|---|
| 477 |
|
|---|
| 478 | design:
|
|---|
| 479 | for all facets in qh.newfacet_list or qh.facet_list
|
|---|
| 480 | check for flagged faults (flipped, etc.)
|
|---|
| 481 | for all facets in qh.newfacet_list or qh.facet_list
|
|---|
| 482 | for each neighbor of facet
|
|---|
| 483 | skip horizon facets for qh.newfacet_list
|
|---|
| 484 | test the opposite vertex
|
|---|
| 485 | if qh.newfacet_list
|
|---|
| 486 | test the other vertices in the facet's horizon facet
|
|---|
| 487 | */
|
|---|
| 488 | boolT qh_checkzero(boolT testall) {
|
|---|
| 489 | facetT *facet, *neighbor, **neighborp;
|
|---|
| 490 | facetT *horizon, *facetlist;
|
|---|
| 491 | int neighbor_i;
|
|---|
| 492 | vertexT *vertex, **vertexp;
|
|---|
| 493 | realT dist;
|
|---|
| 494 |
|
|---|
| 495 | if (testall)
|
|---|
| 496 | facetlist= qh facet_list;
|
|---|
| 497 | else {
|
|---|
| 498 | facetlist= qh newfacet_list;
|
|---|
| 499 | FORALLfacet_(facetlist) {
|
|---|
| 500 | horizon= SETfirstt_(facet->neighbors, facetT);
|
|---|
| 501 | if (!horizon->simplicial)
|
|---|
| 502 | goto LABELproblem;
|
|---|
| 503 | if (facet->flipped || facet->dupridge || !facet->normal)
|
|---|
| 504 | goto LABELproblem;
|
|---|
| 505 | }
|
|---|
| 506 | if (qh MERGEexact && qh ZEROall_ok) {
|
|---|
| 507 | trace2((qh ferr, 2011, "qh_checkzero: skip convexity check until first pre-merge\n"));
|
|---|
| 508 | return True;
|
|---|
| 509 | }
|
|---|
| 510 | }
|
|---|
| 511 | FORALLfacet_(facetlist) {
|
|---|
| 512 | qh vertex_visit++;
|
|---|
| 513 | neighbor_i= 0;
|
|---|
| 514 | horizon= NULL;
|
|---|
| 515 | FOREACHneighbor_(facet) {
|
|---|
| 516 | if (!neighbor_i && !testall) {
|
|---|
| 517 | horizon= neighbor;
|
|---|
| 518 | neighbor_i++;
|
|---|
| 519 | continue; /* horizon facet tested in qh_findhorizon */
|
|---|
| 520 | }
|
|---|
| 521 | vertex= SETelemt_(facet->vertices, neighbor_i++, vertexT);
|
|---|
| 522 | vertex->visitid= qh vertex_visit;
|
|---|
| 523 | zzinc_(Zdistzero);
|
|---|
| 524 | qh_distplane(vertex->point, neighbor, &dist);
|
|---|
| 525 | if (dist >= -qh DISTround) {
|
|---|
| 526 | qh ZEROall_ok= False;
|
|---|
| 527 | if (!qh MERGEexact || testall || dist > qh DISTround)
|
|---|
| 528 | goto LABELnonconvex;
|
|---|
| 529 | }
|
|---|
| 530 | }
|
|---|
| 531 | if (!testall) {
|
|---|
| 532 | FOREACHvertex_(horizon->vertices) {
|
|---|
| 533 | if (vertex->visitid != qh vertex_visit) {
|
|---|
| 534 | zzinc_(Zdistzero);
|
|---|
| 535 | qh_distplane(vertex->point, facet, &dist);
|
|---|
| 536 | if (dist >= -qh DISTround) {
|
|---|
| 537 | qh ZEROall_ok= False;
|
|---|
| 538 | if (!qh MERGEexact || dist > qh DISTround)
|
|---|
| 539 | goto LABELnonconvex;
|
|---|
| 540 | }
|
|---|
| 541 | break;
|
|---|
| 542 | }
|
|---|
| 543 | }
|
|---|
| 544 | }
|
|---|
| 545 | }
|
|---|
| 546 | trace2((qh ferr, 2012, "qh_checkzero: testall %d, facets are %s\n", testall,
|
|---|
| 547 | (qh MERGEexact && !testall) ?
|
|---|
| 548 | "not concave, flipped, or duplicate ridged" : "clearly convex"));
|
|---|
| 549 | return True;
|
|---|
| 550 |
|
|---|
| 551 | LABELproblem:
|
|---|
| 552 | qh ZEROall_ok= False;
|
|---|
| 553 | trace2((qh ferr, 2013, "qh_checkzero: facet f%d needs pre-merging\n",
|
|---|
| 554 | facet->id));
|
|---|
| 555 | return False;
|
|---|
| 556 |
|
|---|
| 557 | LABELnonconvex:
|
|---|
| 558 | trace2((qh ferr, 2014, "qh_checkzero: facet f%d and f%d are not clearly convex. v%d dist %.2g\n",
|
|---|
| 559 | facet->id, neighbor->id, vertex->id, dist));
|
|---|
| 560 | return False;
|
|---|
| 561 | } /* checkzero */
|
|---|
| 562 |
|
|---|
| 563 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 564 | >-------------------------------</a><a name="compareangle">-</a>
|
|---|
| 565 |
|
|---|
| 566 | qh_compareangle( angle1, angle2 )
|
|---|
| 567 | used by qsort() to order merges by angle
|
|---|
| 568 | */
|
|---|
| 569 | int qh_compareangle(const void *p1, const void *p2) {
|
|---|
| 570 | const mergeT *a= *((mergeT *const*)p1), *b= *((mergeT *const*)p2);
|
|---|
| 571 |
|
|---|
| 572 | return((a->angle > b->angle) ? 1 : -1);
|
|---|
| 573 | } /* compareangle */
|
|---|
| 574 |
|
|---|
| 575 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 576 | >-------------------------------</a><a name="comparemerge">-</a>
|
|---|
| 577 |
|
|---|
| 578 | qh_comparemerge( merge1, merge2 )
|
|---|
| 579 | used by qsort() to order merges
|
|---|
| 580 | */
|
|---|
| 581 | int qh_comparemerge(const void *p1, const void *p2) {
|
|---|
| 582 | const mergeT *a= *((mergeT *const*)p1), *b= *((mergeT *const*)p2);
|
|---|
| 583 |
|
|---|
| 584 | return(a->type - b->type);
|
|---|
| 585 | } /* comparemerge */
|
|---|
| 586 |
|
|---|
| 587 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 588 | >-------------------------------</a><a name="comparevisit">-</a>
|
|---|
| 589 |
|
|---|
| 590 | qh_comparevisit( vertex1, vertex2 )
|
|---|
| 591 | used by qsort() to order vertices by their visitid
|
|---|
| 592 | */
|
|---|
| 593 | int qh_comparevisit(const void *p1, const void *p2) {
|
|---|
| 594 | const vertexT *a= *((vertexT *const*)p1), *b= *((vertexT *const*)p2);
|
|---|
| 595 |
|
|---|
| 596 | return(a->visitid - b->visitid);
|
|---|
| 597 | } /* comparevisit */
|
|---|
| 598 |
|
|---|
| 599 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 600 | >-------------------------------</a><a name="copynonconvex">-</a>
|
|---|
| 601 |
|
|---|
| 602 | qh_copynonconvex( atridge )
|
|---|
| 603 | set non-convex flag on other ridges (if any) between same neighbors
|
|---|
| 604 |
|
|---|
| 605 | notes:
|
|---|
| 606 | may be faster if use smaller ridge set
|
|---|
| 607 |
|
|---|
| 608 | design:
|
|---|
| 609 | for each ridge of atridge's top facet
|
|---|
| 610 | if ridge shares the same neighbor
|
|---|
| 611 | set nonconvex flag
|
|---|
| 612 | */
|
|---|
| 613 | void qh_copynonconvex(ridgeT *atridge) {
|
|---|
| 614 | facetT *facet, *otherfacet;
|
|---|
| 615 | ridgeT *ridge, **ridgep;
|
|---|
| 616 |
|
|---|
| 617 | facet= atridge->top;
|
|---|
| 618 | otherfacet= atridge->bottom;
|
|---|
| 619 | FOREACHridge_(facet->ridges) {
|
|---|
| 620 | if (otherfacet == otherfacet_(ridge, facet) && ridge != atridge) {
|
|---|
| 621 | ridge->nonconvex= True;
|
|---|
| 622 | trace4((qh ferr, 4020, "qh_copynonconvex: moved nonconvex flag from r%d to r%d\n",
|
|---|
| 623 | atridge->id, ridge->id));
|
|---|
| 624 | break;
|
|---|
| 625 | }
|
|---|
| 626 | }
|
|---|
| 627 | } /* copynonconvex */
|
|---|
| 628 |
|
|---|
| 629 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 630 | >-------------------------------</a><a name="degen_redundant_facet">-</a>
|
|---|
| 631 |
|
|---|
| 632 | qh_degen_redundant_facet( facet )
|
|---|
| 633 | check facet for degen. or redundancy
|
|---|
| 634 |
|
|---|
| 635 | notes:
|
|---|
| 636 | bumps vertex_visit
|
|---|
| 637 | called if a facet was redundant but no longer is (qh_merge_degenredundant)
|
|---|
| 638 | qh_appendmergeset() only appends first reference to facet (i.e., redundant)
|
|---|
| 639 |
|
|---|
| 640 | see:
|
|---|
| 641 | qh_degen_redundant_neighbors()
|
|---|
| 642 |
|
|---|
| 643 | design:
|
|---|
| 644 | test for redundant neighbor
|
|---|
| 645 | test for degenerate facet
|
|---|
| 646 | */
|
|---|
| 647 | void qh_degen_redundant_facet(facetT *facet) {
|
|---|
| 648 | vertexT *vertex, **vertexp;
|
|---|
| 649 | facetT *neighbor, **neighborp;
|
|---|
| 650 |
|
|---|
| 651 | trace4((qh ferr, 4021, "qh_degen_redundant_facet: test facet f%d for degen/redundant\n",
|
|---|
| 652 | facet->id));
|
|---|
| 653 | FOREACHneighbor_(facet) {
|
|---|
| 654 | qh vertex_visit++;
|
|---|
| 655 | FOREACHvertex_(neighbor->vertices)
|
|---|
| 656 | vertex->visitid= qh vertex_visit;
|
|---|
| 657 | FOREACHvertex_(facet->vertices) {
|
|---|
| 658 | if (vertex->visitid != qh vertex_visit)
|
|---|
| 659 | break;
|
|---|
| 660 | }
|
|---|
| 661 | if (!vertex) {
|
|---|
| 662 | qh_appendmergeset(facet, neighbor, MRGredundant, NULL);
|
|---|
| 663 | trace2((qh ferr, 2015, "qh_degen_redundant_facet: f%d is contained in f%d. merge\n", facet->id, neighbor->id));
|
|---|
| 664 | return;
|
|---|
| 665 | }
|
|---|
| 666 | }
|
|---|
| 667 | if (qh_setsize(facet->neighbors) < qh hull_dim) {
|
|---|
| 668 | qh_appendmergeset(facet, facet, MRGdegen, NULL);
|
|---|
| 669 | trace2((qh ferr, 2016, "qh_degen_redundant_neighbors: f%d is degenerate.\n", facet->id));
|
|---|
| 670 | }
|
|---|
| 671 | } /* degen_redundant_facet */
|
|---|
| 672 |
|
|---|
| 673 |
|
|---|
| 674 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 675 | >-------------------------------</a><a name="degen_redundant_neighbors">-</a>
|
|---|
| 676 |
|
|---|
| 677 | qh_degen_redundant_neighbors( facet, delfacet, )
|
|---|
| 678 | append degenerate and redundant neighbors to facet_mergeset
|
|---|
| 679 | if delfacet,
|
|---|
| 680 | only checks neighbors of both delfacet and facet
|
|---|
| 681 | also checks current facet for degeneracy
|
|---|
| 682 |
|
|---|
| 683 | notes:
|
|---|
| 684 | bumps vertex_visit
|
|---|
| 685 | called for each qh_mergefacet() and qh_mergecycle()
|
|---|
| 686 | merge and statistics occur in merge_nonconvex
|
|---|
| 687 | qh_appendmergeset() only appends first reference to facet (i.e., redundant)
|
|---|
| 688 | it appends redundant facets after degenerate ones
|
|---|
| 689 |
|
|---|
| 690 | a degenerate facet has fewer than hull_dim neighbors
|
|---|
| 691 | a redundant facet's vertices is a subset of its neighbor's vertices
|
|---|
| 692 | tests for redundant merges first (appendmergeset is nop for others)
|
|---|
| 693 | in a merge, only needs to test neighbors of merged facet
|
|---|
| 694 |
|
|---|
| 695 | see:
|
|---|
| 696 | qh_merge_degenredundant() and qh_degen_redundant_facet()
|
|---|
| 697 |
|
|---|
| 698 | design:
|
|---|
| 699 | test for degenerate facet
|
|---|
| 700 | test for redundant neighbor
|
|---|
| 701 | test for degenerate neighbor
|
|---|
| 702 | */
|
|---|
| 703 | void qh_degen_redundant_neighbors(facetT *facet, facetT *delfacet) {
|
|---|
| 704 | vertexT *vertex, **vertexp;
|
|---|
| 705 | facetT *neighbor, **neighborp;
|
|---|
| 706 | int size;
|
|---|
| 707 |
|
|---|
| 708 | trace4((qh ferr, 4022, "qh_degen_redundant_neighbors: test neighbors of f%d with delfacet f%d\n",
|
|---|
| 709 | facet->id, getid_(delfacet)));
|
|---|
| 710 | if ((size= qh_setsize(facet->neighbors)) < qh hull_dim) {
|
|---|
| 711 | qh_appendmergeset(facet, facet, MRGdegen, NULL);
|
|---|
| 712 | trace2((qh ferr, 2017, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors.\n", facet->id, size));
|
|---|
| 713 | }
|
|---|
| 714 | if (!delfacet)
|
|---|
| 715 | delfacet= facet;
|
|---|
| 716 | qh vertex_visit++;
|
|---|
| 717 | FOREACHvertex_(facet->vertices)
|
|---|
| 718 | vertex->visitid= qh vertex_visit;
|
|---|
| 719 | FOREACHneighbor_(delfacet) {
|
|---|
| 720 | /* uses early out instead of checking vertex count */
|
|---|
| 721 | if (neighbor == facet)
|
|---|
| 722 | continue;
|
|---|
| 723 | FOREACHvertex_(neighbor->vertices) {
|
|---|
| 724 | if (vertex->visitid != qh vertex_visit)
|
|---|
| 725 | break;
|
|---|
| 726 | }
|
|---|
| 727 | if (!vertex) {
|
|---|
| 728 | qh_appendmergeset(neighbor, facet, MRGredundant, NULL);
|
|---|
| 729 | trace2((qh ferr, 2018, "qh_degen_redundant_neighbors: f%d is contained in f%d. merge\n", neighbor->id, facet->id));
|
|---|
| 730 | }
|
|---|
| 731 | }
|
|---|
| 732 | FOREACHneighbor_(delfacet) { /* redundant merges occur first */
|
|---|
| 733 | if (neighbor == facet)
|
|---|
| 734 | continue;
|
|---|
| 735 | if ((size= qh_setsize(neighbor->neighbors)) < qh hull_dim) {
|
|---|
| 736 | qh_appendmergeset(neighbor, neighbor, MRGdegen, NULL);
|
|---|
| 737 | trace2((qh ferr, 2019, "qh_degen_redundant_neighbors: f%d is degenerate with %d neighbors. Neighbor of f%d.\n", neighbor->id, size, facet->id));
|
|---|
| 738 | }
|
|---|
| 739 | }
|
|---|
| 740 | } /* degen_redundant_neighbors */
|
|---|
| 741 |
|
|---|
| 742 |
|
|---|
| 743 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 744 | >-------------------------------</a><a name="find_newvertex">-</a>
|
|---|
| 745 |
|
|---|
| 746 | qh_find_newvertex( oldvertex, vertices, ridges )
|
|---|
| 747 | locate new vertex for renaming old vertex
|
|---|
| 748 | vertices is a set of possible new vertices
|
|---|
| 749 | vertices sorted by number of deleted ridges
|
|---|
| 750 |
|
|---|
| 751 | returns:
|
|---|
| 752 | newvertex or NULL
|
|---|
| 753 | each ridge includes both vertex and oldvertex
|
|---|
| 754 | vertices sorted by number of deleted ridges
|
|---|
| 755 |
|
|---|
| 756 | notes:
|
|---|
| 757 | modifies vertex->visitid
|
|---|
| 758 | new vertex is in one of the ridges
|
|---|
| 759 | renaming will not cause a duplicate ridge
|
|---|
| 760 | renaming will minimize the number of deleted ridges
|
|---|
| 761 | newvertex may not be adjacent in the dual (though unlikely)
|
|---|
| 762 |
|
|---|
| 763 | design:
|
|---|
| 764 | for each vertex in vertices
|
|---|
| 765 | set vertex->visitid to number of references in ridges
|
|---|
| 766 | remove unvisited vertices
|
|---|
| 767 | set qh.vertex_visit above all possible values
|
|---|
| 768 | sort vertices by number of references in ridges
|
|---|
| 769 | add each ridge to qh.hash_table
|
|---|
| 770 | for each vertex in vertices
|
|---|
| 771 | look for a vertex that would not cause a duplicate ridge after a rename
|
|---|
| 772 | */
|
|---|
| 773 | vertexT *qh_find_newvertex(vertexT *oldvertex, setT *vertices, setT *ridges) {
|
|---|
| 774 | vertexT *vertex, **vertexp;
|
|---|
| 775 | setT *newridges;
|
|---|
| 776 | ridgeT *ridge, **ridgep;
|
|---|
| 777 | int size, hashsize;
|
|---|
| 778 | int hash;
|
|---|
| 779 |
|
|---|
| 780 | #ifndef qh_NOtrace
|
|---|
| 781 | if (qh IStracing >= 4) {
|
|---|
| 782 | qh_fprintf(qh ferr, 8063, "qh_find_newvertex: find new vertex for v%d from ",
|
|---|
| 783 | oldvertex->id);
|
|---|
| 784 | FOREACHvertex_(vertices)
|
|---|
| 785 | qh_fprintf(qh ferr, 8064, "v%d ", vertex->id);
|
|---|
| 786 | FOREACHridge_(ridges)
|
|---|
| 787 | qh_fprintf(qh ferr, 8065, "r%d ", ridge->id);
|
|---|
| 788 | qh_fprintf(qh ferr, 8066, "\n");
|
|---|
| 789 | }
|
|---|
| 790 | #endif
|
|---|
| 791 | FOREACHvertex_(vertices)
|
|---|
| 792 | vertex->visitid= 0;
|
|---|
| 793 | FOREACHridge_(ridges) {
|
|---|
| 794 | FOREACHvertex_(ridge->vertices)
|
|---|
| 795 | vertex->visitid++;
|
|---|
| 796 | }
|
|---|
| 797 | FOREACHvertex_(vertices) {
|
|---|
| 798 | if (!vertex->visitid) {
|
|---|
| 799 | qh_setdelnth(vertices, SETindex_(vertices,vertex));
|
|---|
| 800 | vertexp--; /* repeat since deleted this vertex */
|
|---|
| 801 | }
|
|---|
| 802 | }
|
|---|
| 803 | qh vertex_visit += (unsigned int)qh_setsize(ridges);
|
|---|
| 804 | if (!qh_setsize(vertices)) {
|
|---|
| 805 | trace4((qh ferr, 4023, "qh_find_newvertex: vertices not in ridges for v%d\n",
|
|---|
| 806 | oldvertex->id));
|
|---|
| 807 | return NULL;
|
|---|
| 808 | }
|
|---|
| 809 | qsort(SETaddr_(vertices, vertexT), (size_t)qh_setsize(vertices),
|
|---|
| 810 | sizeof(vertexT *), qh_comparevisit);
|
|---|
| 811 | /* can now use qh vertex_visit */
|
|---|
| 812 | if (qh PRINTstatistics) {
|
|---|
| 813 | size= qh_setsize(vertices);
|
|---|
| 814 | zinc_(Zintersect);
|
|---|
| 815 | zadd_(Zintersecttot, size);
|
|---|
| 816 | zmax_(Zintersectmax, size);
|
|---|
| 817 | }
|
|---|
| 818 | hashsize= qh_newhashtable(qh_setsize(ridges));
|
|---|
| 819 | FOREACHridge_(ridges)
|
|---|
| 820 | qh_hashridge(qh hash_table, hashsize, ridge, oldvertex);
|
|---|
| 821 | FOREACHvertex_(vertices) {
|
|---|
| 822 | newridges= qh_vertexridges(vertex);
|
|---|
| 823 | FOREACHridge_(newridges) {
|
|---|
| 824 | if (qh_hashridge_find(qh hash_table, hashsize, ridge, vertex, oldvertex, &hash)) {
|
|---|
| 825 | zinc_(Zdupridge);
|
|---|
| 826 | break;
|
|---|
| 827 | }
|
|---|
| 828 | }
|
|---|
| 829 | qh_settempfree(&newridges);
|
|---|
| 830 | if (!ridge)
|
|---|
| 831 | break; /* found a rename */
|
|---|
| 832 | }
|
|---|
| 833 | if (vertex) {
|
|---|
| 834 | /* counted in qh_renamevertex */
|
|---|
| 835 | trace2((qh ferr, 2020, "qh_find_newvertex: found v%d for old v%d from %d vertices and %d ridges.\n",
|
|---|
| 836 | vertex->id, oldvertex->id, qh_setsize(vertices), qh_setsize(ridges)));
|
|---|
| 837 | }else {
|
|---|
| 838 | zinc_(Zfindfail);
|
|---|
| 839 | trace0((qh ferr, 14, "qh_find_newvertex: no vertex for renaming v%d(all duplicated ridges) during p%d\n",
|
|---|
| 840 | oldvertex->id, qh furthest_id));
|
|---|
| 841 | }
|
|---|
| 842 | qh_setfree(&qh hash_table);
|
|---|
| 843 | return vertex;
|
|---|
| 844 | } /* find_newvertex */
|
|---|
| 845 |
|
|---|
| 846 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 847 | >-------------------------------</a><a name="findbest_test">-</a>
|
|---|
| 848 |
|
|---|
| 849 | qh_findbest_test( testcentrum, facet, neighbor, bestfacet, dist, mindist, maxdist )
|
|---|
| 850 | test neighbor of facet for qh_findbestneighbor()
|
|---|
| 851 | if testcentrum,
|
|---|
| 852 | tests centrum (assumes it is defined)
|
|---|
| 853 | else
|
|---|
| 854 | tests vertices
|
|---|
| 855 |
|
|---|
| 856 | returns:
|
|---|
| 857 | if a better facet (i.e., vertices/centrum of facet closer to neighbor)
|
|---|
| 858 | updates bestfacet, dist, mindist, and maxdist
|
|---|
| 859 | */
|
|---|
| 860 | void qh_findbest_test(boolT testcentrum, facetT *facet, facetT *neighbor,
|
|---|
| 861 | facetT **bestfacet, realT *distp, realT *mindistp, realT *maxdistp) {
|
|---|
| 862 | realT dist, mindist, maxdist;
|
|---|
| 863 |
|
|---|
| 864 | if (testcentrum) {
|
|---|
| 865 | zzinc_(Zbestdist);
|
|---|
| 866 | qh_distplane(facet->center, neighbor, &dist);
|
|---|
| 867 | dist *= qh hull_dim; /* estimate furthest vertex */
|
|---|
| 868 | if (dist < 0) {
|
|---|
| 869 | maxdist= 0;
|
|---|
| 870 | mindist= dist;
|
|---|
| 871 | dist= -dist;
|
|---|
| 872 | }else {
|
|---|
| 873 | mindist= 0;
|
|---|
| 874 | maxdist= dist;
|
|---|
| 875 | }
|
|---|
| 876 | }else
|
|---|
| 877 | dist= qh_getdistance(facet, neighbor, &mindist, &maxdist);
|
|---|
| 878 | if (dist < *distp) {
|
|---|
| 879 | *bestfacet= neighbor;
|
|---|
| 880 | *mindistp= mindist;
|
|---|
| 881 | *maxdistp= maxdist;
|
|---|
| 882 | *distp= dist;
|
|---|
| 883 | }
|
|---|
| 884 | } /* findbest_test */
|
|---|
| 885 |
|
|---|
| 886 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 887 | >-------------------------------</a><a name="findbestneighbor">-</a>
|
|---|
| 888 |
|
|---|
| 889 | qh_findbestneighbor( facet, dist, mindist, maxdist )
|
|---|
| 890 | finds best neighbor (least dist) of a facet for merging
|
|---|
| 891 |
|
|---|
| 892 | returns:
|
|---|
| 893 | returns min and max distances and their max absolute value
|
|---|
| 894 |
|
|---|
| 895 | notes:
|
|---|
| 896 | avoids merging old into new
|
|---|
| 897 | assumes ridge->nonconvex only set on one ridge between a pair of facets
|
|---|
| 898 | could use an early out predicate but not worth it
|
|---|
| 899 |
|
|---|
| 900 | design:
|
|---|
| 901 | if a large facet
|
|---|
| 902 | will test centrum
|
|---|
| 903 | else
|
|---|
| 904 | will test vertices
|
|---|
| 905 | if a large facet
|
|---|
| 906 | test nonconvex neighbors for best merge
|
|---|
| 907 | else
|
|---|
| 908 | test all neighbors for the best merge
|
|---|
| 909 | if testing centrum
|
|---|
| 910 | get distance information
|
|---|
| 911 | */
|
|---|
| 912 | facetT *qh_findbestneighbor(facetT *facet, realT *distp, realT *mindistp, realT *maxdistp) {
|
|---|
| 913 | facetT *neighbor, **neighborp, *bestfacet= NULL;
|
|---|
| 914 | ridgeT *ridge, **ridgep;
|
|---|
| 915 | boolT nonconvex= True, testcentrum= False;
|
|---|
| 916 | int size= qh_setsize(facet->vertices);
|
|---|
| 917 |
|
|---|
| 918 | *distp= REALmax;
|
|---|
| 919 | if (size > qh_BESTcentrum2 * qh hull_dim + qh_BESTcentrum) {
|
|---|
| 920 | testcentrum= True;
|
|---|
| 921 | zinc_(Zbestcentrum);
|
|---|
| 922 | if (!facet->center)
|
|---|
| 923 | facet->center= qh_getcentrum(facet);
|
|---|
| 924 | }
|
|---|
| 925 | if (size > qh hull_dim + qh_BESTnonconvex) {
|
|---|
| 926 | FOREACHridge_(facet->ridges) {
|
|---|
| 927 | if (ridge->nonconvex) {
|
|---|
| 928 | neighbor= otherfacet_(ridge, facet);
|
|---|
| 929 | qh_findbest_test(testcentrum, facet, neighbor,
|
|---|
| 930 | &bestfacet, distp, mindistp, maxdistp);
|
|---|
| 931 | }
|
|---|
| 932 | }
|
|---|
| 933 | }
|
|---|
| 934 | if (!bestfacet) {
|
|---|
| 935 | nonconvex= False;
|
|---|
| 936 | FOREACHneighbor_(facet)
|
|---|
| 937 | qh_findbest_test(testcentrum, facet, neighbor,
|
|---|
| 938 | &bestfacet, distp, mindistp, maxdistp);
|
|---|
| 939 | }
|
|---|
| 940 | if (!bestfacet) {
|
|---|
| 941 | qh_fprintf(qh ferr, 6095, "qhull internal error (qh_findbestneighbor): no neighbors for f%d\n", facet->id);
|
|---|
| 942 |
|
|---|
| 943 | qh_errexit(qh_ERRqhull, facet, NULL);
|
|---|
| 944 | }
|
|---|
| 945 | if (testcentrum)
|
|---|
| 946 | qh_getdistance(facet, bestfacet, mindistp, maxdistp);
|
|---|
| 947 | trace3((qh ferr, 3002, "qh_findbestneighbor: f%d is best neighbor for f%d testcentrum? %d nonconvex? %d dist %2.2g min %2.2g max %2.2g\n",
|
|---|
| 948 | bestfacet->id, facet->id, testcentrum, nonconvex, *distp, *mindistp, *maxdistp));
|
|---|
| 949 | return(bestfacet);
|
|---|
| 950 | } /* findbestneighbor */
|
|---|
| 951 |
|
|---|
| 952 |
|
|---|
| 953 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 954 | >-------------------------------</a><a name="flippedmerges">-</a>
|
|---|
| 955 |
|
|---|
| 956 | qh_flippedmerges( facetlist, wasmerge )
|
|---|
| 957 | merge flipped facets into best neighbor
|
|---|
| 958 | assumes qh.facet_mergeset at top of temporary stack
|
|---|
| 959 |
|
|---|
| 960 | returns:
|
|---|
| 961 | no flipped facets on facetlist
|
|---|
| 962 | sets wasmerge if merge occurred
|
|---|
| 963 | degen/redundant merges passed through
|
|---|
| 964 |
|
|---|
| 965 | notes:
|
|---|
| 966 | othermerges not needed since qh.facet_mergeset is empty before & after
|
|---|
| 967 | keep it in case of change
|
|---|
| 968 |
|
|---|
| 969 | design:
|
|---|
| 970 | append flipped facets to qh.facetmergeset
|
|---|
| 971 | for each flipped merge
|
|---|
| 972 | find best neighbor
|
|---|
| 973 | merge facet into neighbor
|
|---|
| 974 | merge degenerate and redundant facets
|
|---|
| 975 | remove flipped merges from qh.facet_mergeset
|
|---|
| 976 | */
|
|---|
| 977 | void qh_flippedmerges(facetT *facetlist, boolT *wasmerge) {
|
|---|
| 978 | facetT *facet, *neighbor, *facet1;
|
|---|
| 979 | realT dist, mindist, maxdist;
|
|---|
| 980 | mergeT *merge, **mergep;
|
|---|
| 981 | setT *othermerges;
|
|---|
| 982 | int nummerge=0;
|
|---|
| 983 |
|
|---|
| 984 | trace4((qh ferr, 4024, "qh_flippedmerges: begin\n"));
|
|---|
| 985 | FORALLfacet_(facetlist) {
|
|---|
| 986 | if (facet->flipped && !facet->visible)
|
|---|
| 987 | qh_appendmergeset(facet, facet, MRGflip, NULL);
|
|---|
| 988 | }
|
|---|
| 989 | othermerges= qh_settemppop(); /* was facet_mergeset */
|
|---|
| 990 | qh facet_mergeset= qh_settemp(qh TEMPsize);
|
|---|
| 991 | qh_settemppush(othermerges);
|
|---|
| 992 | FOREACHmerge_(othermerges) {
|
|---|
| 993 | facet1= merge->facet1;
|
|---|
| 994 | if (merge->type != MRGflip || facet1->visible)
|
|---|
| 995 | continue;
|
|---|
| 996 | if (qh TRACEmerge-1 == zzval_(Ztotmerge))
|
|---|
| 997 | qhmem.IStracing= qh IStracing= qh TRACElevel;
|
|---|
| 998 | neighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
|
|---|
| 999 | trace0((qh ferr, 15, "qh_flippedmerges: merge flipped f%d into f%d dist %2.2g during p%d\n",
|
|---|
| 1000 | facet1->id, neighbor->id, dist, qh furthest_id));
|
|---|
| 1001 | qh_mergefacet(facet1, neighbor, &mindist, &maxdist, !qh_MERGEapex);
|
|---|
| 1002 | nummerge++;
|
|---|
| 1003 | if (qh PRINTstatistics) {
|
|---|
| 1004 | zinc_(Zflipped);
|
|---|
| 1005 | wadd_(Wflippedtot, dist);
|
|---|
| 1006 | wmax_(Wflippedmax, dist);
|
|---|
| 1007 | }
|
|---|
| 1008 | qh_merge_degenredundant();
|
|---|
| 1009 | }
|
|---|
| 1010 | FOREACHmerge_(othermerges) {
|
|---|
| 1011 | if (merge->facet1->visible || merge->facet2->visible)
|
|---|
| 1012 | qh_memfree(merge, (int)sizeof(mergeT));
|
|---|
| 1013 | else
|
|---|
| 1014 | qh_setappend(&qh facet_mergeset, merge);
|
|---|
| 1015 | }
|
|---|
| 1016 | qh_settempfree(&othermerges);
|
|---|
| 1017 | if (nummerge)
|
|---|
| 1018 | *wasmerge= True;
|
|---|
| 1019 | trace1((qh ferr, 1010, "qh_flippedmerges: merged %d flipped facets into a good neighbor\n", nummerge));
|
|---|
| 1020 | } /* flippedmerges */
|
|---|
| 1021 |
|
|---|
| 1022 |
|
|---|
| 1023 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1024 | >-------------------------------</a><a name="forcedmerges">-</a>
|
|---|
| 1025 |
|
|---|
| 1026 | qh_forcedmerges( wasmerge )
|
|---|
| 1027 | merge duplicated ridges
|
|---|
| 1028 |
|
|---|
| 1029 | returns:
|
|---|
| 1030 | removes all duplicate ridges on facet_mergeset
|
|---|
| 1031 | wasmerge set if merge
|
|---|
| 1032 | qh.facet_mergeset may include non-forced merges(none for now)
|
|---|
| 1033 | qh.degen_mergeset includes degen/redun merges
|
|---|
| 1034 |
|
|---|
| 1035 | notes:
|
|---|
| 1036 | duplicate ridges occur when the horizon is pinched,
|
|---|
| 1037 | i.e. a subridge occurs in more than two horizon ridges.
|
|---|
| 1038 | could rename vertices that pinch the horizon
|
|---|
| 1039 | assumes qh_merge_degenredundant() has not be called
|
|---|
| 1040 | othermerges isn't needed since facet_mergeset is empty afterwards
|
|---|
| 1041 | keep it in case of change
|
|---|
| 1042 |
|
|---|
| 1043 | design:
|
|---|
| 1044 | for each duplicate ridge
|
|---|
| 1045 | find current facets by chasing f.replace links
|
|---|
| 1046 | determine best direction for facet
|
|---|
| 1047 | merge one facet into the other
|
|---|
| 1048 | remove duplicate ridges from qh.facet_mergeset
|
|---|
| 1049 | */
|
|---|
| 1050 | void qh_forcedmerges(boolT *wasmerge) {
|
|---|
| 1051 | facetT *facet1, *facet2;
|
|---|
| 1052 | mergeT *merge, **mergep;
|
|---|
| 1053 | realT dist1, dist2, mindist1, mindist2, maxdist1, maxdist2;
|
|---|
| 1054 | setT *othermerges;
|
|---|
| 1055 | int nummerge=0, numflip=0;
|
|---|
| 1056 |
|
|---|
| 1057 | if (qh TRACEmerge-1 == zzval_(Ztotmerge))
|
|---|
| 1058 | qhmem.IStracing= qh IStracing= qh TRACElevel;
|
|---|
| 1059 | trace4((qh ferr, 4025, "qh_forcedmerges: begin\n"));
|
|---|
| 1060 | othermerges= qh_settemppop(); /* was facet_mergeset */
|
|---|
| 1061 | qh facet_mergeset= qh_settemp(qh TEMPsize);
|
|---|
| 1062 | qh_settemppush(othermerges);
|
|---|
| 1063 | FOREACHmerge_(othermerges) {
|
|---|
| 1064 | if (merge->type != MRGridge)
|
|---|
| 1065 | continue;
|
|---|
| 1066 | facet1= merge->facet1;
|
|---|
| 1067 | facet2= merge->facet2;
|
|---|
| 1068 | while (facet1->visible) /* must exist, no qh_merge_degenredunant */
|
|---|
| 1069 | facet1= facet1->f.replace; /* previously merged facet */
|
|---|
| 1070 | while (facet2->visible)
|
|---|
| 1071 | facet2= facet2->f.replace; /* previously merged facet */
|
|---|
| 1072 | if (facet1 == facet2)
|
|---|
| 1073 | continue;
|
|---|
| 1074 | if (!qh_setin(facet2->neighbors, facet1)) {
|
|---|
| 1075 | qh_fprintf(qh ferr, 6096, "qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
|
|---|
| 1076 | merge->facet1->id, merge->facet2->id, facet1->id, facet2->id);
|
|---|
| 1077 | qh_errexit2 (qh_ERRqhull, facet1, facet2);
|
|---|
| 1078 | }
|
|---|
| 1079 | if (qh TRACEmerge-1 == zzval_(Ztotmerge))
|
|---|
| 1080 | qhmem.IStracing= qh IStracing= qh TRACElevel;
|
|---|
| 1081 | dist1= qh_getdistance(facet1, facet2, &mindist1, &maxdist1);
|
|---|
| 1082 | dist2= qh_getdistance(facet2, facet1, &mindist2, &maxdist2);
|
|---|
| 1083 | trace0((qh ferr, 16, "qh_forcedmerges: duplicate ridge between f%d and f%d, dist %2.2g and reverse dist %2.2g during p%d\n",
|
|---|
| 1084 | facet1->id, facet2->id, dist1, dist2, qh furthest_id));
|
|---|
| 1085 | if (dist1 < dist2)
|
|---|
| 1086 | qh_mergefacet(facet1, facet2, &mindist1, &maxdist1, !qh_MERGEapex);
|
|---|
| 1087 | else {
|
|---|
| 1088 | qh_mergefacet(facet2, facet1, &mindist2, &maxdist2, !qh_MERGEapex);
|
|---|
| 1089 | dist1= dist2;
|
|---|
| 1090 | facet1= facet2;
|
|---|
| 1091 | }
|
|---|
| 1092 | if (facet1->flipped) {
|
|---|
| 1093 | zinc_(Zmergeflipdup);
|
|---|
| 1094 | numflip++;
|
|---|
| 1095 | }else
|
|---|
| 1096 | nummerge++;
|
|---|
| 1097 | if (qh PRINTstatistics) {
|
|---|
| 1098 | zinc_(Zduplicate);
|
|---|
| 1099 | wadd_(Wduplicatetot, dist1);
|
|---|
| 1100 | wmax_(Wduplicatemax, dist1);
|
|---|
| 1101 | }
|
|---|
| 1102 | }
|
|---|
| 1103 | FOREACHmerge_(othermerges) {
|
|---|
| 1104 | if (merge->type == MRGridge)
|
|---|
| 1105 | qh_memfree(merge, (int)sizeof(mergeT));
|
|---|
| 1106 | else
|
|---|
| 1107 | qh_setappend(&qh facet_mergeset, merge);
|
|---|
| 1108 | }
|
|---|
| 1109 | qh_settempfree(&othermerges);
|
|---|
| 1110 | if (nummerge)
|
|---|
| 1111 | *wasmerge= True;
|
|---|
| 1112 | trace1((qh ferr, 1011, "qh_forcedmerges: merged %d facets and %d flipped facets across duplicated ridges\n",
|
|---|
| 1113 | nummerge, numflip));
|
|---|
| 1114 | } /* forcedmerges */
|
|---|
| 1115 |
|
|---|
| 1116 |
|
|---|
| 1117 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1118 | >-------------------------------</a><a name="getmergeset">-</a>
|
|---|
| 1119 |
|
|---|
| 1120 | qh_getmergeset( facetlist )
|
|---|
| 1121 | determines nonconvex facets on facetlist
|
|---|
| 1122 | tests !tested ridges and nonconvex ridges of !tested facets
|
|---|
| 1123 |
|
|---|
| 1124 | returns:
|
|---|
| 1125 | returns sorted qh.facet_mergeset of facet-neighbor pairs to be merged
|
|---|
| 1126 | all ridges tested
|
|---|
| 1127 |
|
|---|
| 1128 | notes:
|
|---|
| 1129 | assumes no nonconvex ridges with both facets tested
|
|---|
| 1130 | uses facet->tested/ridge->tested to prevent duplicate tests
|
|---|
| 1131 | can not limit tests to modified ridges since the centrum changed
|
|---|
| 1132 | uses qh.visit_id
|
|---|
| 1133 |
|
|---|
| 1134 | see:
|
|---|
| 1135 | qh_getmergeset_initial()
|
|---|
| 1136 |
|
|---|
| 1137 | design:
|
|---|
| 1138 | for each facet on facetlist
|
|---|
| 1139 | for each ridge of facet
|
|---|
| 1140 | if untested ridge
|
|---|
| 1141 | test ridge for convexity
|
|---|
| 1142 | if non-convex
|
|---|
| 1143 | append ridge to qh.facet_mergeset
|
|---|
| 1144 | sort qh.facet_mergeset by angle
|
|---|
| 1145 | */
|
|---|
| 1146 | void qh_getmergeset(facetT *facetlist) {
|
|---|
| 1147 | facetT *facet, *neighbor, **neighborp;
|
|---|
| 1148 | ridgeT *ridge, **ridgep;
|
|---|
| 1149 | int nummerges;
|
|---|
| 1150 |
|
|---|
| 1151 | nummerges= qh_setsize(qh facet_mergeset);
|
|---|
| 1152 | trace4((qh ferr, 4026, "qh_getmergeset: started.\n"));
|
|---|
| 1153 | qh visit_id++;
|
|---|
| 1154 | FORALLfacet_(facetlist) {
|
|---|
| 1155 | if (facet->tested)
|
|---|
| 1156 | continue;
|
|---|
| 1157 | facet->visitid= qh visit_id;
|
|---|
| 1158 | facet->tested= True; /* must be non-simplicial due to merge */
|
|---|
| 1159 | FOREACHneighbor_(facet)
|
|---|
| 1160 | neighbor->seen= False;
|
|---|
| 1161 | FOREACHridge_(facet->ridges) {
|
|---|
| 1162 | if (ridge->tested && !ridge->nonconvex)
|
|---|
| 1163 | continue;
|
|---|
| 1164 | /* if tested & nonconvex, need to append merge */
|
|---|
| 1165 | neighbor= otherfacet_(ridge, facet);
|
|---|
| 1166 | if (neighbor->seen) {
|
|---|
| 1167 | ridge->tested= True;
|
|---|
| 1168 | ridge->nonconvex= False;
|
|---|
| 1169 | }else if (neighbor->visitid != qh visit_id) {
|
|---|
| 1170 | ridge->tested= True;
|
|---|
| 1171 | ridge->nonconvex= False;
|
|---|
| 1172 | neighbor->seen= True; /* only one ridge is marked nonconvex */
|
|---|
| 1173 | if (qh_test_appendmerge(facet, neighbor))
|
|---|
| 1174 | ridge->nonconvex= True;
|
|---|
| 1175 | }
|
|---|
| 1176 | }
|
|---|
| 1177 | }
|
|---|
| 1178 | nummerges= qh_setsize(qh facet_mergeset);
|
|---|
| 1179 | if (qh ANGLEmerge)
|
|---|
| 1180 | qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
|
|---|
| 1181 | else
|
|---|
| 1182 | qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
|
|---|
| 1183 | if (qh POSTmerging) {
|
|---|
| 1184 | zadd_(Zmergesettot2, nummerges);
|
|---|
| 1185 | }else {
|
|---|
| 1186 | zadd_(Zmergesettot, nummerges);
|
|---|
| 1187 | zmax_(Zmergesetmax, nummerges);
|
|---|
| 1188 | }
|
|---|
| 1189 | trace2((qh ferr, 2021, "qh_getmergeset: %d merges found\n", nummerges));
|
|---|
| 1190 | } /* getmergeset */
|
|---|
| 1191 |
|
|---|
| 1192 |
|
|---|
| 1193 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1194 | >-------------------------------</a><a name="getmergeset_initial">-</a>
|
|---|
| 1195 |
|
|---|
| 1196 | qh_getmergeset_initial( facetlist )
|
|---|
| 1197 | determine initial qh.facet_mergeset for facets
|
|---|
| 1198 | tests all facet/neighbor pairs on facetlist
|
|---|
| 1199 |
|
|---|
| 1200 | returns:
|
|---|
| 1201 | sorted qh.facet_mergeset with nonconvex ridges
|
|---|
| 1202 | sets facet->tested, ridge->tested, and ridge->nonconvex
|
|---|
| 1203 |
|
|---|
| 1204 | notes:
|
|---|
| 1205 | uses visit_id, assumes ridge->nonconvex is False
|
|---|
| 1206 |
|
|---|
| 1207 | see:
|
|---|
| 1208 | qh_getmergeset()
|
|---|
| 1209 |
|
|---|
| 1210 | design:
|
|---|
| 1211 | for each facet on facetlist
|
|---|
| 1212 | for each untested neighbor of facet
|
|---|
| 1213 | test facet and neighbor for convexity
|
|---|
| 1214 | if non-convex
|
|---|
| 1215 | append merge to qh.facet_mergeset
|
|---|
| 1216 | mark one of the ridges as nonconvex
|
|---|
| 1217 | sort qh.facet_mergeset by angle
|
|---|
| 1218 | */
|
|---|
| 1219 | void qh_getmergeset_initial(facetT *facetlist) {
|
|---|
| 1220 | facetT *facet, *neighbor, **neighborp;
|
|---|
| 1221 | ridgeT *ridge, **ridgep;
|
|---|
| 1222 | int nummerges;
|
|---|
| 1223 |
|
|---|
| 1224 | qh visit_id++;
|
|---|
| 1225 | FORALLfacet_(facetlist) {
|
|---|
| 1226 | facet->visitid= qh visit_id;
|
|---|
| 1227 | facet->tested= True;
|
|---|
| 1228 | FOREACHneighbor_(facet) {
|
|---|
| 1229 | if (neighbor->visitid != qh visit_id) {
|
|---|
| 1230 | if (qh_test_appendmerge(facet, neighbor)) {
|
|---|
| 1231 | FOREACHridge_(neighbor->ridges) {
|
|---|
| 1232 | if (facet == otherfacet_(ridge, neighbor)) {
|
|---|
| 1233 | ridge->nonconvex= True;
|
|---|
| 1234 | break; /* only one ridge is marked nonconvex */
|
|---|
| 1235 | }
|
|---|
| 1236 | }
|
|---|
| 1237 | }
|
|---|
| 1238 | }
|
|---|
| 1239 | }
|
|---|
| 1240 | FOREACHridge_(facet->ridges)
|
|---|
| 1241 | ridge->tested= True;
|
|---|
| 1242 | }
|
|---|
| 1243 | nummerges= qh_setsize(qh facet_mergeset);
|
|---|
| 1244 | if (qh ANGLEmerge)
|
|---|
| 1245 | qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_compareangle);
|
|---|
| 1246 | else
|
|---|
| 1247 | qsort(SETaddr_(qh facet_mergeset, mergeT), (size_t)nummerges, sizeof(mergeT *), qh_comparemerge);
|
|---|
| 1248 | if (qh POSTmerging) {
|
|---|
| 1249 | zadd_(Zmergeinittot2, nummerges);
|
|---|
| 1250 | }else {
|
|---|
| 1251 | zadd_(Zmergeinittot, nummerges);
|
|---|
| 1252 | zmax_(Zmergeinitmax, nummerges);
|
|---|
| 1253 | }
|
|---|
| 1254 | trace2((qh ferr, 2022, "qh_getmergeset_initial: %d merges found\n", nummerges));
|
|---|
| 1255 | } /* getmergeset_initial */
|
|---|
| 1256 |
|
|---|
| 1257 |
|
|---|
| 1258 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1259 | >-------------------------------</a><a name="hashridge">-</a>
|
|---|
| 1260 |
|
|---|
| 1261 | qh_hashridge( hashtable, hashsize, ridge, oldvertex )
|
|---|
| 1262 | add ridge to hashtable without oldvertex
|
|---|
| 1263 |
|
|---|
| 1264 | notes:
|
|---|
| 1265 | assumes hashtable is large enough
|
|---|
| 1266 |
|
|---|
| 1267 | design:
|
|---|
| 1268 | determine hash value for ridge without oldvertex
|
|---|
| 1269 | find next empty slot for ridge
|
|---|
| 1270 | */
|
|---|
| 1271 | void qh_hashridge(setT *hashtable, int hashsize, ridgeT *ridge, vertexT *oldvertex) {
|
|---|
| 1272 | int hash;
|
|---|
| 1273 | ridgeT *ridgeA;
|
|---|
| 1274 |
|
|---|
| 1275 | hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, oldvertex);
|
|---|
| 1276 | while (True) {
|
|---|
| 1277 | if (!(ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
|
|---|
| 1278 | SETelem_(hashtable, hash)= ridge;
|
|---|
| 1279 | break;
|
|---|
| 1280 | }else if (ridgeA == ridge)
|
|---|
| 1281 | break;
|
|---|
| 1282 | if (++hash == hashsize)
|
|---|
| 1283 | hash= 0;
|
|---|
| 1284 | }
|
|---|
| 1285 | } /* hashridge */
|
|---|
| 1286 |
|
|---|
| 1287 |
|
|---|
| 1288 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1289 | >-------------------------------</a><a name="hashridge_find">-</a>
|
|---|
| 1290 |
|
|---|
| 1291 | qh_hashridge_find( hashtable, hashsize, ridge, vertex, oldvertex, hashslot )
|
|---|
| 1292 | returns matching ridge without oldvertex in hashtable
|
|---|
| 1293 | for ridge without vertex
|
|---|
| 1294 | if oldvertex is NULL
|
|---|
| 1295 | matches with any one skip
|
|---|
| 1296 |
|
|---|
| 1297 | returns:
|
|---|
| 1298 | matching ridge or NULL
|
|---|
| 1299 | if no match,
|
|---|
| 1300 | if ridge already in table
|
|---|
| 1301 | hashslot= -1
|
|---|
| 1302 | else
|
|---|
| 1303 | hashslot= next NULL index
|
|---|
| 1304 |
|
|---|
| 1305 | notes:
|
|---|
| 1306 | assumes hashtable is large enough
|
|---|
| 1307 | can't match ridge to itself
|
|---|
| 1308 |
|
|---|
| 1309 | design:
|
|---|
| 1310 | get hash value for ridge without vertex
|
|---|
| 1311 | for each hashslot
|
|---|
| 1312 | return match if ridge matches ridgeA without oldvertex
|
|---|
| 1313 | */
|
|---|
| 1314 | ridgeT *qh_hashridge_find(setT *hashtable, int hashsize, ridgeT *ridge,
|
|---|
| 1315 | vertexT *vertex, vertexT *oldvertex, int *hashslot) {
|
|---|
| 1316 | int hash;
|
|---|
| 1317 | ridgeT *ridgeA;
|
|---|
| 1318 |
|
|---|
| 1319 | *hashslot= 0;
|
|---|
| 1320 | zinc_(Zhashridge);
|
|---|
| 1321 | hash= qh_gethash(hashsize, ridge->vertices, qh hull_dim-1, 0, vertex);
|
|---|
| 1322 | while ((ridgeA= SETelemt_(hashtable, hash, ridgeT))) {
|
|---|
| 1323 | if (ridgeA == ridge)
|
|---|
| 1324 | *hashslot= -1;
|
|---|
| 1325 | else {
|
|---|
| 1326 | zinc_(Zhashridgetest);
|
|---|
| 1327 | if (qh_setequal_except(ridge->vertices, vertex, ridgeA->vertices, oldvertex))
|
|---|
| 1328 | return ridgeA;
|
|---|
| 1329 | }
|
|---|
| 1330 | if (++hash == hashsize)
|
|---|
| 1331 | hash= 0;
|
|---|
| 1332 | }
|
|---|
| 1333 | if (!*hashslot)
|
|---|
| 1334 | *hashslot= hash;
|
|---|
| 1335 | return NULL;
|
|---|
| 1336 | } /* hashridge_find */
|
|---|
| 1337 |
|
|---|
| 1338 |
|
|---|
| 1339 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1340 | >-------------------------------</a><a name="makeridges">-</a>
|
|---|
| 1341 |
|
|---|
| 1342 | qh_makeridges( facet )
|
|---|
| 1343 | creates explicit ridges between simplicial facets
|
|---|
| 1344 |
|
|---|
| 1345 | returns:
|
|---|
| 1346 | facet with ridges and without qh_MERGEridge
|
|---|
| 1347 | ->simplicial is False
|
|---|
| 1348 |
|
|---|
| 1349 | notes:
|
|---|
| 1350 | allows qh_MERGEridge flag
|
|---|
| 1351 | uses existing ridges
|
|---|
| 1352 | duplicate neighbors ok if ridges already exist (qh_mergecycle_ridges)
|
|---|
| 1353 |
|
|---|
| 1354 | see:
|
|---|
| 1355 | qh_mergecycle_ridges()
|
|---|
| 1356 |
|
|---|
| 1357 | design:
|
|---|
| 1358 | look for qh_MERGEridge neighbors
|
|---|
| 1359 | mark neighbors that already have ridges
|
|---|
| 1360 | for each unprocessed neighbor of facet
|
|---|
| 1361 | create a ridge for neighbor and facet
|
|---|
| 1362 | if any qh_MERGEridge neighbors
|
|---|
| 1363 | delete qh_MERGEridge flags (already handled by qh_mark_dupridges)
|
|---|
| 1364 | */
|
|---|
| 1365 | void qh_makeridges(facetT *facet) {
|
|---|
| 1366 | facetT *neighbor, **neighborp;
|
|---|
| 1367 | ridgeT *ridge, **ridgep;
|
|---|
| 1368 | int neighbor_i, neighbor_n;
|
|---|
| 1369 | boolT toporient, mergeridge= False;
|
|---|
| 1370 |
|
|---|
| 1371 | if (!facet->simplicial)
|
|---|
| 1372 | return;
|
|---|
| 1373 | trace4((qh ferr, 4027, "qh_makeridges: make ridges for f%d\n", facet->id));
|
|---|
| 1374 | facet->simplicial= False;
|
|---|
| 1375 | FOREACHneighbor_(facet) {
|
|---|
| 1376 | if (neighbor == qh_MERGEridge)
|
|---|
| 1377 | mergeridge= True;
|
|---|
| 1378 | else
|
|---|
| 1379 | neighbor->seen= False;
|
|---|
| 1380 | }
|
|---|
| 1381 | FOREACHridge_(facet->ridges)
|
|---|
| 1382 | otherfacet_(ridge, facet)->seen= True;
|
|---|
| 1383 | FOREACHneighbor_i_(facet) {
|
|---|
| 1384 | if (neighbor == qh_MERGEridge)
|
|---|
| 1385 | continue; /* fixed by qh_mark_dupridges */
|
|---|
| 1386 | else if (!neighbor->seen) { /* no current ridges */
|
|---|
| 1387 | ridge= qh_newridge();
|
|---|
| 1388 | ridge->vertices= qh_setnew_delnthsorted(facet->vertices, qh hull_dim,
|
|---|
| 1389 | neighbor_i, 0);
|
|---|
| 1390 | toporient= facet->toporient ^ (neighbor_i & 0x1);
|
|---|
| 1391 | if (toporient) {
|
|---|
| 1392 | ridge->top= facet;
|
|---|
| 1393 | ridge->bottom= neighbor;
|
|---|
| 1394 | }else {
|
|---|
| 1395 | ridge->top= neighbor;
|
|---|
| 1396 | ridge->bottom= facet;
|
|---|
| 1397 | }
|
|---|
| 1398 | #if 0 /* this also works */
|
|---|
| 1399 | flip= (facet->toporient ^ neighbor->toporient)^(skip1 & 0x1) ^ (skip2 & 0x1);
|
|---|
| 1400 | if (facet->toporient ^ (skip1 & 0x1) ^ flip) {
|
|---|
| 1401 | ridge->top= neighbor;
|
|---|
| 1402 | ridge->bottom= facet;
|
|---|
| 1403 | }else {
|
|---|
| 1404 | ridge->top= facet;
|
|---|
| 1405 | ridge->bottom= neighbor;
|
|---|
| 1406 | }
|
|---|
| 1407 | #endif
|
|---|
| 1408 | qh_setappend(&(facet->ridges), ridge);
|
|---|
| 1409 | qh_setappend(&(neighbor->ridges), ridge);
|
|---|
| 1410 | }
|
|---|
| 1411 | }
|
|---|
| 1412 | if (mergeridge) {
|
|---|
| 1413 | while (qh_setdel(facet->neighbors, qh_MERGEridge))
|
|---|
| 1414 | ; /* delete each one */
|
|---|
| 1415 | }
|
|---|
| 1416 | } /* makeridges */
|
|---|
| 1417 |
|
|---|
| 1418 |
|
|---|
| 1419 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1420 | >-------------------------------</a><a name="mark_dupridges">-</a>
|
|---|
| 1421 |
|
|---|
| 1422 | qh_mark_dupridges( facetlist )
|
|---|
| 1423 | add duplicated ridges to qh.facet_mergeset
|
|---|
| 1424 | facet->dupridge is true
|
|---|
| 1425 |
|
|---|
| 1426 | returns:
|
|---|
| 1427 | duplicate ridges on qh.facet_mergeset
|
|---|
| 1428 | ->mergeridge/->mergeridge2 set
|
|---|
| 1429 | duplicate ridges marked by qh_MERGEridge and both sides facet->dupridge
|
|---|
| 1430 | no MERGEridges in neighbor sets
|
|---|
| 1431 |
|
|---|
| 1432 | notes:
|
|---|
| 1433 | duplicate ridges occur when the horizon is pinched,
|
|---|
| 1434 | i.e. a subridge occurs in more than two horizon ridges.
|
|---|
| 1435 | could rename vertices that pinch the horizon
|
|---|
| 1436 | uses qh.visit_id
|
|---|
| 1437 |
|
|---|
| 1438 | design:
|
|---|
| 1439 | for all facets on facetlist
|
|---|
| 1440 | if facet contains a duplicate ridge
|
|---|
| 1441 | for each neighbor of facet
|
|---|
| 1442 | if neighbor marked qh_MERGEridge (one side of the merge)
|
|---|
| 1443 | set facet->mergeridge
|
|---|
| 1444 | else
|
|---|
| 1445 | if neighbor contains a duplicate ridge
|
|---|
| 1446 | and the back link is qh_MERGEridge
|
|---|
| 1447 | append duplicate ridge to qh.facet_mergeset
|
|---|
| 1448 | for each duplicate ridge
|
|---|
| 1449 | make ridge sets in preparation for merging
|
|---|
| 1450 | remove qh_MERGEridge from neighbor set
|
|---|
| 1451 | for each duplicate ridge
|
|---|
| 1452 | restore the missing neighbor from the neighbor set that was qh_MERGEridge
|
|---|
| 1453 | add the missing ridge for this neighbor
|
|---|
| 1454 | */
|
|---|
| 1455 | void qh_mark_dupridges(facetT *facetlist) {
|
|---|
| 1456 | facetT *facet, *neighbor, **neighborp;
|
|---|
| 1457 | int nummerge=0;
|
|---|
| 1458 | mergeT *merge, **mergep;
|
|---|
| 1459 |
|
|---|
| 1460 |
|
|---|
| 1461 | trace4((qh ferr, 4028, "qh_mark_dupridges: identify duplicate ridges\n"));
|
|---|
| 1462 | FORALLfacet_(facetlist) {
|
|---|
| 1463 | if (facet->dupridge) {
|
|---|
| 1464 | FOREACHneighbor_(facet) {
|
|---|
| 1465 | if (neighbor == qh_MERGEridge) {
|
|---|
| 1466 | facet->mergeridge= True;
|
|---|
| 1467 | continue;
|
|---|
| 1468 | }
|
|---|
| 1469 | if (neighbor->dupridge
|
|---|
| 1470 | && !qh_setin(neighbor->neighbors, facet)) { /* qh_MERGEridge */
|
|---|
| 1471 | qh_appendmergeset(facet, neighbor, MRGridge, NULL);
|
|---|
| 1472 | facet->mergeridge2= True;
|
|---|
| 1473 | facet->mergeridge= True;
|
|---|
| 1474 | nummerge++;
|
|---|
| 1475 | }
|
|---|
| 1476 | }
|
|---|
| 1477 | }
|
|---|
| 1478 | }
|
|---|
| 1479 | if (!nummerge)
|
|---|
| 1480 | return;
|
|---|
| 1481 | FORALLfacet_(facetlist) { /* gets rid of qh_MERGEridge */
|
|---|
| 1482 | if (facet->mergeridge && !facet->mergeridge2)
|
|---|
| 1483 | qh_makeridges(facet);
|
|---|
| 1484 | }
|
|---|
| 1485 | FOREACHmerge_(qh facet_mergeset) { /* restore the missing neighbors */
|
|---|
| 1486 | if (merge->type == MRGridge) {
|
|---|
| 1487 | qh_setappend(&merge->facet2->neighbors, merge->facet1);
|
|---|
| 1488 | qh_makeridges(merge->facet1); /* and the missing ridges */
|
|---|
| 1489 | }
|
|---|
| 1490 | }
|
|---|
| 1491 | trace1((qh ferr, 1012, "qh_mark_dupridges: found %d duplicated ridges\n",
|
|---|
| 1492 | nummerge));
|
|---|
| 1493 | } /* mark_dupridges */
|
|---|
| 1494 |
|
|---|
| 1495 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1496 | >-------------------------------</a><a name="maydropneighbor">-</a>
|
|---|
| 1497 |
|
|---|
| 1498 | qh_maydropneighbor( facet )
|
|---|
| 1499 | drop neighbor relationship if no ridge between facet and neighbor
|
|---|
| 1500 |
|
|---|
| 1501 | returns:
|
|---|
| 1502 | neighbor sets updated
|
|---|
| 1503 | appends degenerate facets to qh.facet_mergeset
|
|---|
| 1504 |
|
|---|
| 1505 | notes:
|
|---|
| 1506 | won't cause redundant facets since vertex inclusion is the same
|
|---|
| 1507 | may drop vertex and neighbor if no ridge
|
|---|
| 1508 | uses qh.visit_id
|
|---|
| 1509 |
|
|---|
| 1510 | design:
|
|---|
| 1511 | visit all neighbors with ridges
|
|---|
| 1512 | for each unvisited neighbor of facet
|
|---|
| 1513 | delete neighbor and facet from the neighbor sets
|
|---|
| 1514 | if neighbor becomes degenerate
|
|---|
| 1515 | append neighbor to qh.degen_mergeset
|
|---|
| 1516 | if facet is degenerate
|
|---|
| 1517 | append facet to qh.degen_mergeset
|
|---|
| 1518 | */
|
|---|
| 1519 | void qh_maydropneighbor(facetT *facet) {
|
|---|
| 1520 | ridgeT *ridge, **ridgep;
|
|---|
| 1521 | realT angledegen= qh_ANGLEdegen;
|
|---|
| 1522 | facetT *neighbor, **neighborp;
|
|---|
| 1523 |
|
|---|
| 1524 | qh visit_id++;
|
|---|
| 1525 | trace4((qh ferr, 4029, "qh_maydropneighbor: test f%d for no ridges to a neighbor\n",
|
|---|
| 1526 | facet->id));
|
|---|
| 1527 | FOREACHridge_(facet->ridges) {
|
|---|
| 1528 | ridge->top->visitid= qh visit_id;
|
|---|
| 1529 | ridge->bottom->visitid= qh visit_id;
|
|---|
| 1530 | }
|
|---|
| 1531 | FOREACHneighbor_(facet) {
|
|---|
| 1532 | if (neighbor->visitid != qh visit_id) {
|
|---|
| 1533 | trace0((qh ferr, 17, "qh_maydropneighbor: facets f%d and f%d are no longer neighbors during p%d\n",
|
|---|
| 1534 | facet->id, neighbor->id, qh furthest_id));
|
|---|
| 1535 | zinc_(Zdropneighbor);
|
|---|
| 1536 | qh_setdel(facet->neighbors, neighbor);
|
|---|
| 1537 | neighborp--; /* repeat, deleted a neighbor */
|
|---|
| 1538 | qh_setdel(neighbor->neighbors, facet);
|
|---|
| 1539 | if (qh_setsize(neighbor->neighbors) < qh hull_dim) {
|
|---|
| 1540 | zinc_(Zdropdegen);
|
|---|
| 1541 | qh_appendmergeset(neighbor, neighbor, MRGdegen, &angledegen);
|
|---|
| 1542 | trace2((qh ferr, 2023, "qh_maydropneighbors: f%d is degenerate.\n", neighbor->id));
|
|---|
| 1543 | }
|
|---|
| 1544 | }
|
|---|
| 1545 | }
|
|---|
| 1546 | if (qh_setsize(facet->neighbors) < qh hull_dim) {
|
|---|
| 1547 | zinc_(Zdropdegen);
|
|---|
| 1548 | qh_appendmergeset(facet, facet, MRGdegen, &angledegen);
|
|---|
| 1549 | trace2((qh ferr, 2024, "qh_maydropneighbors: f%d is degenerate.\n", facet->id));
|
|---|
| 1550 | }
|
|---|
| 1551 | } /* maydropneighbor */
|
|---|
| 1552 |
|
|---|
| 1553 |
|
|---|
| 1554 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1555 | >-------------------------------</a><a name="merge_degenredundant">-</a>
|
|---|
| 1556 |
|
|---|
| 1557 | qh_merge_degenredundant()
|
|---|
| 1558 | merge all degenerate and redundant facets
|
|---|
| 1559 | qh.degen_mergeset contains merges from qh_degen_redundant_neighbors()
|
|---|
| 1560 |
|
|---|
| 1561 | returns:
|
|---|
| 1562 | number of merges performed
|
|---|
| 1563 | resets facet->degenerate/redundant
|
|---|
| 1564 | if deleted (visible) facet has no neighbors
|
|---|
| 1565 | sets ->f.replace to NULL
|
|---|
| 1566 |
|
|---|
| 1567 | notes:
|
|---|
| 1568 | redundant merges happen before degenerate ones
|
|---|
| 1569 | merging and renaming vertices can result in degen/redundant facets
|
|---|
| 1570 |
|
|---|
| 1571 | design:
|
|---|
| 1572 | for each merge on qh.degen_mergeset
|
|---|
| 1573 | if redundant merge
|
|---|
| 1574 | if non-redundant facet merged into redundant facet
|
|---|
| 1575 | recheck facet for redundancy
|
|---|
| 1576 | else
|
|---|
| 1577 | merge redundant facet into other facet
|
|---|
| 1578 | */
|
|---|
| 1579 | int qh_merge_degenredundant(void) {
|
|---|
| 1580 | int size;
|
|---|
| 1581 | mergeT *merge;
|
|---|
| 1582 | facetT *bestneighbor, *facet1, *facet2;
|
|---|
| 1583 | realT dist, mindist, maxdist;
|
|---|
| 1584 | vertexT *vertex, **vertexp;
|
|---|
| 1585 | int nummerges= 0;
|
|---|
| 1586 | mergeType mergetype;
|
|---|
| 1587 |
|
|---|
| 1588 | while ((merge= (mergeT*)qh_setdellast(qh degen_mergeset))) {
|
|---|
| 1589 | facet1= merge->facet1;
|
|---|
| 1590 | facet2= merge->facet2;
|
|---|
| 1591 | mergetype= merge->type;
|
|---|
| 1592 | qh_memfree(merge, (int)sizeof(mergeT));
|
|---|
| 1593 | if (facet1->visible)
|
|---|
| 1594 | continue;
|
|---|
| 1595 | facet1->degenerate= False;
|
|---|
| 1596 | facet1->redundant= False;
|
|---|
| 1597 | if (qh TRACEmerge-1 == zzval_(Ztotmerge))
|
|---|
| 1598 | qhmem.IStracing= qh IStracing= qh TRACElevel;
|
|---|
| 1599 | if (mergetype == MRGredundant) {
|
|---|
| 1600 | zinc_(Zneighbor);
|
|---|
| 1601 | while (facet2->visible) {
|
|---|
| 1602 | if (!facet2->f.replace) {
|
|---|
| 1603 | qh_fprintf(qh ferr, 6097, "qhull internal error (qh_merge_degenredunant): f%d redundant but f%d has no replacement\n",
|
|---|
| 1604 | facet1->id, facet2->id);
|
|---|
| 1605 | qh_errexit2 (qh_ERRqhull, facet1, facet2);
|
|---|
| 1606 | }
|
|---|
| 1607 | facet2= facet2->f.replace;
|
|---|
| 1608 | }
|
|---|
| 1609 | if (facet1 == facet2) {
|
|---|
| 1610 | qh_degen_redundant_facet(facet1); /* in case of others */
|
|---|
| 1611 | continue;
|
|---|
| 1612 | }
|
|---|
| 1613 | trace2((qh ferr, 2025, "qh_merge_degenredundant: facet f%d is contained in f%d, will merge\n",
|
|---|
| 1614 | facet1->id, facet2->id));
|
|---|
| 1615 | qh_mergefacet(facet1, facet2, NULL, NULL, !qh_MERGEapex);
|
|---|
| 1616 | /* merge distance is already accounted for */
|
|---|
| 1617 | nummerges++;
|
|---|
| 1618 | }else { /* mergetype == MRGdegen, other merges may have fixed */
|
|---|
| 1619 | if (!(size= qh_setsize(facet1->neighbors))) {
|
|---|
| 1620 | zinc_(Zdelfacetdup);
|
|---|
| 1621 | trace2((qh ferr, 2026, "qh_merge_degenredundant: facet f%d has no neighbors. Deleted\n", facet1->id));
|
|---|
| 1622 | qh_willdelete(facet1, NULL);
|
|---|
| 1623 | FOREACHvertex_(facet1->vertices) {
|
|---|
| 1624 | qh_setdel(vertex->neighbors, facet1);
|
|---|
| 1625 | if (!SETfirst_(vertex->neighbors)) {
|
|---|
| 1626 | zinc_(Zdegenvertex);
|
|---|
| 1627 | trace2((qh ferr, 2027, "qh_merge_degenredundant: deleted v%d because f%d has no neighbors\n",
|
|---|
| 1628 | vertex->id, facet1->id));
|
|---|
| 1629 | vertex->deleted= True;
|
|---|
| 1630 | qh_setappend(&qh del_vertices, vertex);
|
|---|
| 1631 | }
|
|---|
| 1632 | }
|
|---|
| 1633 | nummerges++;
|
|---|
| 1634 | }else if (size < qh hull_dim) {
|
|---|
| 1635 | bestneighbor= qh_findbestneighbor(facet1, &dist, &mindist, &maxdist);
|
|---|
| 1636 | trace2((qh ferr, 2028, "qh_merge_degenredundant: facet f%d has %d neighbors, merge into f%d dist %2.2g\n",
|
|---|
| 1637 | facet1->id, size, bestneighbor->id, dist));
|
|---|
| 1638 | qh_mergefacet(facet1, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
|
|---|
| 1639 | nummerges++;
|
|---|
| 1640 | if (qh PRINTstatistics) {
|
|---|
| 1641 | zinc_(Zdegen);
|
|---|
| 1642 | wadd_(Wdegentot, dist);
|
|---|
| 1643 | wmax_(Wdegenmax, dist);
|
|---|
| 1644 | }
|
|---|
| 1645 | } /* else, another merge fixed the degeneracy and redundancy tested */
|
|---|
| 1646 | }
|
|---|
| 1647 | }
|
|---|
| 1648 | return nummerges;
|
|---|
| 1649 | } /* merge_degenredundant */
|
|---|
| 1650 |
|
|---|
| 1651 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1652 | >-------------------------------</a><a name="merge_nonconvex">-</a>
|
|---|
| 1653 |
|
|---|
| 1654 | qh_merge_nonconvex( facet1, facet2, mergetype )
|
|---|
| 1655 | remove non-convex ridge between facet1 into facet2
|
|---|
| 1656 | mergetype gives why the facet's are non-convex
|
|---|
| 1657 |
|
|---|
| 1658 | returns:
|
|---|
| 1659 | merges one of the facets into the best neighbor
|
|---|
| 1660 |
|
|---|
| 1661 | design:
|
|---|
| 1662 | if one of the facets is a new facet
|
|---|
| 1663 | prefer merging new facet into old facet
|
|---|
| 1664 | find best neighbors for both facets
|
|---|
| 1665 | merge the nearest facet into its best neighbor
|
|---|
| 1666 | update the statistics
|
|---|
| 1667 | */
|
|---|
| 1668 | void qh_merge_nonconvex(facetT *facet1, facetT *facet2, mergeType mergetype) {
|
|---|
| 1669 | facetT *bestfacet, *bestneighbor, *neighbor;
|
|---|
| 1670 | realT dist, dist2, mindist, mindist2, maxdist, maxdist2;
|
|---|
| 1671 |
|
|---|
| 1672 | if (qh TRACEmerge-1 == zzval_(Ztotmerge))
|
|---|
| 1673 | qhmem.IStracing= qh IStracing= qh TRACElevel;
|
|---|
| 1674 | trace3((qh ferr, 3003, "qh_merge_nonconvex: merge #%d for f%d and f%d type %d\n",
|
|---|
| 1675 | zzval_(Ztotmerge) + 1, facet1->id, facet2->id, mergetype));
|
|---|
| 1676 | /* concave or coplanar */
|
|---|
| 1677 | if (!facet1->newfacet) {
|
|---|
| 1678 | bestfacet= facet2; /* avoid merging old facet if new is ok */
|
|---|
| 1679 | facet2= facet1;
|
|---|
| 1680 | facet1= bestfacet;
|
|---|
| 1681 | }else
|
|---|
| 1682 | bestfacet= facet1;
|
|---|
| 1683 | bestneighbor= qh_findbestneighbor(bestfacet, &dist, &mindist, &maxdist);
|
|---|
| 1684 | neighbor= qh_findbestneighbor(facet2, &dist2, &mindist2, &maxdist2);
|
|---|
| 1685 | if (dist < dist2) {
|
|---|
| 1686 | qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
|
|---|
| 1687 | }else if (qh AVOIDold && !facet2->newfacet
|
|---|
| 1688 | && ((mindist >= -qh MAXcoplanar && maxdist <= qh max_outside)
|
|---|
| 1689 | || dist * 1.5 < dist2)) {
|
|---|
| 1690 | zinc_(Zavoidold);
|
|---|
| 1691 | wadd_(Wavoidoldtot, dist);
|
|---|
| 1692 | wmax_(Wavoidoldmax, dist);
|
|---|
| 1693 | trace2((qh ferr, 2029, "qh_merge_nonconvex: avoid merging old facet f%d dist %2.2g. Use f%d dist %2.2g instead\n",
|
|---|
| 1694 | facet2->id, dist2, facet1->id, dist2));
|
|---|
| 1695 | qh_mergefacet(bestfacet, bestneighbor, &mindist, &maxdist, !qh_MERGEapex);
|
|---|
| 1696 | }else {
|
|---|
| 1697 | qh_mergefacet(facet2, neighbor, &mindist2, &maxdist2, !qh_MERGEapex);
|
|---|
| 1698 | dist= dist2;
|
|---|
| 1699 | }
|
|---|
| 1700 | if (qh PRINTstatistics) {
|
|---|
| 1701 | if (mergetype == MRGanglecoplanar) {
|
|---|
| 1702 | zinc_(Zacoplanar);
|
|---|
| 1703 | wadd_(Wacoplanartot, dist);
|
|---|
| 1704 | wmax_(Wacoplanarmax, dist);
|
|---|
| 1705 | }else if (mergetype == MRGconcave) {
|
|---|
| 1706 | zinc_(Zconcave);
|
|---|
| 1707 | wadd_(Wconcavetot, dist);
|
|---|
| 1708 | wmax_(Wconcavemax, dist);
|
|---|
| 1709 | }else { /* MRGcoplanar */
|
|---|
| 1710 | zinc_(Zcoplanar);
|
|---|
| 1711 | wadd_(Wcoplanartot, dist);
|
|---|
| 1712 | wmax_(Wcoplanarmax, dist);
|
|---|
| 1713 | }
|
|---|
| 1714 | }
|
|---|
| 1715 | } /* merge_nonconvex */
|
|---|
| 1716 |
|
|---|
| 1717 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1718 | >-------------------------------</a><a name="mergecycle">-</a>
|
|---|
| 1719 |
|
|---|
| 1720 | qh_mergecycle( samecycle, newfacet )
|
|---|
| 1721 | merge a cycle of facets starting at samecycle into a newfacet
|
|---|
| 1722 | newfacet is a horizon facet with ->normal
|
|---|
| 1723 | samecycle facets are simplicial from an apex
|
|---|
| 1724 |
|
|---|
| 1725 | returns:
|
|---|
| 1726 | initializes vertex neighbors on first merge
|
|---|
| 1727 | samecycle deleted (placed on qh.visible_list)
|
|---|
| 1728 | newfacet at end of qh.facet_list
|
|---|
| 1729 | deleted vertices on qh.del_vertices
|
|---|
| 1730 |
|
|---|
| 1731 | see:
|
|---|
| 1732 | qh_mergefacet()
|
|---|
| 1733 | called by qh_mergecycle_all() for multiple, same cycle facets
|
|---|
| 1734 |
|
|---|
| 1735 | design:
|
|---|
| 1736 | make vertex neighbors if necessary
|
|---|
| 1737 | make ridges for newfacet
|
|---|
| 1738 | merge neighbor sets of samecycle into newfacet
|
|---|
| 1739 | merge ridges of samecycle into newfacet
|
|---|
| 1740 | merge vertex neighbors of samecycle into newfacet
|
|---|
| 1741 | make apex of samecycle the apex of newfacet
|
|---|
| 1742 | if newfacet wasn't a new facet
|
|---|
| 1743 | add its vertices to qh.newvertex_list
|
|---|
| 1744 | delete samecycle facets a make newfacet a newfacet
|
|---|
| 1745 | */
|
|---|
| 1746 | void qh_mergecycle(facetT *samecycle, facetT *newfacet) {
|
|---|
| 1747 | int traceonce= False, tracerestore= 0;
|
|---|
| 1748 | vertexT *apex;
|
|---|
| 1749 | #ifndef qh_NOtrace
|
|---|
| 1750 | facetT *same;
|
|---|
| 1751 | #endif
|
|---|
| 1752 |
|
|---|
| 1753 | if (newfacet->tricoplanar) {
|
|---|
| 1754 | if (!qh TRInormals) {
|
|---|
| 1755 | qh_fprintf(qh ferr, 6224, "Qhull internal error (qh_mergecycle): does not work for tricoplanar facets. Use option 'Q11'\n");
|
|---|
| 1756 | qh_errexit(qh_ERRqhull, newfacet, NULL);
|
|---|
| 1757 | }
|
|---|
| 1758 | newfacet->tricoplanar= False;
|
|---|
| 1759 | newfacet->keepcentrum= False;
|
|---|
| 1760 | }
|
|---|
| 1761 | if (!qh VERTEXneighbors)
|
|---|
| 1762 | qh_vertexneighbors();
|
|---|
| 1763 | zzinc_(Ztotmerge);
|
|---|
| 1764 | if (qh REPORTfreq2 && qh POSTmerging) {
|
|---|
| 1765 | if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
|
|---|
| 1766 | qh_tracemerging();
|
|---|
| 1767 | }
|
|---|
| 1768 | #ifndef qh_NOtrace
|
|---|
| 1769 | if (qh TRACEmerge == zzval_(Ztotmerge))
|
|---|
| 1770 | qhmem.IStracing= qh IStracing= qh TRACElevel;
|
|---|
| 1771 | trace2((qh ferr, 2030, "qh_mergecycle: merge #%d for facets from cycle f%d into coplanar horizon f%d\n",
|
|---|
| 1772 | zzval_(Ztotmerge), samecycle->id, newfacet->id));
|
|---|
| 1773 | if (newfacet == qh tracefacet) {
|
|---|
| 1774 | tracerestore= qh IStracing;
|
|---|
| 1775 | qh IStracing= 4;
|
|---|
| 1776 | qh_fprintf(qh ferr, 8068, "qh_mergecycle: ========= trace merge %d of samecycle %d into trace f%d, furthest is p%d\n",
|
|---|
| 1777 | zzval_(Ztotmerge), samecycle->id, newfacet->id, qh furthest_id);
|
|---|
| 1778 | traceonce= True;
|
|---|
| 1779 | }
|
|---|
| 1780 | if (qh IStracing >=4) {
|
|---|
| 1781 | qh_fprintf(qh ferr, 8069, " same cycle:");
|
|---|
| 1782 | FORALLsame_cycle_(samecycle)
|
|---|
| 1783 | qh_fprintf(qh ferr, 8070, " f%d", same->id);
|
|---|
| 1784 | qh_fprintf(qh ferr, 8071, "\n");
|
|---|
| 1785 | }
|
|---|
| 1786 | if (qh IStracing >=4)
|
|---|
| 1787 | qh_errprint("MERGING CYCLE", samecycle, newfacet, NULL, NULL);
|
|---|
| 1788 | #endif /* !qh_NOtrace */
|
|---|
| 1789 | apex= SETfirstt_(samecycle->vertices, vertexT);
|
|---|
| 1790 | qh_makeridges(newfacet);
|
|---|
| 1791 | qh_mergecycle_neighbors(samecycle, newfacet);
|
|---|
| 1792 | qh_mergecycle_ridges(samecycle, newfacet);
|
|---|
| 1793 | qh_mergecycle_vneighbors(samecycle, newfacet);
|
|---|
| 1794 | if (SETfirstt_(newfacet->vertices, vertexT) != apex)
|
|---|
| 1795 | qh_setaddnth(&newfacet->vertices, 0, apex); /* apex has last id */
|
|---|
| 1796 | if (!newfacet->newfacet)
|
|---|
| 1797 | qh_newvertices(newfacet->vertices);
|
|---|
| 1798 | qh_mergecycle_facets(samecycle, newfacet);
|
|---|
| 1799 | qh_tracemerge(samecycle, newfacet);
|
|---|
| 1800 | /* check for degen_redundant_neighbors after qh_forcedmerges() */
|
|---|
| 1801 | if (traceonce) {
|
|---|
| 1802 | qh_fprintf(qh ferr, 8072, "qh_mergecycle: end of trace facet\n");
|
|---|
| 1803 | qh IStracing= tracerestore;
|
|---|
| 1804 | }
|
|---|
| 1805 | } /* mergecycle */
|
|---|
| 1806 |
|
|---|
| 1807 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1808 | >-------------------------------</a><a name="mergecycle_all">-</a>
|
|---|
| 1809 |
|
|---|
| 1810 | qh_mergecycle_all( facetlist, wasmerge )
|
|---|
| 1811 | merge all samecycles of coplanar facets into horizon
|
|---|
| 1812 | don't merge facets with ->mergeridge (these already have ->normal)
|
|---|
| 1813 | all facets are simplicial from apex
|
|---|
| 1814 | all facet->cycledone == False
|
|---|
| 1815 |
|
|---|
| 1816 | returns:
|
|---|
| 1817 | all newfacets merged into coplanar horizon facets
|
|---|
| 1818 | deleted vertices on qh.del_vertices
|
|---|
| 1819 | sets wasmerge if any merge
|
|---|
| 1820 |
|
|---|
| 1821 | see:
|
|---|
| 1822 | calls qh_mergecycle for multiple, same cycle facets
|
|---|
| 1823 |
|
|---|
| 1824 | design:
|
|---|
| 1825 | for each facet on facetlist
|
|---|
| 1826 | skip facets with duplicate ridges and normals
|
|---|
| 1827 | check that facet is in a samecycle (->mergehorizon)
|
|---|
| 1828 | if facet only member of samecycle
|
|---|
| 1829 | sets vertex->delridge for all vertices except apex
|
|---|
| 1830 | merge facet into horizon
|
|---|
| 1831 | else
|
|---|
| 1832 | mark all facets in samecycle
|
|---|
| 1833 | remove facets with duplicate ridges from samecycle
|
|---|
| 1834 | merge samecycle into horizon (deletes facets from facetlist)
|
|---|
| 1835 | */
|
|---|
| 1836 | void qh_mergecycle_all(facetT *facetlist, boolT *wasmerge) {
|
|---|
| 1837 | facetT *facet, *same, *prev, *horizon;
|
|---|
| 1838 | facetT *samecycle= NULL, *nextfacet, *nextsame;
|
|---|
| 1839 | vertexT *apex, *vertex, **vertexp;
|
|---|
| 1840 | int cycles=0, total=0, facets, nummerge;
|
|---|
| 1841 |
|
|---|
| 1842 | trace2((qh ferr, 2031, "qh_mergecycle_all: begin\n"));
|
|---|
| 1843 | for (facet= facetlist; facet && (nextfacet= facet->next); facet= nextfacet) {
|
|---|
| 1844 | if (facet->normal)
|
|---|
| 1845 | continue;
|
|---|
| 1846 | if (!facet->mergehorizon) {
|
|---|
| 1847 | qh_fprintf(qh ferr, 6225, "Qhull internal error (qh_mergecycle_all): f%d without normal\n", facet->id);
|
|---|
| 1848 | qh_errexit(qh_ERRqhull, facet, NULL);
|
|---|
| 1849 | }
|
|---|
| 1850 | horizon= SETfirstt_(facet->neighbors, facetT);
|
|---|
| 1851 | if (facet->f.samecycle == facet) {
|
|---|
| 1852 | zinc_(Zonehorizon);
|
|---|
| 1853 | /* merge distance done in qh_findhorizon */
|
|---|
| 1854 | apex= SETfirstt_(facet->vertices, vertexT);
|
|---|
| 1855 | FOREACHvertex_(facet->vertices) {
|
|---|
| 1856 | if (vertex != apex)
|
|---|
| 1857 | vertex->delridge= True;
|
|---|
| 1858 | }
|
|---|
| 1859 | horizon->f.newcycle= NULL;
|
|---|
| 1860 | qh_mergefacet(facet, horizon, NULL, NULL, qh_MERGEapex);
|
|---|
| 1861 | }else {
|
|---|
| 1862 | samecycle= facet;
|
|---|
| 1863 | facets= 0;
|
|---|
| 1864 | prev= facet;
|
|---|
| 1865 | for (same= facet->f.samecycle; same; /* FORALLsame_cycle_(facet) */
|
|---|
| 1866 | same= (same == facet ? NULL :nextsame)) { /* ends at facet */
|
|---|
| 1867 | nextsame= same->f.samecycle;
|
|---|
| 1868 | if (same->cycledone || same->visible)
|
|---|
| 1869 | qh_infiniteloop(same);
|
|---|
| 1870 | same->cycledone= True;
|
|---|
| 1871 | if (same->normal) {
|
|---|
| 1872 | prev->f.samecycle= same->f.samecycle; /* unlink ->mergeridge */
|
|---|
| 1873 | same->f.samecycle= NULL;
|
|---|
| 1874 | }else {
|
|---|
| 1875 | prev= same;
|
|---|
| 1876 | facets++;
|
|---|
| 1877 | }
|
|---|
| 1878 | }
|
|---|
| 1879 | while (nextfacet && nextfacet->cycledone) /* will delete samecycle */
|
|---|
| 1880 | nextfacet= nextfacet->next;
|
|---|
| 1881 | horizon->f.newcycle= NULL;
|
|---|
| 1882 | qh_mergecycle(samecycle, horizon);
|
|---|
| 1883 | nummerge= horizon->nummerge + facets;
|
|---|
| 1884 | if (nummerge > qh_MAXnummerge)
|
|---|
| 1885 | horizon->nummerge= qh_MAXnummerge;
|
|---|
| 1886 | else
|
|---|
| 1887 | horizon->nummerge= (short unsigned int)nummerge;
|
|---|
| 1888 | zzinc_(Zcyclehorizon);
|
|---|
| 1889 | total += facets;
|
|---|
| 1890 | zzadd_(Zcyclefacettot, facets);
|
|---|
| 1891 | zmax_(Zcyclefacetmax, facets);
|
|---|
| 1892 | }
|
|---|
| 1893 | cycles++;
|
|---|
| 1894 | }
|
|---|
| 1895 | if (cycles)
|
|---|
| 1896 | *wasmerge= True;
|
|---|
| 1897 | trace1((qh ferr, 1013, "qh_mergecycle_all: merged %d same cycles or facets into coplanar horizons\n", cycles));
|
|---|
| 1898 | } /* mergecycle_all */
|
|---|
| 1899 |
|
|---|
| 1900 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1901 | >-------------------------------</a><a name="mergecycle_facets">-</a>
|
|---|
| 1902 |
|
|---|
| 1903 | qh_mergecycle_facets( samecycle, newfacet )
|
|---|
| 1904 | finish merge of samecycle into newfacet
|
|---|
| 1905 |
|
|---|
| 1906 | returns:
|
|---|
| 1907 | samecycle prepended to visible_list for later deletion and partitioning
|
|---|
| 1908 | each facet->f.replace == newfacet
|
|---|
| 1909 |
|
|---|
| 1910 | newfacet moved to end of qh.facet_list
|
|---|
| 1911 | makes newfacet a newfacet (get's facet1->id if it was old)
|
|---|
| 1912 | sets newfacet->newmerge
|
|---|
| 1913 | clears newfacet->center (unless merging into a large facet)
|
|---|
| 1914 | clears newfacet->tested and ridge->tested for facet1
|
|---|
| 1915 |
|
|---|
| 1916 | adds neighboring facets to facet_mergeset if redundant or degenerate
|
|---|
| 1917 |
|
|---|
| 1918 | design:
|
|---|
| 1919 | make newfacet a new facet and set its flags
|
|---|
| 1920 | move samecycle facets to qh.visible_list for later deletion
|
|---|
| 1921 | unless newfacet is large
|
|---|
| 1922 | remove its centrum
|
|---|
| 1923 | */
|
|---|
| 1924 | void qh_mergecycle_facets(facetT *samecycle, facetT *newfacet) {
|
|---|
| 1925 | facetT *same, *next;
|
|---|
| 1926 |
|
|---|
| 1927 | trace4((qh ferr, 4030, "qh_mergecycle_facets: make newfacet new and samecycle deleted\n"));
|
|---|
| 1928 | qh_removefacet(newfacet); /* append as a newfacet to end of qh facet_list */
|
|---|
| 1929 | qh_appendfacet(newfacet);
|
|---|
| 1930 | newfacet->newfacet= True;
|
|---|
| 1931 | newfacet->simplicial= False;
|
|---|
| 1932 | newfacet->newmerge= True;
|
|---|
| 1933 |
|
|---|
| 1934 | for (same= samecycle->f.samecycle; same; same= (same == samecycle ? NULL : next)) {
|
|---|
| 1935 | next= same->f.samecycle; /* reused by willdelete */
|
|---|
| 1936 | qh_willdelete(same, newfacet);
|
|---|
| 1937 | }
|
|---|
| 1938 | if (newfacet->center
|
|---|
| 1939 | && qh_setsize(newfacet->vertices) <= qh hull_dim + qh_MAXnewcentrum) {
|
|---|
| 1940 | qh_memfree(newfacet->center, qh normal_size);
|
|---|
| 1941 | newfacet->center= NULL;
|
|---|
| 1942 | }
|
|---|
| 1943 | trace3((qh ferr, 3004, "qh_mergecycle_facets: merged facets from cycle f%d into f%d\n",
|
|---|
| 1944 | samecycle->id, newfacet->id));
|
|---|
| 1945 | } /* mergecycle_facets */
|
|---|
| 1946 |
|
|---|
| 1947 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 1948 | >-------------------------------</a><a name="mergecycle_neighbors">-</a>
|
|---|
| 1949 |
|
|---|
| 1950 | qh_mergecycle_neighbors( samecycle, newfacet )
|
|---|
| 1951 | add neighbors for samecycle facets to newfacet
|
|---|
| 1952 |
|
|---|
| 1953 | returns:
|
|---|
| 1954 | newfacet with updated neighbors and vice-versa
|
|---|
| 1955 | newfacet has ridges
|
|---|
| 1956 | all neighbors of newfacet marked with qh.visit_id
|
|---|
| 1957 | samecycle facets marked with qh.visit_id-1
|
|---|
| 1958 | ridges updated for simplicial neighbors of samecycle with a ridge
|
|---|
| 1959 |
|
|---|
| 1960 | notes:
|
|---|
| 1961 | assumes newfacet not in samecycle
|
|---|
| 1962 | usually, samecycle facets are new, simplicial facets without internal ridges
|
|---|
| 1963 | not so if horizon facet is coplanar to two different samecycles
|
|---|
| 1964 |
|
|---|
| 1965 | see:
|
|---|
| 1966 | qh_mergeneighbors()
|
|---|
| 1967 |
|
|---|
| 1968 | design:
|
|---|
| 1969 | check samecycle
|
|---|
| 1970 | delete neighbors from newfacet that are also in samecycle
|
|---|
| 1971 | for each neighbor of a facet in samecycle
|
|---|
| 1972 | if neighbor is simplicial
|
|---|
| 1973 | if first visit
|
|---|
| 1974 | move the neighbor relation to newfacet
|
|---|
| 1975 | update facet links for its ridges
|
|---|
| 1976 | else
|
|---|
| 1977 | make ridges for neighbor
|
|---|
| 1978 | remove samecycle reference
|
|---|
| 1979 | else
|
|---|
| 1980 | update neighbor sets
|
|---|
| 1981 | */
|
|---|
| 1982 | void qh_mergecycle_neighbors(facetT *samecycle, facetT *newfacet) {
|
|---|
| 1983 | facetT *same, *neighbor, **neighborp;
|
|---|
| 1984 | int delneighbors= 0, newneighbors= 0;
|
|---|
| 1985 | unsigned int samevisitid;
|
|---|
| 1986 | ridgeT *ridge, **ridgep;
|
|---|
| 1987 |
|
|---|
| 1988 | samevisitid= ++qh visit_id;
|
|---|
| 1989 | FORALLsame_cycle_(samecycle) {
|
|---|
| 1990 | if (same->visitid == samevisitid || same->visible)
|
|---|
| 1991 | qh_infiniteloop(samecycle);
|
|---|
| 1992 | same->visitid= samevisitid;
|
|---|
| 1993 | }
|
|---|
| 1994 | newfacet->visitid= ++qh visit_id;
|
|---|
| 1995 | trace4((qh ferr, 4031, "qh_mergecycle_neighbors: delete shared neighbors from newfacet\n"));
|
|---|
| 1996 | FOREACHneighbor_(newfacet) {
|
|---|
| 1997 | if (neighbor->visitid == samevisitid) {
|
|---|
| 1998 | SETref_(neighbor)= NULL; /* samecycle neighbors deleted */
|
|---|
| 1999 | delneighbors++;
|
|---|
| 2000 | }else
|
|---|
| 2001 | neighbor->visitid= qh visit_id;
|
|---|
| 2002 | }
|
|---|
| 2003 | qh_setcompact(newfacet->neighbors);
|
|---|
| 2004 |
|
|---|
| 2005 | trace4((qh ferr, 4032, "qh_mergecycle_neighbors: update neighbors\n"));
|
|---|
| 2006 | FORALLsame_cycle_(samecycle) {
|
|---|
| 2007 | FOREACHneighbor_(same) {
|
|---|
| 2008 | if (neighbor->visitid == samevisitid)
|
|---|
| 2009 | continue;
|
|---|
| 2010 | if (neighbor->simplicial) {
|
|---|
| 2011 | if (neighbor->visitid != qh visit_id) {
|
|---|
| 2012 | qh_setappend(&newfacet->neighbors, neighbor);
|
|---|
| 2013 | qh_setreplace(neighbor->neighbors, same, newfacet);
|
|---|
| 2014 | newneighbors++;
|
|---|
| 2015 | neighbor->visitid= qh visit_id;
|
|---|
| 2016 | FOREACHridge_(neighbor->ridges) { /* update ridge in case of qh_makeridges */
|
|---|
| 2017 | if (ridge->top == same) {
|
|---|
| 2018 | ridge->top= newfacet;
|
|---|
| 2019 | break;
|
|---|
| 2020 | }else if (ridge->bottom == same) {
|
|---|
| 2021 | ridge->bottom= newfacet;
|
|---|
| 2022 | break;
|
|---|
| 2023 | }
|
|---|
| 2024 | }
|
|---|
| 2025 | }else {
|
|---|
| 2026 | qh_makeridges(neighbor);
|
|---|
| 2027 | qh_setdel(neighbor->neighbors, same);
|
|---|
| 2028 | /* same can't be horizon facet for neighbor */
|
|---|
| 2029 | }
|
|---|
| 2030 | }else { /* non-simplicial neighbor */
|
|---|
| 2031 | qh_setdel(neighbor->neighbors, same);
|
|---|
| 2032 | if (neighbor->visitid != qh visit_id) {
|
|---|
| 2033 | qh_setappend(&neighbor->neighbors, newfacet);
|
|---|
| 2034 | qh_setappend(&newfacet->neighbors, neighbor);
|
|---|
| 2035 | neighbor->visitid= qh visit_id;
|
|---|
| 2036 | newneighbors++;
|
|---|
| 2037 | }
|
|---|
| 2038 | }
|
|---|
| 2039 | }
|
|---|
| 2040 | }
|
|---|
| 2041 | trace2((qh ferr, 2032, "qh_mergecycle_neighbors: deleted %d neighbors and added %d\n",
|
|---|
| 2042 | delneighbors, newneighbors));
|
|---|
| 2043 | } /* mergecycle_neighbors */
|
|---|
| 2044 |
|
|---|
| 2045 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2046 | >-------------------------------</a><a name="mergecycle_ridges">-</a>
|
|---|
| 2047 |
|
|---|
| 2048 | qh_mergecycle_ridges( samecycle, newfacet )
|
|---|
| 2049 | add ridges/neighbors for facets in samecycle to newfacet
|
|---|
| 2050 | all new/old neighbors of newfacet marked with qh.visit_id
|
|---|
| 2051 | facets in samecycle marked with qh.visit_id-1
|
|---|
| 2052 | newfacet marked with qh.visit_id
|
|---|
| 2053 |
|
|---|
| 2054 | returns:
|
|---|
| 2055 | newfacet has merged ridges
|
|---|
| 2056 |
|
|---|
| 2057 | notes:
|
|---|
| 2058 | ridge already updated for simplicial neighbors of samecycle with a ridge
|
|---|
| 2059 |
|
|---|
| 2060 | see:
|
|---|
| 2061 | qh_mergeridges()
|
|---|
| 2062 | qh_makeridges()
|
|---|
| 2063 |
|
|---|
| 2064 | design:
|
|---|
| 2065 | remove ridges between newfacet and samecycle
|
|---|
| 2066 | for each facet in samecycle
|
|---|
| 2067 | for each ridge in facet
|
|---|
| 2068 | update facet pointers in ridge
|
|---|
| 2069 | skip ridges processed in qh_mergecycle_neighors
|
|---|
| 2070 | free ridges between newfacet and samecycle
|
|---|
| 2071 | free ridges between facets of samecycle (on 2nd visit)
|
|---|
| 2072 | append remaining ridges to newfacet
|
|---|
| 2073 | if simpilicial facet
|
|---|
| 2074 | for each neighbor of facet
|
|---|
| 2075 | if simplicial facet
|
|---|
| 2076 | and not samecycle facet or newfacet
|
|---|
| 2077 | make ridge between neighbor and newfacet
|
|---|
| 2078 | */
|
|---|
| 2079 | void qh_mergecycle_ridges(facetT *samecycle, facetT *newfacet) {
|
|---|
| 2080 | facetT *same, *neighbor= NULL;
|
|---|
| 2081 | int numold=0, numnew=0;
|
|---|
| 2082 | int neighbor_i, neighbor_n;
|
|---|
| 2083 | unsigned int samevisitid;
|
|---|
| 2084 | ridgeT *ridge, **ridgep;
|
|---|
| 2085 | boolT toporient;
|
|---|
| 2086 | void **freelistp; /* used !qh_NOmem */
|
|---|
| 2087 |
|
|---|
| 2088 | trace4((qh ferr, 4033, "qh_mergecycle_ridges: delete shared ridges from newfacet\n"));
|
|---|
| 2089 | samevisitid= qh visit_id -1;
|
|---|
| 2090 | FOREACHridge_(newfacet->ridges) {
|
|---|
| 2091 | neighbor= otherfacet_(ridge, newfacet);
|
|---|
| 2092 | if (neighbor->visitid == samevisitid)
|
|---|
| 2093 | SETref_(ridge)= NULL; /* ridge free'd below */
|
|---|
| 2094 | }
|
|---|
| 2095 | qh_setcompact(newfacet->ridges);
|
|---|
| 2096 |
|
|---|
| 2097 | trace4((qh ferr, 4034, "qh_mergecycle_ridges: add ridges to newfacet\n"));
|
|---|
| 2098 | FORALLsame_cycle_(samecycle) {
|
|---|
| 2099 | FOREACHridge_(same->ridges) {
|
|---|
| 2100 | if (ridge->top == same) {
|
|---|
| 2101 | ridge->top= newfacet;
|
|---|
| 2102 | neighbor= ridge->bottom;
|
|---|
| 2103 | }else if (ridge->bottom == same) {
|
|---|
| 2104 | ridge->bottom= newfacet;
|
|---|
| 2105 | neighbor= ridge->top;
|
|---|
| 2106 | }else if (ridge->top == newfacet || ridge->bottom == newfacet) {
|
|---|
| 2107 | qh_setappend(&newfacet->ridges, ridge);
|
|---|
| 2108 | numold++; /* already set by qh_mergecycle_neighbors */
|
|---|
| 2109 | continue;
|
|---|
| 2110 | }else {
|
|---|
| 2111 | qh_fprintf(qh ferr, 6098, "qhull internal error (qh_mergecycle_ridges): bad ridge r%d\n", ridge->id);
|
|---|
| 2112 | qh_errexit(qh_ERRqhull, NULL, ridge);
|
|---|
| 2113 | }
|
|---|
| 2114 | if (neighbor == newfacet) {
|
|---|
| 2115 | qh_setfree(&(ridge->vertices));
|
|---|
| 2116 | qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
|
|---|
| 2117 | numold++;
|
|---|
| 2118 | }else if (neighbor->visitid == samevisitid) {
|
|---|
| 2119 | qh_setdel(neighbor->ridges, ridge);
|
|---|
| 2120 | qh_setfree(&(ridge->vertices));
|
|---|
| 2121 | qh_memfree_(ridge, (int)sizeof(ridgeT), freelistp);
|
|---|
| 2122 | numold++;
|
|---|
| 2123 | }else {
|
|---|
| 2124 | qh_setappend(&newfacet->ridges, ridge);
|
|---|
| 2125 | numold++;
|
|---|
| 2126 | }
|
|---|
| 2127 | }
|
|---|
| 2128 | if (same->ridges)
|
|---|
| 2129 | qh_settruncate(same->ridges, 0);
|
|---|
| 2130 | if (!same->simplicial)
|
|---|
| 2131 | continue;
|
|---|
| 2132 | FOREACHneighbor_i_(same) { /* note: !newfact->simplicial */
|
|---|
| 2133 | if (neighbor->visitid != samevisitid && neighbor->simplicial) {
|
|---|
| 2134 | ridge= qh_newridge();
|
|---|
| 2135 | ridge->vertices= qh_setnew_delnthsorted(same->vertices, qh hull_dim,
|
|---|
| 2136 | neighbor_i, 0);
|
|---|
| 2137 | toporient= same->toporient ^ (neighbor_i & 0x1);
|
|---|
| 2138 | if (toporient) {
|
|---|
| 2139 | ridge->top= newfacet;
|
|---|
| 2140 | ridge->bottom= neighbor;
|
|---|
| 2141 | }else {
|
|---|
| 2142 | ridge->top= neighbor;
|
|---|
| 2143 | ridge->bottom= newfacet;
|
|---|
| 2144 | }
|
|---|
| 2145 | qh_setappend(&(newfacet->ridges), ridge);
|
|---|
| 2146 | qh_setappend(&(neighbor->ridges), ridge);
|
|---|
| 2147 | numnew++;
|
|---|
| 2148 | }
|
|---|
| 2149 | }
|
|---|
| 2150 | }
|
|---|
| 2151 |
|
|---|
| 2152 | trace2((qh ferr, 2033, "qh_mergecycle_ridges: found %d old ridges and %d new ones\n",
|
|---|
| 2153 | numold, numnew));
|
|---|
| 2154 | } /* mergecycle_ridges */
|
|---|
| 2155 |
|
|---|
| 2156 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2157 | >-------------------------------</a><a name="mergecycle_vneighbors">-</a>
|
|---|
| 2158 |
|
|---|
| 2159 | qh_mergecycle_vneighbors( samecycle, newfacet )
|
|---|
| 2160 | create vertex neighbors for newfacet from vertices of facets in samecycle
|
|---|
| 2161 | samecycle marked with visitid == qh.visit_id - 1
|
|---|
| 2162 |
|
|---|
| 2163 | returns:
|
|---|
| 2164 | newfacet vertices with updated neighbors
|
|---|
| 2165 | marks newfacet with qh.visit_id-1
|
|---|
| 2166 | deletes vertices that are merged away
|
|---|
| 2167 | sets delridge on all vertices (faster here than in mergecycle_ridges)
|
|---|
| 2168 |
|
|---|
| 2169 | see:
|
|---|
| 2170 | qh_mergevertex_neighbors()
|
|---|
| 2171 |
|
|---|
| 2172 | design:
|
|---|
| 2173 | for each vertex of samecycle facet
|
|---|
| 2174 | set vertex->delridge
|
|---|
| 2175 | delete samecycle facets from vertex neighbors
|
|---|
| 2176 | append newfacet to vertex neighbors
|
|---|
| 2177 | if vertex only in newfacet
|
|---|
| 2178 | delete it from newfacet
|
|---|
| 2179 | add it to qh.del_vertices for later deletion
|
|---|
| 2180 | */
|
|---|
| 2181 | void qh_mergecycle_vneighbors(facetT *samecycle, facetT *newfacet) {
|
|---|
| 2182 | facetT *neighbor, **neighborp;
|
|---|
| 2183 | unsigned int mergeid;
|
|---|
| 2184 | vertexT *vertex, **vertexp, *apex;
|
|---|
| 2185 | setT *vertices;
|
|---|
| 2186 |
|
|---|
| 2187 | trace4((qh ferr, 4035, "qh_mergecycle_vneighbors: update vertex neighbors for newfacet\n"));
|
|---|
| 2188 | mergeid= qh visit_id - 1;
|
|---|
| 2189 | newfacet->visitid= mergeid;
|
|---|
| 2190 | vertices= qh_basevertices(samecycle); /* temp */
|
|---|
| 2191 | apex= SETfirstt_(samecycle->vertices, vertexT);
|
|---|
| 2192 | qh_setappend(&vertices, apex);
|
|---|
| 2193 | FOREACHvertex_(vertices) {
|
|---|
| 2194 | vertex->delridge= True;
|
|---|
| 2195 | FOREACHneighbor_(vertex) {
|
|---|
| 2196 | if (neighbor->visitid == mergeid)
|
|---|
| 2197 | SETref_(neighbor)= NULL;
|
|---|
| 2198 | }
|
|---|
| 2199 | qh_setcompact(vertex->neighbors);
|
|---|
| 2200 | qh_setappend(&vertex->neighbors, newfacet);
|
|---|
| 2201 | if (!SETsecond_(vertex->neighbors)) {
|
|---|
| 2202 | zinc_(Zcyclevertex);
|
|---|
| 2203 | trace2((qh ferr, 2034, "qh_mergecycle_vneighbors: deleted v%d when merging cycle f%d into f%d\n",
|
|---|
| 2204 | vertex->id, samecycle->id, newfacet->id));
|
|---|
| 2205 | qh_setdelsorted(newfacet->vertices, vertex);
|
|---|
| 2206 | vertex->deleted= True;
|
|---|
| 2207 | qh_setappend(&qh del_vertices, vertex);
|
|---|
| 2208 | }
|
|---|
| 2209 | }
|
|---|
| 2210 | qh_settempfree(&vertices);
|
|---|
| 2211 | trace3((qh ferr, 3005, "qh_mergecycle_vneighbors: merged vertices from cycle f%d into f%d\n",
|
|---|
| 2212 | samecycle->id, newfacet->id));
|
|---|
| 2213 | } /* mergecycle_vneighbors */
|
|---|
| 2214 |
|
|---|
| 2215 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2216 | >-------------------------------</a><a name="mergefacet">-</a>
|
|---|
| 2217 |
|
|---|
| 2218 | qh_mergefacet( facet1, facet2, mindist, maxdist, mergeapex )
|
|---|
| 2219 | merges facet1 into facet2
|
|---|
| 2220 | mergeapex==qh_MERGEapex if merging new facet into coplanar horizon
|
|---|
| 2221 |
|
|---|
| 2222 | returns:
|
|---|
| 2223 | qh.max_outside and qh.min_vertex updated
|
|---|
| 2224 | initializes vertex neighbors on first merge
|
|---|
| 2225 |
|
|---|
| 2226 | returns:
|
|---|
| 2227 | facet2 contains facet1's vertices, neighbors, and ridges
|
|---|
| 2228 | facet2 moved to end of qh.facet_list
|
|---|
| 2229 | makes facet2 a newfacet
|
|---|
| 2230 | sets facet2->newmerge set
|
|---|
| 2231 | clears facet2->center (unless merging into a large facet)
|
|---|
| 2232 | clears facet2->tested and ridge->tested for facet1
|
|---|
| 2233 |
|
|---|
| 2234 | facet1 prepended to visible_list for later deletion and partitioning
|
|---|
| 2235 | facet1->f.replace == facet2
|
|---|
| 2236 |
|
|---|
| 2237 | adds neighboring facets to facet_mergeset if redundant or degenerate
|
|---|
| 2238 |
|
|---|
| 2239 | notes:
|
|---|
| 2240 | mindist/maxdist may be NULL (only if both NULL)
|
|---|
| 2241 | traces merge if fmax_(maxdist,-mindist) > TRACEdist
|
|---|
| 2242 |
|
|---|
| 2243 | see:
|
|---|
| 2244 | qh_mergecycle()
|
|---|
| 2245 |
|
|---|
| 2246 | design:
|
|---|
| 2247 | trace merge and check for degenerate simplex
|
|---|
| 2248 | make ridges for both facets
|
|---|
| 2249 | update qh.max_outside, qh.max_vertex, qh.min_vertex
|
|---|
| 2250 | update facet2->maxoutside and keepcentrum
|
|---|
| 2251 | update facet2->nummerge
|
|---|
| 2252 | update tested flags for facet2
|
|---|
| 2253 | if facet1 is simplicial
|
|---|
| 2254 | merge facet1 into facet2
|
|---|
| 2255 | else
|
|---|
| 2256 | merge facet1's neighbors into facet2
|
|---|
| 2257 | merge facet1's ridges into facet2
|
|---|
| 2258 | merge facet1's vertices into facet2
|
|---|
| 2259 | merge facet1's vertex neighbors into facet2
|
|---|
| 2260 | add facet2's vertices to qh.new_vertexlist
|
|---|
| 2261 | unless qh_MERGEapex
|
|---|
| 2262 | test facet2 for degenerate or redundant neighbors
|
|---|
| 2263 | move facet1 to qh.visible_list for later deletion
|
|---|
| 2264 | move facet2 to end of qh.newfacet_list
|
|---|
| 2265 | */
|
|---|
| 2266 | void qh_mergefacet(facetT *facet1, facetT *facet2, realT *mindist, realT *maxdist, boolT mergeapex) {
|
|---|
| 2267 | boolT traceonce= False;
|
|---|
| 2268 | vertexT *vertex, **vertexp;
|
|---|
| 2269 | int tracerestore=0, nummerge;
|
|---|
| 2270 |
|
|---|
| 2271 | if (facet1->tricoplanar || facet2->tricoplanar) {
|
|---|
| 2272 | if (!qh TRInormals) {
|
|---|
| 2273 | qh_fprintf(qh ferr, 6226, "Qhull internal error (qh_mergefacet): does not work for tricoplanar facets. Use option 'Q11'\n");
|
|---|
| 2274 | qh_errexit2 (qh_ERRqhull, facet1, facet2);
|
|---|
| 2275 | }
|
|---|
| 2276 | if (facet2->tricoplanar) {
|
|---|
| 2277 | facet2->tricoplanar= False;
|
|---|
| 2278 | facet2->keepcentrum= False;
|
|---|
| 2279 | }
|
|---|
| 2280 | }
|
|---|
| 2281 | zzinc_(Ztotmerge);
|
|---|
| 2282 | if (qh REPORTfreq2 && qh POSTmerging) {
|
|---|
| 2283 | if (zzval_(Ztotmerge) > qh mergereport + qh REPORTfreq2)
|
|---|
| 2284 | qh_tracemerging();
|
|---|
| 2285 | }
|
|---|
| 2286 | #ifndef qh_NOtrace
|
|---|
| 2287 | if (qh build_cnt >= qh RERUN) {
|
|---|
| 2288 | if (mindist && (-*mindist > qh TRACEdist || *maxdist > qh TRACEdist)) {
|
|---|
| 2289 | tracerestore= 0;
|
|---|
| 2290 | qh IStracing= qh TRACElevel;
|
|---|
| 2291 | traceonce= True;
|
|---|
| 2292 | qh_fprintf(qh ferr, 8075, "qh_mergefacet: ========= trace wide merge #%d(%2.2g) for f%d into f%d, last point was p%d\n", zzval_(Ztotmerge),
|
|---|
| 2293 | fmax_(-*mindist, *maxdist), facet1->id, facet2->id, qh furthest_id);
|
|---|
| 2294 | }else if (facet1 == qh tracefacet || facet2 == qh tracefacet) {
|
|---|
| 2295 | tracerestore= qh IStracing;
|
|---|
| 2296 | qh IStracing= 4;
|
|---|
| 2297 | traceonce= True;
|
|---|
| 2298 | qh_fprintf(qh ferr, 8076, "qh_mergefacet: ========= trace merge #%d involving f%d, furthest is p%d\n",
|
|---|
| 2299 | zzval_(Ztotmerge), qh tracefacet_id, qh furthest_id);
|
|---|
| 2300 | }
|
|---|
| 2301 | }
|
|---|
| 2302 | if (qh IStracing >= 2) {
|
|---|
| 2303 | realT mergemin= -2;
|
|---|
| 2304 | realT mergemax= -2;
|
|---|
| 2305 |
|
|---|
| 2306 | if (mindist) {
|
|---|
| 2307 | mergemin= *mindist;
|
|---|
| 2308 | mergemax= *maxdist;
|
|---|
| 2309 | }
|
|---|
| 2310 | qh_fprintf(qh ferr, 8077, "qh_mergefacet: #%d merge f%d into f%d, mindist= %2.2g, maxdist= %2.2g\n",
|
|---|
| 2311 | zzval_(Ztotmerge), facet1->id, facet2->id, mergemin, mergemax);
|
|---|
| 2312 | }
|
|---|
| 2313 | #endif /* !qh_NOtrace */
|
|---|
| 2314 | if (facet1 == facet2 || facet1->visible || facet2->visible) {
|
|---|
| 2315 | qh_fprintf(qh ferr, 6099, "qhull internal error (qh_mergefacet): either f%d and f%d are the same or one is a visible facet\n",
|
|---|
| 2316 | facet1->id, facet2->id);
|
|---|
| 2317 | qh_errexit2 (qh_ERRqhull, facet1, facet2);
|
|---|
| 2318 | }
|
|---|
| 2319 | if (qh num_facets - qh num_visible <= qh hull_dim + 1) {
|
|---|
| 2320 | qh_fprintf(qh ferr, 6227, "\n\
|
|---|
| 2321 | qhull precision error: Only %d facets remain. Can not merge another\n\
|
|---|
| 2322 | pair. The input is too degenerate or the convexity constraints are\n\
|
|---|
| 2323 | too strong.\n", qh hull_dim+1);
|
|---|
| 2324 | if (qh hull_dim >= 5 && !qh MERGEexact)
|
|---|
| 2325 | qh_fprintf(qh ferr, 8079, "Option 'Qx' may avoid this problem.\n");
|
|---|
| 2326 | qh_errexit(qh_ERRprec, NULL, NULL);
|
|---|
| 2327 | }
|
|---|
| 2328 | if (!qh VERTEXneighbors)
|
|---|
| 2329 | qh_vertexneighbors();
|
|---|
| 2330 | qh_makeridges(facet1);
|
|---|
| 2331 | qh_makeridges(facet2);
|
|---|
| 2332 | if (qh IStracing >=4)
|
|---|
| 2333 | qh_errprint("MERGING", facet1, facet2, NULL, NULL);
|
|---|
| 2334 | if (mindist) {
|
|---|
| 2335 | maximize_(qh max_outside, *maxdist);
|
|---|
| 2336 | maximize_(qh max_vertex, *maxdist);
|
|---|
| 2337 | #if qh_MAXoutside
|
|---|
| 2338 | maximize_(facet2->maxoutside, *maxdist);
|
|---|
| 2339 | #endif
|
|---|
| 2340 | minimize_(qh min_vertex, *mindist);
|
|---|
| 2341 | if (!facet2->keepcentrum
|
|---|
| 2342 | && (*maxdist > qh WIDEfacet || *mindist < -qh WIDEfacet)) {
|
|---|
| 2343 | facet2->keepcentrum= True;
|
|---|
| 2344 | zinc_(Zwidefacet);
|
|---|
| 2345 | }
|
|---|
| 2346 | }
|
|---|
| 2347 | nummerge= facet1->nummerge + facet2->nummerge + 1;
|
|---|
| 2348 | if (nummerge >= qh_MAXnummerge)
|
|---|
| 2349 | facet2->nummerge= qh_MAXnummerge;
|
|---|
| 2350 | else
|
|---|
| 2351 | facet2->nummerge= (short unsigned int)nummerge;
|
|---|
| 2352 | facet2->newmerge= True;
|
|---|
| 2353 | facet2->dupridge= False;
|
|---|
| 2354 | qh_updatetested (facet1, facet2);
|
|---|
| 2355 | if (qh hull_dim > 2 && qh_setsize(facet1->vertices) == qh hull_dim)
|
|---|
| 2356 | qh_mergesimplex(facet1, facet2, mergeapex);
|
|---|
| 2357 | else {
|
|---|
| 2358 | qh vertex_visit++;
|
|---|
| 2359 | FOREACHvertex_(facet2->vertices)
|
|---|
| 2360 | vertex->visitid= qh vertex_visit;
|
|---|
| 2361 | if (qh hull_dim == 2)
|
|---|
| 2362 | qh_mergefacet2d(facet1, facet2);
|
|---|
| 2363 | else {
|
|---|
| 2364 | qh_mergeneighbors(facet1, facet2);
|
|---|
| 2365 | qh_mergevertices(facet1->vertices, &facet2->vertices);
|
|---|
| 2366 | }
|
|---|
| 2367 | qh_mergeridges(facet1, facet2);
|
|---|
| 2368 | qh_mergevertex_neighbors(facet1, facet2);
|
|---|
| 2369 | if (!facet2->newfacet)
|
|---|
| 2370 | qh_newvertices(facet2->vertices);
|
|---|
| 2371 | }
|
|---|
| 2372 | if (!mergeapex)
|
|---|
| 2373 | qh_degen_redundant_neighbors(facet2, facet1);
|
|---|
| 2374 | if (facet2->coplanar || !facet2->newfacet) {
|
|---|
| 2375 | zinc_(Zmergeintohorizon);
|
|---|
| 2376 | }else if (!facet1->newfacet && facet2->newfacet) {
|
|---|
| 2377 | zinc_(Zmergehorizon);
|
|---|
| 2378 | }else {
|
|---|
| 2379 | zinc_(Zmergenew);
|
|---|
| 2380 | }
|
|---|
| 2381 | qh_willdelete(facet1, facet2);
|
|---|
| 2382 | qh_removefacet(facet2); /* append as a newfacet to end of qh facet_list */
|
|---|
| 2383 | qh_appendfacet(facet2);
|
|---|
| 2384 | facet2->newfacet= True;
|
|---|
| 2385 | facet2->tested= False;
|
|---|
| 2386 | qh_tracemerge(facet1, facet2);
|
|---|
| 2387 | if (traceonce) {
|
|---|
| 2388 | qh_fprintf(qh ferr, 8080, "qh_mergefacet: end of wide tracing\n");
|
|---|
| 2389 | qh IStracing= tracerestore;
|
|---|
| 2390 | }
|
|---|
| 2391 | } /* mergefacet */
|
|---|
| 2392 |
|
|---|
| 2393 |
|
|---|
| 2394 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2395 | >-------------------------------</a><a name="mergefacet2d">-</a>
|
|---|
| 2396 |
|
|---|
| 2397 | qh_mergefacet2d( facet1, facet2 )
|
|---|
| 2398 | in 2d, merges neighbors and vertices of facet1 into facet2
|
|---|
| 2399 |
|
|---|
| 2400 | returns:
|
|---|
| 2401 | build ridges for neighbors if necessary
|
|---|
| 2402 | facet2 looks like a simplicial facet except for centrum, ridges
|
|---|
| 2403 | neighbors are opposite the corresponding vertex
|
|---|
| 2404 | maintains orientation of facet2
|
|---|
| 2405 |
|
|---|
| 2406 | notes:
|
|---|
| 2407 | qh_mergefacet() retains non-simplicial structures
|
|---|
| 2408 | they are not needed in 2d, but later routines may use them
|
|---|
| 2409 | preserves qh.vertex_visit for qh_mergevertex_neighbors()
|
|---|
| 2410 |
|
|---|
| 2411 | design:
|
|---|
| 2412 | get vertices and neighbors
|
|---|
| 2413 | determine new vertices and neighbors
|
|---|
| 2414 | set new vertices and neighbors and adjust orientation
|
|---|
| 2415 | make ridges for new neighbor if needed
|
|---|
| 2416 | */
|
|---|
| 2417 | void qh_mergefacet2d(facetT *facet1, facetT *facet2) {
|
|---|
| 2418 | vertexT *vertex1A, *vertex1B, *vertex2A, *vertex2B, *vertexA, *vertexB;
|
|---|
| 2419 | facetT *neighbor1A, *neighbor1B, *neighbor2A, *neighbor2B, *neighborA, *neighborB;
|
|---|
| 2420 |
|
|---|
| 2421 | vertex1A= SETfirstt_(facet1->vertices, vertexT);
|
|---|
| 2422 | vertex1B= SETsecondt_(facet1->vertices, vertexT);
|
|---|
| 2423 | vertex2A= SETfirstt_(facet2->vertices, vertexT);
|
|---|
| 2424 | vertex2B= SETsecondt_(facet2->vertices, vertexT);
|
|---|
| 2425 | neighbor1A= SETfirstt_(facet1->neighbors, facetT);
|
|---|
| 2426 | neighbor1B= SETsecondt_(facet1->neighbors, facetT);
|
|---|
| 2427 | neighbor2A= SETfirstt_(facet2->neighbors, facetT);
|
|---|
| 2428 | neighbor2B= SETsecondt_(facet2->neighbors, facetT);
|
|---|
| 2429 | if (vertex1A == vertex2A) {
|
|---|
| 2430 | vertexA= vertex1B;
|
|---|
| 2431 | vertexB= vertex2B;
|
|---|
| 2432 | neighborA= neighbor2A;
|
|---|
| 2433 | neighborB= neighbor1A;
|
|---|
| 2434 | }else if (vertex1A == vertex2B) {
|
|---|
| 2435 | vertexA= vertex1B;
|
|---|
| 2436 | vertexB= vertex2A;
|
|---|
| 2437 | neighborA= neighbor2B;
|
|---|
| 2438 | neighborB= neighbor1A;
|
|---|
| 2439 | }else if (vertex1B == vertex2A) {
|
|---|
| 2440 | vertexA= vertex1A;
|
|---|
| 2441 | vertexB= vertex2B;
|
|---|
| 2442 | neighborA= neighbor2A;
|
|---|
| 2443 | neighborB= neighbor1B;
|
|---|
| 2444 | }else { /* 1B == 2B */
|
|---|
| 2445 | vertexA= vertex1A;
|
|---|
| 2446 | vertexB= vertex2A;
|
|---|
| 2447 | neighborA= neighbor2B;
|
|---|
| 2448 | neighborB= neighbor1B;
|
|---|
| 2449 | }
|
|---|
| 2450 | /* vertexB always from facet2, neighborB always from facet1 */
|
|---|
| 2451 | if (vertexA->id > vertexB->id) {
|
|---|
| 2452 | SETfirst_(facet2->vertices)= vertexA;
|
|---|
| 2453 | SETsecond_(facet2->vertices)= vertexB;
|
|---|
| 2454 | if (vertexB == vertex2A)
|
|---|
| 2455 | facet2->toporient= !facet2->toporient;
|
|---|
| 2456 | SETfirst_(facet2->neighbors)= neighborA;
|
|---|
| 2457 | SETsecond_(facet2->neighbors)= neighborB;
|
|---|
| 2458 | }else {
|
|---|
| 2459 | SETfirst_(facet2->vertices)= vertexB;
|
|---|
| 2460 | SETsecond_(facet2->vertices)= vertexA;
|
|---|
| 2461 | if (vertexB == vertex2B)
|
|---|
| 2462 | facet2->toporient= !facet2->toporient;
|
|---|
| 2463 | SETfirst_(facet2->neighbors)= neighborB;
|
|---|
| 2464 | SETsecond_(facet2->neighbors)= neighborA;
|
|---|
| 2465 | }
|
|---|
| 2466 | qh_makeridges(neighborB);
|
|---|
| 2467 | qh_setreplace(neighborB->neighbors, facet1, facet2);
|
|---|
| 2468 | trace4((qh ferr, 4036, "qh_mergefacet2d: merged v%d and neighbor f%d of f%d into f%d\n",
|
|---|
| 2469 | vertexA->id, neighborB->id, facet1->id, facet2->id));
|
|---|
| 2470 | } /* mergefacet2d */
|
|---|
| 2471 |
|
|---|
| 2472 |
|
|---|
| 2473 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2474 | >-------------------------------</a><a name="mergeneighbors">-</a>
|
|---|
| 2475 |
|
|---|
| 2476 | qh_mergeneighbors( facet1, facet2 )
|
|---|
| 2477 | merges the neighbors of facet1 into facet2
|
|---|
| 2478 |
|
|---|
| 2479 | see:
|
|---|
| 2480 | qh_mergecycle_neighbors()
|
|---|
| 2481 |
|
|---|
| 2482 | design:
|
|---|
| 2483 | for each neighbor of facet1
|
|---|
| 2484 | if neighbor is also a neighbor of facet2
|
|---|
| 2485 | if neighbor is simpilicial
|
|---|
| 2486 | make ridges for later deletion as a degenerate facet
|
|---|
| 2487 | update its neighbor set
|
|---|
| 2488 | else
|
|---|
| 2489 | move the neighbor relation to facet2
|
|---|
| 2490 | remove the neighbor relation for facet1 and facet2
|
|---|
| 2491 | */
|
|---|
| 2492 | void qh_mergeneighbors(facetT *facet1, facetT *facet2) {
|
|---|
| 2493 | facetT *neighbor, **neighborp;
|
|---|
| 2494 |
|
|---|
| 2495 | trace4((qh ferr, 4037, "qh_mergeneighbors: merge neighbors of f%d and f%d\n",
|
|---|
| 2496 | facet1->id, facet2->id));
|
|---|
| 2497 | qh visit_id++;
|
|---|
| 2498 | FOREACHneighbor_(facet2) {
|
|---|
| 2499 | neighbor->visitid= qh visit_id;
|
|---|
| 2500 | }
|
|---|
| 2501 | FOREACHneighbor_(facet1) {
|
|---|
| 2502 | if (neighbor->visitid == qh visit_id) {
|
|---|
| 2503 | if (neighbor->simplicial) /* is degen, needs ridges */
|
|---|
| 2504 | qh_makeridges(neighbor);
|
|---|
| 2505 | if (SETfirstt_(neighbor->neighbors, facetT) != facet1) /*keep newfacet->horizon*/
|
|---|
| 2506 | qh_setdel(neighbor->neighbors, facet1);
|
|---|
| 2507 | else {
|
|---|
| 2508 | qh_setdel(neighbor->neighbors, facet2);
|
|---|
| 2509 | qh_setreplace(neighbor->neighbors, facet1, facet2);
|
|---|
| 2510 | }
|
|---|
| 2511 | }else if (neighbor != facet2) {
|
|---|
| 2512 | qh_setappend(&(facet2->neighbors), neighbor);
|
|---|
| 2513 | qh_setreplace(neighbor->neighbors, facet1, facet2);
|
|---|
| 2514 | }
|
|---|
| 2515 | }
|
|---|
| 2516 | qh_setdel(facet1->neighbors, facet2); /* here for makeridges */
|
|---|
| 2517 | qh_setdel(facet2->neighbors, facet1);
|
|---|
| 2518 | } /* mergeneighbors */
|
|---|
| 2519 |
|
|---|
| 2520 |
|
|---|
| 2521 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2522 | >-------------------------------</a><a name="mergeridges">-</a>
|
|---|
| 2523 |
|
|---|
| 2524 | qh_mergeridges( facet1, facet2 )
|
|---|
| 2525 | merges the ridge set of facet1 into facet2
|
|---|
| 2526 |
|
|---|
| 2527 | returns:
|
|---|
| 2528 | may delete all ridges for a vertex
|
|---|
| 2529 | sets vertex->delridge on deleted ridges
|
|---|
| 2530 |
|
|---|
| 2531 | see:
|
|---|
| 2532 | qh_mergecycle_ridges()
|
|---|
| 2533 |
|
|---|
| 2534 | design:
|
|---|
| 2535 | delete ridges between facet1 and facet2
|
|---|
| 2536 | mark (delridge) vertices on these ridges for later testing
|
|---|
| 2537 | for each remaining ridge
|
|---|
| 2538 | rename facet1 to facet2
|
|---|
| 2539 | */
|
|---|
| 2540 | void qh_mergeridges(facetT *facet1, facetT *facet2) {
|
|---|
| 2541 | ridgeT *ridge, **ridgep;
|
|---|
| 2542 | vertexT *vertex, **vertexp;
|
|---|
| 2543 |
|
|---|
| 2544 | trace4((qh ferr, 4038, "qh_mergeridges: merge ridges of f%d and f%d\n",
|
|---|
| 2545 | facet1->id, facet2->id));
|
|---|
| 2546 | FOREACHridge_(facet2->ridges) {
|
|---|
| 2547 | if ((ridge->top == facet1) || (ridge->bottom == facet1)) {
|
|---|
| 2548 | FOREACHvertex_(ridge->vertices)
|
|---|
| 2549 | vertex->delridge= True;
|
|---|
| 2550 | qh_delridge(ridge); /* expensive in high-d, could rebuild */
|
|---|
| 2551 | ridgep--; /*repeat*/
|
|---|
| 2552 | }
|
|---|
| 2553 | }
|
|---|
| 2554 | FOREACHridge_(facet1->ridges) {
|
|---|
| 2555 | if (ridge->top == facet1)
|
|---|
| 2556 | ridge->top= facet2;
|
|---|
| 2557 | else
|
|---|
| 2558 | ridge->bottom= facet2;
|
|---|
| 2559 | qh_setappend(&(facet2->ridges), ridge);
|
|---|
| 2560 | }
|
|---|
| 2561 | } /* mergeridges */
|
|---|
| 2562 |
|
|---|
| 2563 |
|
|---|
| 2564 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2565 | >-------------------------------</a><a name="mergesimplex">-</a>
|
|---|
| 2566 |
|
|---|
| 2567 | qh_mergesimplex( facet1, facet2, mergeapex )
|
|---|
| 2568 | merge simplicial facet1 into facet2
|
|---|
| 2569 | mergeapex==qh_MERGEapex if merging samecycle into horizon facet
|
|---|
| 2570 | vertex id is latest (most recently created)
|
|---|
| 2571 | facet1 may be contained in facet2
|
|---|
| 2572 | ridges exist for both facets
|
|---|
| 2573 |
|
|---|
| 2574 | returns:
|
|---|
| 2575 | facet2 with updated vertices, ridges, neighbors
|
|---|
| 2576 | updated neighbors for facet1's vertices
|
|---|
| 2577 | facet1 not deleted
|
|---|
| 2578 | sets vertex->delridge on deleted ridges
|
|---|
| 2579 |
|
|---|
| 2580 | notes:
|
|---|
| 2581 | special case code since this is the most common merge
|
|---|
| 2582 | called from qh_mergefacet()
|
|---|
| 2583 |
|
|---|
| 2584 | design:
|
|---|
| 2585 | if qh_MERGEapex
|
|---|
| 2586 | add vertices of facet2 to qh.new_vertexlist if necessary
|
|---|
| 2587 | add apex to facet2
|
|---|
| 2588 | else
|
|---|
| 2589 | for each ridge between facet1 and facet2
|
|---|
| 2590 | set vertex->delridge
|
|---|
| 2591 | determine the apex for facet1 (i.e., vertex to be merged)
|
|---|
| 2592 | unless apex already in facet2
|
|---|
| 2593 | insert apex into vertices for facet2
|
|---|
| 2594 | add vertices of facet2 to qh.new_vertexlist if necessary
|
|---|
| 2595 | add apex to qh.new_vertexlist if necessary
|
|---|
| 2596 | for each vertex of facet1
|
|---|
| 2597 | if apex
|
|---|
| 2598 | rename facet1 to facet2 in its vertex neighbors
|
|---|
| 2599 | else
|
|---|
| 2600 | delete facet1 from vertex neighors
|
|---|
| 2601 | if only in facet2
|
|---|
| 2602 | add vertex to qh.del_vertices for later deletion
|
|---|
| 2603 | for each ridge of facet1
|
|---|
| 2604 | delete ridges between facet1 and facet2
|
|---|
| 2605 | append other ridges to facet2 after renaming facet to facet2
|
|---|
| 2606 | */
|
|---|
| 2607 | void qh_mergesimplex(facetT *facet1, facetT *facet2, boolT mergeapex) {
|
|---|
| 2608 | vertexT *vertex, **vertexp, *apex;
|
|---|
| 2609 | ridgeT *ridge, **ridgep;
|
|---|
| 2610 | boolT issubset= False;
|
|---|
| 2611 | int vertex_i= -1, vertex_n;
|
|---|
| 2612 | facetT *neighbor, **neighborp, *otherfacet;
|
|---|
| 2613 |
|
|---|
| 2614 | if (mergeapex) {
|
|---|
| 2615 | if (!facet2->newfacet)
|
|---|
| 2616 | qh_newvertices(facet2->vertices); /* apex is new */
|
|---|
| 2617 | apex= SETfirstt_(facet1->vertices, vertexT);
|
|---|
| 2618 | if (SETfirstt_(facet2->vertices, vertexT) != apex)
|
|---|
| 2619 | qh_setaddnth(&facet2->vertices, 0, apex); /* apex has last id */
|
|---|
| 2620 | else
|
|---|
| 2621 | issubset= True;
|
|---|
| 2622 | }else {
|
|---|
| 2623 | zinc_(Zmergesimplex);
|
|---|
| 2624 | FOREACHvertex_(facet1->vertices)
|
|---|
| 2625 | vertex->seen= False;
|
|---|
| 2626 | FOREACHridge_(facet1->ridges) {
|
|---|
| 2627 | if (otherfacet_(ridge, facet1) == facet2) {
|
|---|
| 2628 | FOREACHvertex_(ridge->vertices) {
|
|---|
| 2629 | vertex->seen= True;
|
|---|
| 2630 | vertex->delridge= True;
|
|---|
| 2631 | }
|
|---|
| 2632 | break;
|
|---|
| 2633 | }
|
|---|
| 2634 | }
|
|---|
| 2635 | FOREACHvertex_(facet1->vertices) {
|
|---|
| 2636 | if (!vertex->seen)
|
|---|
| 2637 | break; /* must occur */
|
|---|
| 2638 | }
|
|---|
| 2639 | apex= vertex;
|
|---|
| 2640 | trace4((qh ferr, 4039, "qh_mergesimplex: merge apex v%d of f%d into facet f%d\n",
|
|---|
| 2641 | apex->id, facet1->id, facet2->id));
|
|---|
| 2642 | FOREACHvertex_i_(facet2->vertices) {
|
|---|
| 2643 | if (vertex->id < apex->id) {
|
|---|
| 2644 | break;
|
|---|
| 2645 | }else if (vertex->id == apex->id) {
|
|---|
| 2646 | issubset= True;
|
|---|
| 2647 | break;
|
|---|
| 2648 | }
|
|---|
| 2649 | }
|
|---|
| 2650 | if (!issubset)
|
|---|
| 2651 | qh_setaddnth(&facet2->vertices, vertex_i, apex);
|
|---|
| 2652 | if (!facet2->newfacet)
|
|---|
| 2653 | qh_newvertices(facet2->vertices);
|
|---|
| 2654 | else if (!apex->newlist) {
|
|---|
| 2655 | qh_removevertex(apex);
|
|---|
| 2656 | qh_appendvertex(apex);
|
|---|
| 2657 | }
|
|---|
| 2658 | }
|
|---|
| 2659 | trace4((qh ferr, 4040, "qh_mergesimplex: update vertex neighbors of f%d\n",
|
|---|
| 2660 | facet1->id));
|
|---|
| 2661 | FOREACHvertex_(facet1->vertices) {
|
|---|
| 2662 | if (vertex == apex && !issubset)
|
|---|
| 2663 | qh_setreplace(vertex->neighbors, facet1, facet2);
|
|---|
| 2664 | else {
|
|---|
| 2665 | qh_setdel(vertex->neighbors, facet1);
|
|---|
| 2666 | if (!SETsecond_(vertex->neighbors))
|
|---|
| 2667 | qh_mergevertex_del(vertex, facet1, facet2);
|
|---|
| 2668 | }
|
|---|
| 2669 | }
|
|---|
| 2670 | trace4((qh ferr, 4041, "qh_mergesimplex: merge ridges and neighbors of f%d into f%d\n",
|
|---|
| 2671 | facet1->id, facet2->id));
|
|---|
| 2672 | qh visit_id++;
|
|---|
| 2673 | FOREACHneighbor_(facet2)
|
|---|
| 2674 | neighbor->visitid= qh visit_id;
|
|---|
| 2675 | FOREACHridge_(facet1->ridges) {
|
|---|
| 2676 | otherfacet= otherfacet_(ridge, facet1);
|
|---|
| 2677 | if (otherfacet == facet2) {
|
|---|
| 2678 | qh_setdel(facet2->ridges, ridge);
|
|---|
| 2679 | qh_setfree(&(ridge->vertices));
|
|---|
| 2680 | qh_memfree(ridge, (int)sizeof(ridgeT));
|
|---|
| 2681 | qh_setdel(facet2->neighbors, facet1);
|
|---|
| 2682 | }else {
|
|---|
| 2683 | qh_setappend(&facet2->ridges, ridge);
|
|---|
| 2684 | if (otherfacet->visitid != qh visit_id) {
|
|---|
| 2685 | qh_setappend(&facet2->neighbors, otherfacet);
|
|---|
| 2686 | qh_setreplace(otherfacet->neighbors, facet1, facet2);
|
|---|
| 2687 | otherfacet->visitid= qh visit_id;
|
|---|
| 2688 | }else {
|
|---|
| 2689 | if (otherfacet->simplicial) /* is degen, needs ridges */
|
|---|
| 2690 | qh_makeridges(otherfacet);
|
|---|
| 2691 | if (SETfirstt_(otherfacet->neighbors, facetT) != facet1)
|
|---|
| 2692 | qh_setdel(otherfacet->neighbors, facet1);
|
|---|
| 2693 | else { /*keep newfacet->neighbors->horizon*/
|
|---|
| 2694 | qh_setdel(otherfacet->neighbors, facet2);
|
|---|
| 2695 | qh_setreplace(otherfacet->neighbors, facet1, facet2);
|
|---|
| 2696 | }
|
|---|
| 2697 | }
|
|---|
| 2698 | if (ridge->top == facet1) /* wait until after qh_makeridges */
|
|---|
| 2699 | ridge->top= facet2;
|
|---|
| 2700 | else
|
|---|
| 2701 | ridge->bottom= facet2;
|
|---|
| 2702 | }
|
|---|
| 2703 | }
|
|---|
| 2704 | SETfirst_(facet1->ridges)= NULL; /* it will be deleted */
|
|---|
| 2705 | trace3((qh ferr, 3006, "qh_mergesimplex: merged simplex f%d apex v%d into facet f%d\n",
|
|---|
| 2706 | facet1->id, getid_(apex), facet2->id));
|
|---|
| 2707 | } /* mergesimplex */
|
|---|
| 2708 |
|
|---|
| 2709 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2710 | >-------------------------------</a><a name="mergevertex_del">-</a>
|
|---|
| 2711 |
|
|---|
| 2712 | qh_mergevertex_del( vertex, facet1, facet2 )
|
|---|
| 2713 | delete a vertex because of merging facet1 into facet2
|
|---|
| 2714 |
|
|---|
| 2715 | returns:
|
|---|
| 2716 | deletes vertex from facet2
|
|---|
| 2717 | adds vertex to qh.del_vertices for later deletion
|
|---|
| 2718 | */
|
|---|
| 2719 | void qh_mergevertex_del(vertexT *vertex, facetT *facet1, facetT *facet2) {
|
|---|
| 2720 |
|
|---|
| 2721 | zinc_(Zmergevertex);
|
|---|
| 2722 | trace2((qh ferr, 2035, "qh_mergevertex_del: deleted v%d when merging f%d into f%d\n",
|
|---|
| 2723 | vertex->id, facet1->id, facet2->id));
|
|---|
| 2724 | qh_setdelsorted(facet2->vertices, vertex);
|
|---|
| 2725 | vertex->deleted= True;
|
|---|
| 2726 | qh_setappend(&qh del_vertices, vertex);
|
|---|
| 2727 | } /* mergevertex_del */
|
|---|
| 2728 |
|
|---|
| 2729 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2730 | >-------------------------------</a><a name="mergevertex_neighbors">-</a>
|
|---|
| 2731 |
|
|---|
| 2732 | qh_mergevertex_neighbors( facet1, facet2 )
|
|---|
| 2733 | merge the vertex neighbors of facet1 to facet2
|
|---|
| 2734 |
|
|---|
| 2735 | returns:
|
|---|
| 2736 | if vertex is current qh.vertex_visit
|
|---|
| 2737 | deletes facet1 from vertex->neighbors
|
|---|
| 2738 | else
|
|---|
| 2739 | renames facet1 to facet2 in vertex->neighbors
|
|---|
| 2740 | deletes vertices if only one neighbor
|
|---|
| 2741 |
|
|---|
| 2742 | notes:
|
|---|
| 2743 | assumes vertex neighbor sets are good
|
|---|
| 2744 | */
|
|---|
| 2745 | void qh_mergevertex_neighbors(facetT *facet1, facetT *facet2) {
|
|---|
| 2746 | vertexT *vertex, **vertexp;
|
|---|
| 2747 |
|
|---|
| 2748 | trace4((qh ferr, 4042, "qh_mergevertex_neighbors: merge vertex neighbors of f%d and f%d\n",
|
|---|
| 2749 | facet1->id, facet2->id));
|
|---|
| 2750 | if (qh tracevertex) {
|
|---|
| 2751 | qh_fprintf(qh ferr, 8081, "qh_mergevertex_neighbors: of f%d and f%d at furthest p%d f0= %p\n",
|
|---|
| 2752 | facet1->id, facet2->id, qh furthest_id, qh tracevertex->neighbors->e[0].p);
|
|---|
| 2753 | qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
|
|---|
| 2754 | }
|
|---|
| 2755 | FOREACHvertex_(facet1->vertices) {
|
|---|
| 2756 | if (vertex->visitid != qh vertex_visit)
|
|---|
| 2757 | qh_setreplace(vertex->neighbors, facet1, facet2);
|
|---|
| 2758 | else {
|
|---|
| 2759 | qh_setdel(vertex->neighbors, facet1);
|
|---|
| 2760 | if (!SETsecond_(vertex->neighbors))
|
|---|
| 2761 | qh_mergevertex_del(vertex, facet1, facet2);
|
|---|
| 2762 | }
|
|---|
| 2763 | }
|
|---|
| 2764 | if (qh tracevertex)
|
|---|
| 2765 | qh_errprint("TRACE", NULL, NULL, NULL, qh tracevertex);
|
|---|
| 2766 | } /* mergevertex_neighbors */
|
|---|
| 2767 |
|
|---|
| 2768 |
|
|---|
| 2769 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2770 | >-------------------------------</a><a name="mergevertices">-</a>
|
|---|
| 2771 |
|
|---|
| 2772 | qh_mergevertices( vertices1, vertices2 )
|
|---|
| 2773 | merges the vertex set of facet1 into facet2
|
|---|
| 2774 |
|
|---|
| 2775 | returns:
|
|---|
| 2776 | replaces vertices2 with merged set
|
|---|
| 2777 | preserves vertex_visit for qh_mergevertex_neighbors
|
|---|
| 2778 | updates qh.newvertex_list
|
|---|
| 2779 |
|
|---|
| 2780 | design:
|
|---|
| 2781 | create a merged set of both vertices (in inverse id order)
|
|---|
| 2782 | */
|
|---|
| 2783 | void qh_mergevertices(setT *vertices1, setT **vertices2) {
|
|---|
| 2784 | int newsize= qh_setsize(vertices1)+qh_setsize(*vertices2) - qh hull_dim + 1;
|
|---|
| 2785 | setT *mergedvertices;
|
|---|
| 2786 | vertexT *vertex, **vertexp, **vertex2= SETaddr_(*vertices2, vertexT);
|
|---|
| 2787 |
|
|---|
| 2788 | mergedvertices= qh_settemp(newsize);
|
|---|
| 2789 | FOREACHvertex_(vertices1) {
|
|---|
| 2790 | if (!*vertex2 || vertex->id > (*vertex2)->id)
|
|---|
| 2791 | qh_setappend(&mergedvertices, vertex);
|
|---|
| 2792 | else {
|
|---|
| 2793 | while (*vertex2 && (*vertex2)->id > vertex->id)
|
|---|
| 2794 | qh_setappend(&mergedvertices, *vertex2++);
|
|---|
| 2795 | if (!*vertex2 || (*vertex2)->id < vertex->id)
|
|---|
| 2796 | qh_setappend(&mergedvertices, vertex);
|
|---|
| 2797 | else
|
|---|
| 2798 | qh_setappend(&mergedvertices, *vertex2++);
|
|---|
| 2799 | }
|
|---|
| 2800 | }
|
|---|
| 2801 | while (*vertex2)
|
|---|
| 2802 | qh_setappend(&mergedvertices, *vertex2++);
|
|---|
| 2803 | if (newsize < qh_setsize(mergedvertices)) {
|
|---|
| 2804 | qh_fprintf(qh ferr, 6100, "qhull internal error (qh_mergevertices): facets did not share a ridge\n");
|
|---|
| 2805 | qh_errexit(qh_ERRqhull, NULL, NULL);
|
|---|
| 2806 | }
|
|---|
| 2807 | qh_setfree(vertices2);
|
|---|
| 2808 | *vertices2= mergedvertices;
|
|---|
| 2809 | qh_settemppop();
|
|---|
| 2810 | } /* mergevertices */
|
|---|
| 2811 |
|
|---|
| 2812 |
|
|---|
| 2813 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2814 | >-------------------------------</a><a name="neighbor_intersections">-</a>
|
|---|
| 2815 |
|
|---|
| 2816 | qh_neighbor_intersections( vertex )
|
|---|
| 2817 | return intersection of all vertices in vertex->neighbors except for vertex
|
|---|
| 2818 |
|
|---|
| 2819 | returns:
|
|---|
| 2820 | returns temporary set of vertices
|
|---|
| 2821 | does not include vertex
|
|---|
| 2822 | NULL if a neighbor is simplicial
|
|---|
| 2823 | NULL if empty set
|
|---|
| 2824 |
|
|---|
| 2825 | notes:
|
|---|
| 2826 | used for renaming vertices
|
|---|
| 2827 |
|
|---|
| 2828 | design:
|
|---|
| 2829 | initialize the intersection set with vertices of the first two neighbors
|
|---|
| 2830 | delete vertex from the intersection
|
|---|
| 2831 | for each remaining neighbor
|
|---|
| 2832 | intersect its vertex set with the intersection set
|
|---|
| 2833 | return NULL if empty
|
|---|
| 2834 | return the intersection set
|
|---|
| 2835 | */
|
|---|
| 2836 | setT *qh_neighbor_intersections(vertexT *vertex) {
|
|---|
| 2837 | facetT *neighbor, **neighborp, *neighborA, *neighborB;
|
|---|
| 2838 | setT *intersect;
|
|---|
| 2839 | int neighbor_i, neighbor_n;
|
|---|
| 2840 |
|
|---|
| 2841 | FOREACHneighbor_(vertex) {
|
|---|
| 2842 | if (neighbor->simplicial)
|
|---|
| 2843 | return NULL;
|
|---|
| 2844 | }
|
|---|
| 2845 | neighborA= SETfirstt_(vertex->neighbors, facetT);
|
|---|
| 2846 | neighborB= SETsecondt_(vertex->neighbors, facetT);
|
|---|
| 2847 | zinc_(Zintersectnum);
|
|---|
| 2848 | if (!neighborA)
|
|---|
| 2849 | return NULL;
|
|---|
| 2850 | if (!neighborB)
|
|---|
| 2851 | intersect= qh_setcopy(neighborA->vertices, 0);
|
|---|
| 2852 | else
|
|---|
| 2853 | intersect= qh_vertexintersect_new(neighborA->vertices, neighborB->vertices);
|
|---|
| 2854 | qh_settemppush(intersect);
|
|---|
| 2855 | qh_setdelsorted(intersect, vertex);
|
|---|
| 2856 | FOREACHneighbor_i_(vertex) {
|
|---|
| 2857 | if (neighbor_i >= 2) {
|
|---|
| 2858 | zinc_(Zintersectnum);
|
|---|
| 2859 | qh_vertexintersect(&intersect, neighbor->vertices);
|
|---|
| 2860 | if (!SETfirst_(intersect)) {
|
|---|
| 2861 | zinc_(Zintersectfail);
|
|---|
| 2862 | qh_settempfree(&intersect);
|
|---|
| 2863 | return NULL;
|
|---|
| 2864 | }
|
|---|
| 2865 | }
|
|---|
| 2866 | }
|
|---|
| 2867 | trace3((qh ferr, 3007, "qh_neighbor_intersections: %d vertices in neighbor intersection of v%d\n",
|
|---|
| 2868 | qh_setsize(intersect), vertex->id));
|
|---|
| 2869 | return intersect;
|
|---|
| 2870 | } /* neighbor_intersections */
|
|---|
| 2871 |
|
|---|
| 2872 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2873 | >-------------------------------</a><a name="newvertices">-</a>
|
|---|
| 2874 |
|
|---|
| 2875 | qh_newvertices( vertices )
|
|---|
| 2876 | add vertices to end of qh.vertex_list (marks as new vertices)
|
|---|
| 2877 |
|
|---|
| 2878 | returns:
|
|---|
| 2879 | vertices on qh.newvertex_list
|
|---|
| 2880 | vertex->newlist set
|
|---|
| 2881 | */
|
|---|
| 2882 | void qh_newvertices(setT *vertices) {
|
|---|
| 2883 | vertexT *vertex, **vertexp;
|
|---|
| 2884 |
|
|---|
| 2885 | FOREACHvertex_(vertices) {
|
|---|
| 2886 | if (!vertex->newlist) {
|
|---|
| 2887 | qh_removevertex(vertex);
|
|---|
| 2888 | qh_appendvertex(vertex);
|
|---|
| 2889 | }
|
|---|
| 2890 | }
|
|---|
| 2891 | } /* newvertices */
|
|---|
| 2892 |
|
|---|
| 2893 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2894 | >-------------------------------</a><a name="reducevertices">-</a>
|
|---|
| 2895 |
|
|---|
| 2896 | qh_reducevertices()
|
|---|
| 2897 | reduce extra vertices, shared vertices, and redundant vertices
|
|---|
| 2898 | facet->newmerge is set if merged since last call
|
|---|
| 2899 | if !qh.MERGEvertices, only removes extra vertices
|
|---|
| 2900 |
|
|---|
| 2901 | returns:
|
|---|
| 2902 | True if also merged degen_redundant facets
|
|---|
| 2903 | vertices are renamed if possible
|
|---|
| 2904 | clears facet->newmerge and vertex->delridge
|
|---|
| 2905 |
|
|---|
| 2906 | notes:
|
|---|
| 2907 | ignored if 2-d
|
|---|
| 2908 |
|
|---|
| 2909 | design:
|
|---|
| 2910 | merge any degenerate or redundant facets
|
|---|
| 2911 | for each newly merged facet
|
|---|
| 2912 | remove extra vertices
|
|---|
| 2913 | if qh.MERGEvertices
|
|---|
| 2914 | for each newly merged facet
|
|---|
| 2915 | for each vertex
|
|---|
| 2916 | if vertex was on a deleted ridge
|
|---|
| 2917 | rename vertex if it is shared
|
|---|
| 2918 | remove delridge flag from new vertices
|
|---|
| 2919 | */
|
|---|
| 2920 | boolT qh_reducevertices(void) {
|
|---|
| 2921 | int numshare=0, numrename= 0;
|
|---|
| 2922 | boolT degenredun= False;
|
|---|
| 2923 | facetT *newfacet;
|
|---|
| 2924 | vertexT *vertex, **vertexp;
|
|---|
| 2925 |
|
|---|
| 2926 | if (qh hull_dim == 2)
|
|---|
| 2927 | return False;
|
|---|
| 2928 | if (qh_merge_degenredundant())
|
|---|
| 2929 | degenredun= True;
|
|---|
| 2930 | LABELrestart:
|
|---|
| 2931 | FORALLnew_facets {
|
|---|
| 2932 | if (newfacet->newmerge) {
|
|---|
| 2933 | if (!qh MERGEvertices)
|
|---|
| 2934 | newfacet->newmerge= False;
|
|---|
| 2935 | qh_remove_extravertices(newfacet);
|
|---|
| 2936 | }
|
|---|
| 2937 | }
|
|---|
| 2938 | if (!qh MERGEvertices)
|
|---|
| 2939 | return False;
|
|---|
| 2940 | FORALLnew_facets {
|
|---|
| 2941 | if (newfacet->newmerge) {
|
|---|
| 2942 | newfacet->newmerge= False;
|
|---|
| 2943 | FOREACHvertex_(newfacet->vertices) {
|
|---|
| 2944 | if (vertex->delridge) {
|
|---|
| 2945 | if (qh_rename_sharedvertex(vertex, newfacet)) {
|
|---|
| 2946 | numshare++;
|
|---|
| 2947 | vertexp--; /* repeat since deleted vertex */
|
|---|
| 2948 | }
|
|---|
| 2949 | }
|
|---|
| 2950 | }
|
|---|
| 2951 | }
|
|---|
| 2952 | }
|
|---|
| 2953 | FORALLvertex_(qh newvertex_list) {
|
|---|
| 2954 | if (vertex->delridge && !vertex->deleted) {
|
|---|
| 2955 | vertex->delridge= False;
|
|---|
| 2956 | if (qh hull_dim >= 4 && qh_redundant_vertex(vertex)) {
|
|---|
| 2957 | numrename++;
|
|---|
| 2958 | if (qh_merge_degenredundant()) {
|
|---|
| 2959 | degenredun= True;
|
|---|
| 2960 | goto LABELrestart;
|
|---|
| 2961 | }
|
|---|
| 2962 | }
|
|---|
| 2963 | }
|
|---|
| 2964 | }
|
|---|
| 2965 | trace1((qh ferr, 1014, "qh_reducevertices: renamed %d shared vertices and %d redundant vertices. Degen? %d\n",
|
|---|
| 2966 | numshare, numrename, degenredun));
|
|---|
| 2967 | return degenredun;
|
|---|
| 2968 | } /* reducevertices */
|
|---|
| 2969 |
|
|---|
| 2970 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 2971 | >-------------------------------</a><a name="redundant_vertex">-</a>
|
|---|
| 2972 |
|
|---|
| 2973 | qh_redundant_vertex( vertex )
|
|---|
| 2974 | detect and rename a redundant vertex
|
|---|
| 2975 | vertices have full vertex->neighbors
|
|---|
| 2976 |
|
|---|
| 2977 | returns:
|
|---|
| 2978 | returns true if find a redundant vertex
|
|---|
| 2979 | deletes vertex(vertex->deleted)
|
|---|
| 2980 |
|
|---|
| 2981 | notes:
|
|---|
| 2982 | only needed if vertex->delridge and hull_dim >= 4
|
|---|
| 2983 | may add degenerate facets to qh.facet_mergeset
|
|---|
| 2984 | doesn't change vertex->neighbors or create redundant facets
|
|---|
| 2985 |
|
|---|
| 2986 | design:
|
|---|
| 2987 | intersect vertices of all facet neighbors of vertex
|
|---|
| 2988 | determine ridges for these vertices
|
|---|
| 2989 | if find a new vertex for vertex amoung these ridges and vertices
|
|---|
| 2990 | rename vertex to the new vertex
|
|---|
| 2991 | */
|
|---|
| 2992 | vertexT *qh_redundant_vertex(vertexT *vertex) {
|
|---|
| 2993 | vertexT *newvertex= NULL;
|
|---|
| 2994 | setT *vertices, *ridges;
|
|---|
| 2995 |
|
|---|
| 2996 | trace3((qh ferr, 3008, "qh_redundant_vertex: check if v%d can be renamed\n", vertex->id));
|
|---|
| 2997 | if ((vertices= qh_neighbor_intersections(vertex))) {
|
|---|
| 2998 | ridges= qh_vertexridges(vertex);
|
|---|
| 2999 | if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
|
|---|
| 3000 | qh_renamevertex(vertex, newvertex, ridges, NULL, NULL);
|
|---|
| 3001 | qh_settempfree(&ridges);
|
|---|
| 3002 | qh_settempfree(&vertices);
|
|---|
| 3003 | }
|
|---|
| 3004 | return newvertex;
|
|---|
| 3005 | } /* redundant_vertex */
|
|---|
| 3006 |
|
|---|
| 3007 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3008 | >-------------------------------</a><a name="remove_extravertices">-</a>
|
|---|
| 3009 |
|
|---|
| 3010 | qh_remove_extravertices( facet )
|
|---|
| 3011 | remove extra vertices from non-simplicial facets
|
|---|
| 3012 |
|
|---|
| 3013 | returns:
|
|---|
| 3014 | returns True if it finds them
|
|---|
| 3015 |
|
|---|
| 3016 | design:
|
|---|
| 3017 | for each vertex in facet
|
|---|
| 3018 | if vertex not in a ridge (i.e., no longer used)
|
|---|
| 3019 | delete vertex from facet
|
|---|
| 3020 | delete facet from vertice's neighbors
|
|---|
| 3021 | unless vertex in another facet
|
|---|
| 3022 | add vertex to qh.del_vertices for later deletion
|
|---|
| 3023 | */
|
|---|
| 3024 | boolT qh_remove_extravertices(facetT *facet) {
|
|---|
| 3025 | ridgeT *ridge, **ridgep;
|
|---|
| 3026 | vertexT *vertex, **vertexp;
|
|---|
| 3027 | boolT foundrem= False;
|
|---|
| 3028 |
|
|---|
| 3029 | trace4((qh ferr, 4043, "qh_remove_extravertices: test f%d for extra vertices\n",
|
|---|
| 3030 | facet->id));
|
|---|
| 3031 | FOREACHvertex_(facet->vertices)
|
|---|
| 3032 | vertex->seen= False;
|
|---|
| 3033 | FOREACHridge_(facet->ridges) {
|
|---|
| 3034 | FOREACHvertex_(ridge->vertices)
|
|---|
| 3035 | vertex->seen= True;
|
|---|
| 3036 | }
|
|---|
| 3037 | FOREACHvertex_(facet->vertices) {
|
|---|
| 3038 | if (!vertex->seen) {
|
|---|
| 3039 | foundrem= True;
|
|---|
| 3040 | zinc_(Zremvertex);
|
|---|
| 3041 | qh_setdelsorted(facet->vertices, vertex);
|
|---|
| 3042 | qh_setdel(vertex->neighbors, facet);
|
|---|
| 3043 | if (!qh_setsize(vertex->neighbors)) {
|
|---|
| 3044 | vertex->deleted= True;
|
|---|
| 3045 | qh_setappend(&qh del_vertices, vertex);
|
|---|
| 3046 | zinc_(Zremvertexdel);
|
|---|
| 3047 | trace2((qh ferr, 2036, "qh_remove_extravertices: v%d deleted because it's lost all ridges\n", vertex->id));
|
|---|
| 3048 | }else
|
|---|
| 3049 | trace3((qh ferr, 3009, "qh_remove_extravertices: v%d removed from f%d because it's lost all ridges\n", vertex->id, facet->id));
|
|---|
| 3050 | vertexp--; /*repeat*/
|
|---|
| 3051 | }
|
|---|
| 3052 | }
|
|---|
| 3053 | return foundrem;
|
|---|
| 3054 | } /* remove_extravertices */
|
|---|
| 3055 |
|
|---|
| 3056 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3057 | >-------------------------------</a><a name="rename_sharedvertex">-</a>
|
|---|
| 3058 |
|
|---|
| 3059 | qh_rename_sharedvertex( vertex, facet )
|
|---|
| 3060 | detect and rename if shared vertex in facet
|
|---|
| 3061 | vertices have full ->neighbors
|
|---|
| 3062 |
|
|---|
| 3063 | returns:
|
|---|
| 3064 | newvertex or NULL
|
|---|
| 3065 | the vertex may still exist in other facets (i.e., a neighbor was pinched)
|
|---|
| 3066 | does not change facet->neighbors
|
|---|
| 3067 | updates vertex->neighbors
|
|---|
| 3068 |
|
|---|
| 3069 | notes:
|
|---|
| 3070 | a shared vertex for a facet is only in ridges to one neighbor
|
|---|
| 3071 | this may undo a pinched facet
|
|---|
| 3072 |
|
|---|
| 3073 | it does not catch pinches involving multiple facets. These appear
|
|---|
| 3074 | to be difficult to detect, since an exhaustive search is too expensive.
|
|---|
| 3075 |
|
|---|
| 3076 | design:
|
|---|
| 3077 | if vertex only has two neighbors
|
|---|
| 3078 | determine the ridges that contain the vertex
|
|---|
| 3079 | determine the vertices shared by both neighbors
|
|---|
| 3080 | if can find a new vertex in this set
|
|---|
| 3081 | rename the vertex to the new vertex
|
|---|
| 3082 | */
|
|---|
| 3083 | vertexT *qh_rename_sharedvertex(vertexT *vertex, facetT *facet) {
|
|---|
| 3084 | facetT *neighbor, **neighborp, *neighborA= NULL;
|
|---|
| 3085 | setT *vertices, *ridges;
|
|---|
| 3086 | vertexT *newvertex;
|
|---|
| 3087 |
|
|---|
| 3088 | if (qh_setsize(vertex->neighbors) == 2) {
|
|---|
| 3089 | neighborA= SETfirstt_(vertex->neighbors, facetT);
|
|---|
| 3090 | if (neighborA == facet)
|
|---|
| 3091 | neighborA= SETsecondt_(vertex->neighbors, facetT);
|
|---|
| 3092 | }else if (qh hull_dim == 3)
|
|---|
| 3093 | return NULL;
|
|---|
| 3094 | else {
|
|---|
| 3095 | qh visit_id++;
|
|---|
| 3096 | FOREACHneighbor_(facet)
|
|---|
| 3097 | neighbor->visitid= qh visit_id;
|
|---|
| 3098 | FOREACHneighbor_(vertex) {
|
|---|
| 3099 | if (neighbor->visitid == qh visit_id) {
|
|---|
| 3100 | if (neighborA)
|
|---|
| 3101 | return NULL;
|
|---|
| 3102 | neighborA= neighbor;
|
|---|
| 3103 | }
|
|---|
| 3104 | }
|
|---|
| 3105 | if (!neighborA) {
|
|---|
| 3106 | qh_fprintf(qh ferr, 6101, "qhull internal error (qh_rename_sharedvertex): v%d's neighbors not in f%d\n",
|
|---|
| 3107 | vertex->id, facet->id);
|
|---|
| 3108 | qh_errprint("ERRONEOUS", facet, NULL, NULL, vertex);
|
|---|
| 3109 | qh_errexit(qh_ERRqhull, NULL, NULL);
|
|---|
| 3110 | }
|
|---|
| 3111 | }
|
|---|
| 3112 | /* the vertex is shared by facet and neighborA */
|
|---|
| 3113 | ridges= qh_settemp(qh TEMPsize);
|
|---|
| 3114 | neighborA->visitid= ++qh visit_id;
|
|---|
| 3115 | qh_vertexridges_facet(vertex, facet, &ridges);
|
|---|
| 3116 | trace2((qh ferr, 2037, "qh_rename_sharedvertex: p%d(v%d) is shared by f%d(%d ridges) and f%d\n",
|
|---|
| 3117 | qh_pointid(vertex->point), vertex->id, facet->id, qh_setsize(ridges), neighborA->id));
|
|---|
| 3118 | zinc_(Zintersectnum);
|
|---|
| 3119 | vertices= qh_vertexintersect_new(facet->vertices, neighborA->vertices);
|
|---|
| 3120 | qh_setdel(vertices, vertex);
|
|---|
| 3121 | qh_settemppush(vertices);
|
|---|
| 3122 | if ((newvertex= qh_find_newvertex(vertex, vertices, ridges)))
|
|---|
| 3123 | qh_renamevertex(vertex, newvertex, ridges, facet, neighborA);
|
|---|
| 3124 | qh_settempfree(&vertices);
|
|---|
| 3125 | qh_settempfree(&ridges);
|
|---|
| 3126 | return newvertex;
|
|---|
| 3127 | } /* rename_sharedvertex */
|
|---|
| 3128 |
|
|---|
| 3129 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3130 | >-------------------------------</a><a name="renameridgevertex">-</a>
|
|---|
| 3131 |
|
|---|
| 3132 | qh_renameridgevertex( ridge, oldvertex, newvertex )
|
|---|
| 3133 | renames oldvertex as newvertex in ridge
|
|---|
| 3134 |
|
|---|
| 3135 | returns:
|
|---|
| 3136 |
|
|---|
| 3137 | design:
|
|---|
| 3138 | delete oldvertex from ridge
|
|---|
| 3139 | if newvertex already in ridge
|
|---|
| 3140 | copy ridge->noconvex to another ridge if possible
|
|---|
| 3141 | delete the ridge
|
|---|
| 3142 | else
|
|---|
| 3143 | insert newvertex into the ridge
|
|---|
| 3144 | adjust the ridge's orientation
|
|---|
| 3145 | */
|
|---|
| 3146 | void qh_renameridgevertex(ridgeT *ridge, vertexT *oldvertex, vertexT *newvertex) {
|
|---|
| 3147 | int nth= 0, oldnth;
|
|---|
| 3148 | facetT *temp;
|
|---|
| 3149 | vertexT *vertex, **vertexp;
|
|---|
| 3150 |
|
|---|
| 3151 | oldnth= qh_setindex(ridge->vertices, oldvertex);
|
|---|
| 3152 | qh_setdelnthsorted(ridge->vertices, oldnth);
|
|---|
| 3153 | FOREACHvertex_(ridge->vertices) {
|
|---|
| 3154 | if (vertex == newvertex) {
|
|---|
| 3155 | zinc_(Zdelridge);
|
|---|
| 3156 | if (ridge->nonconvex) /* only one ridge has nonconvex set */
|
|---|
| 3157 | qh_copynonconvex(ridge);
|
|---|
| 3158 | qh_delridge(ridge);
|
|---|
| 3159 | trace2((qh ferr, 2038, "qh_renameridgevertex: ridge r%d deleted. It contained both v%d and v%d\n",
|
|---|
| 3160 | ridge->id, oldvertex->id, newvertex->id));
|
|---|
| 3161 | return;
|
|---|
| 3162 | }
|
|---|
| 3163 | if (vertex->id < newvertex->id)
|
|---|
| 3164 | break;
|
|---|
| 3165 | nth++;
|
|---|
| 3166 | }
|
|---|
| 3167 | qh_setaddnth(&ridge->vertices, nth, newvertex);
|
|---|
| 3168 | if (abs(oldnth - nth)%2) {
|
|---|
| 3169 | trace3((qh ferr, 3010, "qh_renameridgevertex: swapped the top and bottom of ridge r%d\n",
|
|---|
| 3170 | ridge->id));
|
|---|
| 3171 | temp= ridge->top;
|
|---|
| 3172 | ridge->top= ridge->bottom;
|
|---|
| 3173 | ridge->bottom= temp;
|
|---|
| 3174 | }
|
|---|
| 3175 | } /* renameridgevertex */
|
|---|
| 3176 |
|
|---|
| 3177 |
|
|---|
| 3178 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3179 | >-------------------------------</a><a name="renamevertex">-</a>
|
|---|
| 3180 |
|
|---|
| 3181 | qh_renamevertex( oldvertex, newvertex, ridges, oldfacet, neighborA )
|
|---|
| 3182 | renames oldvertex as newvertex in ridges
|
|---|
| 3183 | gives oldfacet/neighborA if oldvertex is shared between two facets
|
|---|
| 3184 |
|
|---|
| 3185 | returns:
|
|---|
| 3186 | oldvertex may still exist afterwards
|
|---|
| 3187 |
|
|---|
| 3188 |
|
|---|
| 3189 | notes:
|
|---|
| 3190 | can not change neighbors of newvertex (since it's a subset)
|
|---|
| 3191 |
|
|---|
| 3192 | design:
|
|---|
| 3193 | for each ridge in ridges
|
|---|
| 3194 | rename oldvertex to newvertex and delete degenerate ridges
|
|---|
| 3195 | if oldfacet not defined
|
|---|
| 3196 | for each neighbor of oldvertex
|
|---|
| 3197 | delete oldvertex from neighbor's vertices
|
|---|
| 3198 | remove extra vertices from neighbor
|
|---|
| 3199 | add oldvertex to qh.del_vertices
|
|---|
| 3200 | else if oldvertex only between oldfacet and neighborA
|
|---|
| 3201 | delete oldvertex from oldfacet and neighborA
|
|---|
| 3202 | add oldvertex to qh.del_vertices
|
|---|
| 3203 | else oldvertex is in oldfacet and neighborA and other facets (i.e., pinched)
|
|---|
| 3204 | delete oldvertex from oldfacet
|
|---|
| 3205 | delete oldfacet from oldvertice's neighbors
|
|---|
| 3206 | remove extra vertices (e.g., oldvertex) from neighborA
|
|---|
| 3207 | */
|
|---|
| 3208 | void qh_renamevertex(vertexT *oldvertex, vertexT *newvertex, setT *ridges, facetT *oldfacet, facetT *neighborA) {
|
|---|
| 3209 | facetT *neighbor, **neighborp;
|
|---|
| 3210 | ridgeT *ridge, **ridgep;
|
|---|
| 3211 | boolT istrace= False;
|
|---|
| 3212 |
|
|---|
| 3213 | if (qh IStracing >= 2 || oldvertex->id == qh tracevertex_id ||
|
|---|
| 3214 | newvertex->id == qh tracevertex_id)
|
|---|
| 3215 | istrace= True;
|
|---|
| 3216 | FOREACHridge_(ridges)
|
|---|
| 3217 | qh_renameridgevertex(ridge, oldvertex, newvertex);
|
|---|
| 3218 | if (!oldfacet) {
|
|---|
| 3219 | zinc_(Zrenameall);
|
|---|
| 3220 | if (istrace)
|
|---|
| 3221 | qh_fprintf(qh ferr, 8082, "qh_renamevertex: renamed v%d to v%d in several facets\n",
|
|---|
| 3222 | oldvertex->id, newvertex->id);
|
|---|
| 3223 | FOREACHneighbor_(oldvertex) {
|
|---|
| 3224 | qh_maydropneighbor(neighbor);
|
|---|
| 3225 | qh_setdelsorted(neighbor->vertices, oldvertex);
|
|---|
| 3226 | if (qh_remove_extravertices(neighbor))
|
|---|
| 3227 | neighborp--; /* neighbor may be deleted */
|
|---|
| 3228 | }
|
|---|
| 3229 | if (!oldvertex->deleted) {
|
|---|
| 3230 | oldvertex->deleted= True;
|
|---|
| 3231 | qh_setappend(&qh del_vertices, oldvertex);
|
|---|
| 3232 | }
|
|---|
| 3233 | }else if (qh_setsize(oldvertex->neighbors) == 2) {
|
|---|
| 3234 | zinc_(Zrenameshare);
|
|---|
| 3235 | if (istrace)
|
|---|
| 3236 | qh_fprintf(qh ferr, 8083, "qh_renamevertex: renamed v%d to v%d in oldfacet f%d\n",
|
|---|
| 3237 | oldvertex->id, newvertex->id, oldfacet->id);
|
|---|
| 3238 | FOREACHneighbor_(oldvertex)
|
|---|
| 3239 | qh_setdelsorted(neighbor->vertices, oldvertex);
|
|---|
| 3240 | oldvertex->deleted= True;
|
|---|
| 3241 | qh_setappend(&qh del_vertices, oldvertex);
|
|---|
| 3242 | }else {
|
|---|
| 3243 | zinc_(Zrenamepinch);
|
|---|
| 3244 | if (istrace || qh IStracing)
|
|---|
| 3245 | qh_fprintf(qh ferr, 8084, "qh_renamevertex: renamed pinched v%d to v%d between f%d and f%d\n",
|
|---|
| 3246 | oldvertex->id, newvertex->id, oldfacet->id, neighborA->id);
|
|---|
| 3247 | qh_setdelsorted(oldfacet->vertices, oldvertex);
|
|---|
| 3248 | qh_setdel(oldvertex->neighbors, oldfacet);
|
|---|
| 3249 | qh_remove_extravertices(neighborA);
|
|---|
| 3250 | }
|
|---|
| 3251 | } /* renamevertex */
|
|---|
| 3252 |
|
|---|
| 3253 |
|
|---|
| 3254 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3255 | >-------------------------------</a><a name="test_appendmerge">-</a>
|
|---|
| 3256 |
|
|---|
| 3257 | qh_test_appendmerge( facet, neighbor )
|
|---|
| 3258 | tests facet/neighbor for convexity
|
|---|
| 3259 | appends to mergeset if non-convex
|
|---|
| 3260 | if pre-merging,
|
|---|
| 3261 | nop if qh.SKIPconvex, or qh.MERGEexact and coplanar
|
|---|
| 3262 |
|
|---|
| 3263 | returns:
|
|---|
| 3264 | true if appends facet/neighbor to mergeset
|
|---|
| 3265 | sets facet->center as needed
|
|---|
| 3266 | does not change facet->seen
|
|---|
| 3267 |
|
|---|
| 3268 | design:
|
|---|
| 3269 | if qh.cos_max is defined
|
|---|
| 3270 | if the angle between facet normals is too shallow
|
|---|
| 3271 | append an angle-coplanar merge to qh.mergeset
|
|---|
| 3272 | return True
|
|---|
| 3273 | make facet's centrum if needed
|
|---|
| 3274 | if facet's centrum is above the neighbor
|
|---|
| 3275 | set isconcave
|
|---|
| 3276 | else
|
|---|
| 3277 | if facet's centrum is not below the neighbor
|
|---|
| 3278 | set iscoplanar
|
|---|
| 3279 | make neighbor's centrum if needed
|
|---|
| 3280 | if neighbor's centrum is above the facet
|
|---|
| 3281 | set isconcave
|
|---|
| 3282 | else if neighbor's centrum is not below the facet
|
|---|
| 3283 | set iscoplanar
|
|---|
| 3284 | if isconcave or iscoplanar
|
|---|
| 3285 | get angle if needed
|
|---|
| 3286 | append concave or coplanar merge to qh.mergeset
|
|---|
| 3287 | */
|
|---|
| 3288 | boolT qh_test_appendmerge(facetT *facet, facetT *neighbor) {
|
|---|
| 3289 | realT dist, dist2= -REALmax, angle= -REALmax;
|
|---|
| 3290 | boolT isconcave= False, iscoplanar= False, okangle= False;
|
|---|
| 3291 |
|
|---|
| 3292 | if (qh SKIPconvex && !qh POSTmerging)
|
|---|
| 3293 | return False;
|
|---|
| 3294 | if ((!qh MERGEexact || qh POSTmerging) && qh cos_max < REALmax/2) {
|
|---|
| 3295 | angle= qh_getangle(facet->normal, neighbor->normal);
|
|---|
| 3296 | zinc_(Zangletests);
|
|---|
| 3297 | if (angle > qh cos_max) {
|
|---|
| 3298 | zinc_(Zcoplanarangle);
|
|---|
| 3299 | qh_appendmergeset(facet, neighbor, MRGanglecoplanar, &angle);
|
|---|
| 3300 | trace2((qh ferr, 2039, "qh_test_appendmerge: coplanar angle %4.4g between f%d and f%d\n",
|
|---|
| 3301 | angle, facet->id, neighbor->id));
|
|---|
| 3302 | return True;
|
|---|
| 3303 | }else
|
|---|
| 3304 | okangle= True;
|
|---|
| 3305 | }
|
|---|
| 3306 | if (!facet->center)
|
|---|
| 3307 | facet->center= qh_getcentrum(facet);
|
|---|
| 3308 | zzinc_(Zcentrumtests);
|
|---|
| 3309 | qh_distplane(facet->center, neighbor, &dist);
|
|---|
| 3310 | if (dist > qh centrum_radius)
|
|---|
| 3311 | isconcave= True;
|
|---|
| 3312 | else {
|
|---|
| 3313 | if (dist > -qh centrum_radius)
|
|---|
| 3314 | iscoplanar= True;
|
|---|
| 3315 | if (!neighbor->center)
|
|---|
| 3316 | neighbor->center= qh_getcentrum(neighbor);
|
|---|
| 3317 | zzinc_(Zcentrumtests);
|
|---|
| 3318 | qh_distplane(neighbor->center, facet, &dist2);
|
|---|
| 3319 | if (dist2 > qh centrum_radius)
|
|---|
| 3320 | isconcave= True;
|
|---|
| 3321 | else if (!iscoplanar && dist2 > -qh centrum_radius)
|
|---|
| 3322 | iscoplanar= True;
|
|---|
| 3323 | }
|
|---|
| 3324 | if (!isconcave && (!iscoplanar || (qh MERGEexact && !qh POSTmerging)))
|
|---|
| 3325 | return False;
|
|---|
| 3326 | if (!okangle && qh ANGLEmerge) {
|
|---|
| 3327 | angle= qh_getangle(facet->normal, neighbor->normal);
|
|---|
| 3328 | zinc_(Zangletests);
|
|---|
| 3329 | }
|
|---|
| 3330 | if (isconcave) {
|
|---|
| 3331 | zinc_(Zconcaveridge);
|
|---|
| 3332 | if (qh ANGLEmerge)
|
|---|
| 3333 | angle += qh_ANGLEconcave + 0.5;
|
|---|
| 3334 | qh_appendmergeset(facet, neighbor, MRGconcave, &angle);
|
|---|
| 3335 | trace0((qh ferr, 18, "qh_test_appendmerge: concave f%d to f%d dist %4.4g and reverse dist %4.4g angle %4.4g during p%d\n",
|
|---|
| 3336 | facet->id, neighbor->id, dist, dist2, angle, qh furthest_id));
|
|---|
| 3337 | }else /* iscoplanar */ {
|
|---|
| 3338 | zinc_(Zcoplanarcentrum);
|
|---|
| 3339 | qh_appendmergeset(facet, neighbor, MRGcoplanar, &angle);
|
|---|
| 3340 | trace2((qh ferr, 2040, "qh_test_appendmerge: coplanar f%d to f%d dist %4.4g, reverse dist %4.4g angle %4.4g\n",
|
|---|
| 3341 | facet->id, neighbor->id, dist, dist2, angle));
|
|---|
| 3342 | }
|
|---|
| 3343 | return True;
|
|---|
| 3344 | } /* test_appendmerge */
|
|---|
| 3345 |
|
|---|
| 3346 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3347 | >-------------------------------</a><a name="test_vneighbors">-</a>
|
|---|
| 3348 |
|
|---|
| 3349 | qh_test_vneighbors()
|
|---|
| 3350 | test vertex neighbors for convexity
|
|---|
| 3351 | tests all facets on qh.newfacet_list
|
|---|
| 3352 |
|
|---|
| 3353 | returns:
|
|---|
| 3354 | true if non-convex vneighbors appended to qh.facet_mergeset
|
|---|
| 3355 | initializes vertex neighbors if needed
|
|---|
| 3356 |
|
|---|
| 3357 | notes:
|
|---|
| 3358 | assumes all facet neighbors have been tested
|
|---|
| 3359 | this can be expensive
|
|---|
| 3360 | this does not guarantee that a centrum is below all facets
|
|---|
| 3361 | but it is unlikely
|
|---|
| 3362 | uses qh.visit_id
|
|---|
| 3363 |
|
|---|
| 3364 | design:
|
|---|
| 3365 | build vertex neighbors if necessary
|
|---|
| 3366 | for all new facets
|
|---|
| 3367 | for all vertices
|
|---|
| 3368 | for each unvisited facet neighbor of the vertex
|
|---|
| 3369 | test new facet and neighbor for convexity
|
|---|
| 3370 | */
|
|---|
| 3371 | boolT qh_test_vneighbors(void /* qh newfacet_list */) {
|
|---|
| 3372 | facetT *newfacet, *neighbor, **neighborp;
|
|---|
| 3373 | vertexT *vertex, **vertexp;
|
|---|
| 3374 | int nummerges= 0;
|
|---|
| 3375 |
|
|---|
| 3376 | trace1((qh ferr, 1015, "qh_test_vneighbors: testing vertex neighbors for convexity\n"));
|
|---|
| 3377 | if (!qh VERTEXneighbors)
|
|---|
| 3378 | qh_vertexneighbors();
|
|---|
| 3379 | FORALLnew_facets
|
|---|
| 3380 | newfacet->seen= False;
|
|---|
| 3381 | FORALLnew_facets {
|
|---|
| 3382 | newfacet->seen= True;
|
|---|
| 3383 | newfacet->visitid= qh visit_id++;
|
|---|
| 3384 | FOREACHneighbor_(newfacet)
|
|---|
| 3385 | newfacet->visitid= qh visit_id;
|
|---|
| 3386 | FOREACHvertex_(newfacet->vertices) {
|
|---|
| 3387 | FOREACHneighbor_(vertex) {
|
|---|
| 3388 | if (neighbor->seen || neighbor->visitid == qh visit_id)
|
|---|
| 3389 | continue;
|
|---|
| 3390 | if (qh_test_appendmerge(newfacet, neighbor))
|
|---|
| 3391 | nummerges++;
|
|---|
| 3392 | }
|
|---|
| 3393 | }
|
|---|
| 3394 | }
|
|---|
| 3395 | zadd_(Ztestvneighbor, nummerges);
|
|---|
| 3396 | trace1((qh ferr, 1016, "qh_test_vneighbors: found %d non-convex, vertex neighbors\n",
|
|---|
| 3397 | nummerges));
|
|---|
| 3398 | return (nummerges > 0);
|
|---|
| 3399 | } /* test_vneighbors */
|
|---|
| 3400 |
|
|---|
| 3401 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3402 | >-------------------------------</a><a name="tracemerge">-</a>
|
|---|
| 3403 |
|
|---|
| 3404 | qh_tracemerge( facet1, facet2 )
|
|---|
| 3405 | print trace message after merge
|
|---|
| 3406 | */
|
|---|
| 3407 | void qh_tracemerge(facetT *facet1, facetT *facet2) {
|
|---|
| 3408 | boolT waserror= False;
|
|---|
| 3409 |
|
|---|
| 3410 | #ifndef qh_NOtrace
|
|---|
| 3411 | if (qh IStracing >= 4)
|
|---|
| 3412 | qh_errprint("MERGED", facet2, NULL, NULL, NULL);
|
|---|
| 3413 | if (facet2 == qh tracefacet || (qh tracevertex && qh tracevertex->newlist)) {
|
|---|
| 3414 | qh_fprintf(qh ferr, 8085, "qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->id, facet2->id, qh furthest_id);
|
|---|
| 3415 | if (facet2 != qh tracefacet)
|
|---|
| 3416 | qh_errprint("TRACE", qh tracefacet,
|
|---|
| 3417 | (qh tracevertex && qh tracevertex->neighbors) ?
|
|---|
| 3418 | SETfirstt_(qh tracevertex->neighbors, facetT) : NULL,
|
|---|
| 3419 | NULL, qh tracevertex);
|
|---|
| 3420 | }
|
|---|
| 3421 | if (qh tracevertex) {
|
|---|
| 3422 | if (qh tracevertex->deleted)
|
|---|
| 3423 | qh_fprintf(qh ferr, 8086, "qh_tracemerge: trace vertex deleted at furthest p%d\n",
|
|---|
| 3424 | qh furthest_id);
|
|---|
| 3425 | else
|
|---|
| 3426 | qh_checkvertex(qh tracevertex);
|
|---|
| 3427 | }
|
|---|
| 3428 | if (qh tracefacet) {
|
|---|
| 3429 | qh_checkfacet(qh tracefacet, True, &waserror);
|
|---|
| 3430 | if (waserror)
|
|---|
| 3431 | qh_errexit(qh_ERRqhull, qh tracefacet, NULL);
|
|---|
| 3432 | }
|
|---|
| 3433 | #endif /* !qh_NOtrace */
|
|---|
| 3434 | if (qh CHECKfrequently || qh IStracing >= 4) { /* can't check polygon here */
|
|---|
| 3435 | qh_checkfacet(facet2, True, &waserror);
|
|---|
| 3436 | if (waserror)
|
|---|
| 3437 | qh_errexit(qh_ERRqhull, NULL, NULL);
|
|---|
| 3438 | }
|
|---|
| 3439 | } /* tracemerge */
|
|---|
| 3440 |
|
|---|
| 3441 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3442 | >-------------------------------</a><a name="tracemerging">-</a>
|
|---|
| 3443 |
|
|---|
| 3444 | qh_tracemerging()
|
|---|
| 3445 | print trace message during POSTmerging
|
|---|
| 3446 |
|
|---|
| 3447 | returns:
|
|---|
| 3448 | updates qh.mergereport
|
|---|
| 3449 |
|
|---|
| 3450 | notes:
|
|---|
| 3451 | called from qh_mergecycle() and qh_mergefacet()
|
|---|
| 3452 |
|
|---|
| 3453 | see:
|
|---|
| 3454 | qh_buildtracing()
|
|---|
| 3455 | */
|
|---|
| 3456 | void qh_tracemerging(void) {
|
|---|
| 3457 | realT cpu;
|
|---|
| 3458 | int total;
|
|---|
| 3459 | time_t timedata;
|
|---|
| 3460 | struct tm *tp;
|
|---|
| 3461 |
|
|---|
| 3462 | qh mergereport= zzval_(Ztotmerge);
|
|---|
| 3463 | time(&timedata);
|
|---|
| 3464 | tp= localtime(&timedata);
|
|---|
| 3465 | cpu= qh_CPUclock;
|
|---|
| 3466 | cpu /= qh_SECticks;
|
|---|
| 3467 | total= zzval_(Ztotmerge) - zzval_(Zcyclehorizon) + zzval_(Zcyclefacettot);
|
|---|
| 3468 | qh_fprintf(qh ferr, 8087, "\n\
|
|---|
| 3469 | At %d:%d:%d & %2.5g CPU secs, qhull has merged %d facets. The hull\n\
|
|---|
| 3470 | contains %d facets and %d vertices.\n",
|
|---|
| 3471 | tp->tm_hour, tp->tm_min, tp->tm_sec, cpu,
|
|---|
| 3472 | total, qh num_facets - qh num_visible,
|
|---|
| 3473 | qh num_vertices-qh_setsize(qh del_vertices));
|
|---|
| 3474 | } /* tracemerging */
|
|---|
| 3475 |
|
|---|
| 3476 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3477 | >-------------------------------</a><a name="updatetested">-</a>
|
|---|
| 3478 |
|
|---|
| 3479 | qh_updatetested( facet1, facet2 )
|
|---|
| 3480 | clear facet2->tested and facet1->ridge->tested for merge
|
|---|
| 3481 |
|
|---|
| 3482 | returns:
|
|---|
| 3483 | deletes facet2->center unless it's already large
|
|---|
| 3484 | if so, clears facet2->ridge->tested
|
|---|
| 3485 |
|
|---|
| 3486 | design:
|
|---|
| 3487 | clear facet2->tested
|
|---|
| 3488 | clear ridge->tested for facet1's ridges
|
|---|
| 3489 | if facet2 has a centrum
|
|---|
| 3490 | if facet2 is large
|
|---|
| 3491 | set facet2->keepcentrum
|
|---|
| 3492 | else if facet2 has 3 vertices due to many merges, or not large and post merging
|
|---|
| 3493 | clear facet2->keepcentrum
|
|---|
| 3494 | unless facet2->keepcentrum
|
|---|
| 3495 | clear facet2->center to recompute centrum later
|
|---|
| 3496 | clear ridge->tested for facet2's ridges
|
|---|
| 3497 | */
|
|---|
| 3498 | void qh_updatetested(facetT *facet1, facetT *facet2) {
|
|---|
| 3499 | ridgeT *ridge, **ridgep;
|
|---|
| 3500 | int size;
|
|---|
| 3501 |
|
|---|
| 3502 | facet2->tested= False;
|
|---|
| 3503 | FOREACHridge_(facet1->ridges)
|
|---|
| 3504 | ridge->tested= False;
|
|---|
| 3505 | if (!facet2->center)
|
|---|
| 3506 | return;
|
|---|
| 3507 | size= qh_setsize(facet2->vertices);
|
|---|
| 3508 | if (!facet2->keepcentrum) {
|
|---|
| 3509 | if (size > qh hull_dim + qh_MAXnewcentrum) {
|
|---|
| 3510 | facet2->keepcentrum= True;
|
|---|
| 3511 | zinc_(Zwidevertices);
|
|---|
| 3512 | }
|
|---|
| 3513 | }else if (size <= qh hull_dim + qh_MAXnewcentrum) {
|
|---|
| 3514 | /* center and keepcentrum was set */
|
|---|
| 3515 | if (size == qh hull_dim || qh POSTmerging)
|
|---|
| 3516 | facet2->keepcentrum= False; /* if many merges need to recompute centrum */
|
|---|
| 3517 | }
|
|---|
| 3518 | if (!facet2->keepcentrum) {
|
|---|
| 3519 | qh_memfree(facet2->center, qh normal_size);
|
|---|
| 3520 | facet2->center= NULL;
|
|---|
| 3521 | FOREACHridge_(facet2->ridges)
|
|---|
| 3522 | ridge->tested= False;
|
|---|
| 3523 | }
|
|---|
| 3524 | } /* updatetested */
|
|---|
| 3525 |
|
|---|
| 3526 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3527 | >-------------------------------</a><a name="vertexridges">-</a>
|
|---|
| 3528 |
|
|---|
| 3529 | qh_vertexridges( vertex )
|
|---|
| 3530 | return temporary set of ridges adjacent to a vertex
|
|---|
| 3531 | vertex->neighbors defined
|
|---|
| 3532 |
|
|---|
| 3533 | ntoes:
|
|---|
| 3534 | uses qh.visit_id
|
|---|
| 3535 | does not include implicit ridges for simplicial facets
|
|---|
| 3536 |
|
|---|
| 3537 | design:
|
|---|
| 3538 | for each neighbor of vertex
|
|---|
| 3539 | add ridges that include the vertex to ridges
|
|---|
| 3540 | */
|
|---|
| 3541 | setT *qh_vertexridges(vertexT *vertex) {
|
|---|
| 3542 | facetT *neighbor, **neighborp;
|
|---|
| 3543 | setT *ridges= qh_settemp(qh TEMPsize);
|
|---|
| 3544 | int size;
|
|---|
| 3545 |
|
|---|
| 3546 | qh visit_id++;
|
|---|
| 3547 | FOREACHneighbor_(vertex)
|
|---|
| 3548 | neighbor->visitid= qh visit_id;
|
|---|
| 3549 | FOREACHneighbor_(vertex) {
|
|---|
| 3550 | if (*neighborp) /* no new ridges in last neighbor */
|
|---|
| 3551 | qh_vertexridges_facet(vertex, neighbor, &ridges);
|
|---|
| 3552 | }
|
|---|
| 3553 | if (qh PRINTstatistics || qh IStracing) {
|
|---|
| 3554 | size= qh_setsize(ridges);
|
|---|
| 3555 | zinc_(Zvertexridge);
|
|---|
| 3556 | zadd_(Zvertexridgetot, size);
|
|---|
| 3557 | zmax_(Zvertexridgemax, size);
|
|---|
| 3558 | trace3((qh ferr, 3011, "qh_vertexridges: found %d ridges for v%d\n",
|
|---|
| 3559 | size, vertex->id));
|
|---|
| 3560 | }
|
|---|
| 3561 | return ridges;
|
|---|
| 3562 | } /* vertexridges */
|
|---|
| 3563 |
|
|---|
| 3564 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3565 | >-------------------------------</a><a name="vertexridges_facet">-</a>
|
|---|
| 3566 |
|
|---|
| 3567 | qh_vertexridges_facet( vertex, facet, ridges )
|
|---|
| 3568 | add adjacent ridges for vertex in facet
|
|---|
| 3569 | neighbor->visitid==qh.visit_id if it hasn't been visited
|
|---|
| 3570 |
|
|---|
| 3571 | returns:
|
|---|
| 3572 | ridges updated
|
|---|
| 3573 | sets facet->visitid to qh.visit_id-1
|
|---|
| 3574 |
|
|---|
| 3575 | design:
|
|---|
| 3576 | for each ridge of facet
|
|---|
| 3577 | if ridge of visited neighbor (i.e., unprocessed)
|
|---|
| 3578 | if vertex in ridge
|
|---|
| 3579 | append ridge to vertex
|
|---|
| 3580 | mark facet processed
|
|---|
| 3581 | */
|
|---|
| 3582 | void qh_vertexridges_facet(vertexT *vertex, facetT *facet, setT **ridges) {
|
|---|
| 3583 | ridgeT *ridge, **ridgep;
|
|---|
| 3584 | facetT *neighbor;
|
|---|
| 3585 |
|
|---|
| 3586 | FOREACHridge_(facet->ridges) {
|
|---|
| 3587 | neighbor= otherfacet_(ridge, facet);
|
|---|
| 3588 | if (neighbor->visitid == qh visit_id
|
|---|
| 3589 | && qh_setin(ridge->vertices, vertex))
|
|---|
| 3590 | qh_setappend(ridges, ridge);
|
|---|
| 3591 | }
|
|---|
| 3592 | facet->visitid= qh visit_id-1;
|
|---|
| 3593 | } /* vertexridges_facet */
|
|---|
| 3594 |
|
|---|
| 3595 | /*-<a href="qh-merge.htm#TOC"
|
|---|
| 3596 | >-------------------------------</a><a name="willdelete">-</a>
|
|---|
| 3597 |
|
|---|
| 3598 | qh_willdelete( facet, replace )
|
|---|
| 3599 | moves facet to visible list
|
|---|
| 3600 | sets facet->f.replace to replace (may be NULL)
|
|---|
| 3601 |
|
|---|
| 3602 | returns:
|
|---|
| 3603 | bumps qh.num_visible
|
|---|
| 3604 | */
|
|---|
| 3605 | void qh_willdelete(facetT *facet, facetT *replace) {
|
|---|
| 3606 |
|
|---|
| 3607 | qh_removefacet(facet);
|
|---|
| 3608 | qh_prependfacet(facet, &qh visible_list);
|
|---|
| 3609 | qh num_visible++;
|
|---|
| 3610 | facet->visible= True;
|
|---|
| 3611 | facet->f.replace= replace;
|
|---|
| 3612 | } /* willdelete */
|
|---|
| 3613 |
|
|---|
| 3614 | #else /* qh_NOmerge */
|
|---|
| 3615 | void qh_premerge(vertexT *apex, realT maxcentrum, realT maxangle) {
|
|---|
| 3616 | }
|
|---|
| 3617 | void qh_postmerge(const char *reason, realT maxcentrum, realT maxangle,
|
|---|
| 3618 | boolT vneighbors) {
|
|---|
| 3619 | }
|
|---|
| 3620 | boolT qh_checkzero(boolT testall) {
|
|---|
| 3621 | }
|
|---|
| 3622 | #endif /* qh_NOmerge */
|
|---|
| 3623 |
|
|---|
