41 if (tail ==
qh newfacet_list)
42 qh newfacet_list= facet;
43 if (tail ==
qh facet_next)
53 trace4((
qh ferr, 4044,
"qh_appendfacet: append f%d to facet_list\n", facet->
id));
75 if (tail ==
qh newvertex_list)
76 qh newvertex_list= vertex;
83 qh vertex_list= vertex;
86 trace4((
qh ferr, 4045,
"qh_appendvertex: append v%d to vertex_list\n", vertex->
id));
130 facetT *newfacet= NULL, *neighbor, **neighborp, *horizon, *visible;
134 trace3((
qh ferr, 3012,
"qh_attachnewfacets: delete interior ridges\n"));
137 visible->visitid=
qh visit_id;
138 if (visible->ridges) {
141 if (neighbor->visitid ==
qh visit_id
142 || (!neighbor->visible && neighbor->simplicial)) {
143 if (!neighbor->visible)
153 trace1((
qh ferr, 1017,
"qh_attachnewfacets: attach horizon facets to new facets\n"));
156 if (horizon->simplicial) {
159 if (neighbor->visible) {
162 SETindex_(horizon->neighbors, neighbor))) {
171 visible->f.replace= newfacet;
174 qh_fprintf(
qh ferr, 6102,
"qhull internal error (qh_attachnewfacets): couldn't find visible facet for horizon f%d of newfacet f%d\n",
175 horizon->id, newfacet->
id);
180 if (neighbor->visible) {
181 neighbor->f.replace= newfacet;
183 SETindex_(horizon->neighbors, neighbor));
189 if (ridge->
top == horizon)
192 ridge->
top= newfacet;
195 if (
qh PRINTstatistics) {
197 if (!visible->f.replace)
227 if ((allerror && dist > -
qh DISTround)|| (!allerror && dist >= 0.0)) {
230 trace0((
qh ferr, 19,
"qh_checkflipped: facet f%d is flipped, distance= %6.12g during p%d\n",
231 facet->
id, dist,
qh furthest_id));
250 trace4((
qh ferr, 4046,
"qh_delfacet: delete f%d\n", facet->
id));
251 if (facet ==
qh tracefacet)
253 if (facet ==
qh GOODclosest)
254 qh GOODclosest= NULL;
293 facetT *visible, *nextfacet;
297 trace1((
qh ferr, 1018,
"qh_deletevisible: delete %d visible facets and %d vertices\n",
298 qh num_visible, numdel));
299 for (visible=
qh visible_list; visible && visible->
visible;
300 visible= nextfacet) {
301 nextfacet= visible->
next;
305 if (numvisible !=
qh num_visible) {
306 qh_fprintf(
qh ferr, 6103,
"qhull internal error (qh_deletevisible): qh num_visible %d is not number of visible facets %d\n",
307 qh num_visible, numvisible);
344 int *skipA,
int *skipB,
int prepend) {
346 int dim=
qh hull_dim, i, j;
347 facetT **neighborsA, **neighborsB;
352 if (facetB == *neighborsA++)
354 else if (facetB == *neighborsA++)
356 else if (facetB == *neighborsA++)
359 for (i=3; i < dim; i++) {
360 if (facetB == *neighborsA++) {
366 if (facetA == *neighborsB++)
368 else if (facetA == *neighborsB++)
370 else if (facetA == *neighborsB++)
373 for (j=3; j < dim; j++) {
374 if (facetA == *neighborsB++) {
380 if (i >= dim || j >= dim) {
381 qh_fprintf(
qh ferr, 6104,
"qhull internal error (qh_facetintersect): f%d or f%d not in others neighbors\n",
382 facetA->
id, facetB->
id);
386 trace4((
qh ferr, 4047,
"qh_facetintersect: f%d skip %d matches f%d skip %d\n",
387 facetA->
id, *skipA, facetB->
id, *skipB));
405 int qh_gethash(
int hashsize,
setT *
set,
int size,
int firstindex,
void *skipelem) {
411 #pragma warning( push) 412 #pragma warning( disable : 4311) 415 switch (size-firstindex) {
444 hash ^= (elem << i) + (elem >> (32-i));
453 qh_fprintf(
qh ferr, 6202,
"qhull internal error: negative hashsize %d passed to qh_gethash [poly.c]\n", hashsize);
456 result= (unsigned)hash;
457 result %= (unsigned)hashsize;
461 #pragma warning( pop) 491 newfacet->
toporient= (
unsigned char)toporient;
566 facetT *neighbor, *newfacet= NULL, *samecycle;
582 toporient= (ridge->
top == visible);
590 if (!neighbor->
seen) {
603 if (neighbor->
seen) {
605 qh_fprintf(
qh ferr, 6105,
"qhull internal error (qh_makenew_nonsimplicial): simplicial f%d sharing two ridges with f%d\n",
606 neighbor->
id, visible->
id);
619 ridge->
top= newfacet;
623 trace4((
qh ferr, 4048,
"qh_makenew_nonsimplicial: created facet f%d from v%d and r%d of horizon f%d\n",
624 newfacet->
id, apex->
id, ridgeid, neighbor->
id));
661 facetT *neighbor, **neighborp, *newfacet= NULL;
663 boolT flip, toporient;
664 int horizonskip= 0, visibleskip= 0;
670 flip= ((horizonskip & 0x1) ^ (visibleskip & 0x1));
672 toporient= horizonskip & 0x1;
674 toporient= (horizonskip & 0x1) ^ 0x1;
677 if (neighbor->
coplanar && (
qh PREmerge ||
qh MERGEexact)) {
685 trace4((
qh ferr, 4049,
"qh_makenew_simplicial: create facet f%d top %d from v%d and horizon f%d skip %d top %d and visible f%d skip %d, flip? %d\n",
686 newfacet->
id, toporient, apex->
id, neighbor->
id, horizonskip,
687 neighbor->
toporient, visible->
id, visibleskip, flip));
728 facetT *facet, *matchfacet;
733 trace4((
qh ferr, 4050,
"qh_matchneighbor: newfacet f%d skip %d hash %d hashcount %d\n",
734 newfacet->
id, newskip, hash, *hashcount));
737 scan= (++scan >= hashsize ? 0 : scan)) {
738 if (facet == newfacet) {
747 qh_fprintf(
qh ferr, 6106,
"qhull precision error: Vertex sets are the same for f%d and f%d. Can not force output.\n",
748 facet->
id, newfacet->
id);
753 if (ismatch && !matchfacet) {
757 trace4((
qh ferr, 4051,
"qh_matchneighbor: f%d skip %d matched with new f%d skip %d\n",
758 facet->
id, skip, newfacet->
id, newskip));
761 if (!
qh PREmerge && !
qh MERGEexact) {
763 qh_fprintf(
qh ferr, 6107,
"qhull precision error: facets f%d, f%d and f%d meet at a ridge with more than 2 neighbors. Can not continue.\n",
783 qh_fprintf(
qh ferr, 6260,
"qhull internal error (qh_matchneighbor): matchfacet f%d is in f%d neighbors but not vice versa. Can not continue.\n",
784 matchfacet->
id, facet->
id);
795 trace4((
qh ferr, 4052,
"qh_matchneighbor: new f%d skip %d duplicates ridge for f%d skip %d matching f%d ismatch %d at hash %d\n",
796 newfacet->
id, newskip, facet->
id, skip,
805 trace4((
qh ferr, 4053,
"qh_matchneighbor: no match for f%d skip %d at hash %d\n",
806 newfacet->
id, newskip, hash));
842 int numnew=0, hashcount=0, newskip;
843 facetT *newfacet, *neighbor;
844 int dim=
qh hull_dim, hashsize, neighbor_i, neighbor_n;
847 int facet_i, facet_n, numfree= 0;
851 trace1((
qh ferr, 1019,
"qh_matchnewfacets: match neighbors for new facets.\n"));
856 neighbors->
e[neighbors->
maxsize].
i= dim+1;
865 for (newskip=1; newskip<
qh hull_dim; newskip++)
875 for (k=1; k <
qh hull_dim; k++) {
880 if (facet == newfacet)
883 if (count != hashcount) {
884 qh_fprintf(
qh ferr, 8088,
"qh_matchnewfacets: after adding facet %d, hashcount %d != count %d\n",
885 newfacet->
id, hashcount, count);
904 qh_fprintf(
qh ferr, 6108,
"qhull internal error (qh_matchnewfacets): %d neighbors did not match up\n",
910 if (
qh IStracing >= 2) {
915 qh_fprintf(
qh ferr, 8089,
"qh_matchnewfacets: %d new facets, %d unused hash entries . hashsize %d\n",
920 if (
qh PREmerge ||
qh MERGEexact) {
921 if (
qh IStracing >= 4)
927 }
else if (
qh FORCEoutput)
953 setT *verticesB,
int *skipB,
boolT *same) {
954 vertexT **elemAp, **elemBp, **skipBp=NULL, **skipAp;
959 do if (elemAp != skipAp) {
960 while (*elemAp != *elemBp++) {
965 }
while (*(++elemAp));
969 *same= !((skipA & 0x1) ^ (*skipB & 0x1));
970 trace4((
qh ferr, 4054,
"qh_matchvertices: matched by skip %d(v%d) and skip %d(v%d) same? %d\n",
971 skipA, (*skipAp)->id, *skipB, (*(skipBp-1))->id, *same));
990 memset((
char *)facet, (
size_t)0,
sizeof(
facetT));
991 if (
qh facet_id ==
qh tracefacet_id)
992 qh tracefacet= facet;
993 facet->id=
qh facet_id++;
995 #if !qh_COMPUTEfurthest 996 facet->furthestdist= 0.0;
999 if (
qh FORCEoutput &&
qh APPROXhull)
1000 facet->maxoutside=
qh MINoutside;
1002 facet->maxoutside=
qh DISTround;
1004 facet->simplicial=
True;
1006 facet->newfacet=
True;
1007 trace4((
qh ferr, 4055,
"qh_newfacet: created facet f%d\n", facet->id));
1023 memset((
char *)ridge, (
size_t)0,
sizeof(
ridgeT));
1025 if (
qh ridge_id == UINT_MAX) {
1027 qhull warning: more than 2^32 ridges. Qhull results are OK. Since the ridge ID wraps around to 0, two ridges may have the same identifier.\n");
1029 ridge->id=
qh ridge_id++;
1030 trace4((
qh ferr, 4056,
"qh_newridge: created ridge r%d\n", ridge->id));
1058 else if (point ==
qh interior_point)
1060 else if (point >=
qh first_point
1061 && point <
qh first_point +
qh num_points *
qh hull_dim) {
1063 id= offset /
qh hull_dim;
1065 id +=
qh num_points;
1087 if (facet ==
qh newfacet_list)
1088 qh newfacet_list= next;
1089 if (facet ==
qh facet_next)
1090 qh facet_next= next;
1091 if (facet ==
qh visible_list)
1092 qh visible_list= next;
1094 previous->
next= next;
1097 qh facet_list= next;
1098 qh facet_list->previous= NULL;
1101 trace4((
qh ferr, 4057,
"qh_removefacet: remove f%d from facet_list\n", facet->
id));
1118 if (vertex ==
qh newvertex_list)
1119 qh newvertex_list= next;
1121 previous->
next= next;
1124 qh vertex_list= vertex->
next;
1125 qh vertex_list->previous= NULL;
1128 trace4((
qh ferr, 4058,
"qh_removevertex: remove v%d from vertex_list\n", vertex->
id));
1156 facetT *newfacet= NULL, *neighbor, **neighborp, *visible;
1159 trace3((
qh ferr, 3013,
"qh_updatevertices: delete interior vertices and update vertex->neighbors\n"));
1160 if (
qh VERTEXneighbors) {
1163 if (neighbor->visible)
1176 if (!neighbor->visible)
1184 trace2((
qh ferr, 2041,
"qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
1196 trace2((
qh ferr, 2042,
"qh_updatevertices: delete vertex p%d(v%d) in f%d\n",
boolT qh_checkflipped(facetT *facet, realT *distp, boolT allerror)
facetT * qh_newfacet(void)
void qh_deletevisible(void)
setT * qh_facetintersect(facetT *facetA, facetT *facetB, int *skipA, int *skipB, int prepend)
void qh_settruncate(setT *set, int size)
#define otherfacet_(ridge, facet)
void qh_checkflipped_all(facetT *facetlist)
void qh_addhash(void *newelem, setT *hashtable, int hashsize, int hash)
#define FOREACHvertex_(vertices)
void qh_removefacet(facetT *facet)
void qh_setcompact(setT *set)
void qh_setreplace(setT *set, void *oldelem, void *newelem)
#define SETfirstt_(set, type)
#define FORALLvertex_(vertexlist)
#define qh_memalloc_(insize, freelistp, object, type)
void qh_fprintf(FILE *fp, int msgcode, const char *fmt,...)
void qh_removevertex(vertexT *vertex)
void qh_precision(const char *reason)
facetT * qh_makenewfacet(setT *vertices, boolT toporient, facetT *horizon)
void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall)
#define FORALLfacet_(facetlist)
void qh_delvertex(vertexT *vertex)
int qh_setindex(setT *set, void *atelem)
void qh_printhashtable(FILE *fp)
#define qh_DUPLICATEridge
void qh_appendfacet(facetT *facet)
void qh_attachnewfacets(void)
void qh_delfacet(facetT *facet)
boolT qh_matchvertices(int firstindex, setT *verticesA, int skipA, setT *verticesB, int *skipB, boolT *same)
facetT * qh_makenew_nonsimplicial(facetT *visible, vertexT *apex, int *numnew)
#define FOREACHridge_(ridges)
void qh_setappend_set(setT **setp, setT *setA)
int qh_newhashtable(int newsize)
void qh_matchneighbor(facetT *newfacet, int newskip, int hashsize, int *hashcount)
#define FOREACHfacet_i_(facets)
void qh_errexit2(int exitcode, facetT *facet, facetT *otherfacet)
#define SETelemaddr_(set, n, type)
setT * qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend)
facetT * qh_makenew_simplicial(facetT *visible, vertexT *apex, int *numnew)
void * qh_setdelnth(setT *set, int nth)
void qh_setfree(setT **setp)
#define FOREACHneighbor_(facet)
void qh_matchduplicates(facetT *atfacet, int atskip, int hashsize, int *hashcount)
#define SETelemt_(set, n, type)
#define SETindex_(set, elem)
void qh_setappend(setT **setp, void *newelem)
#define qh_memfree_(object, insize, freelistp)
void qh_makenewplanes(void)
void qh_memfree(void *object, int insize)
void qh_appendvertex(vertexT *vertex)
void * qh_setdel(setT *set, void *oldelem)
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge)
void qh_matchnewfacets(void)
int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB)
int qh_pointid(pointT *point)
ridgeT * qh_newridge(void)
#define FORALLvisible_facets
void qh_updatevertices(void)
void qh_distplane(pointT *point, facetT *facet, realT *dist)
int qh_setsize(setT *set)
setT * qh_setnew(int setsize)
#define SETaddr_(set, type)
#define FOREACHneighbor_i_(facet)
int qh_gethash(int hashsize, setT *set, int size, int firstindex, void *skipelem)
#define minimize_(minval, val)
void qh_setfacetplane(facetT *facet)