aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/qhull/libqhull_r/libqhull_r.h
blob: 1f476b33ea2591a030903d3f9c6d84c7e48549a3 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
/*<html><pre>  -<a                             href="qh-qhull_r.htm"
  >-------------------------------</a><a name="TOP">-</a>

   libqhull_r.h
   user-level header file for using qhull.a library

   see qh-qhull_r.htm, qhull_ra.h

   Copyright (c) 1993-2020 The Geometry Center.
   $Id: //main/2019/qhull/src/libqhull_r/libqhull_r.h#16 $$Change: 3037 $
   $DateTime: 2020/09/03 17:28:32 $$Author: bbarber $

   includes function prototypes for libqhull_r.c, geom_r.c, global_r.c, io_r.c, user_r.c

   use mem_r.h for mem_r.c
   use qset_r.h for qset_r.c

   see unix_r.c for an example of using libqhull_r.h

   recompile qhull if you change this file
*/

#ifndef qhDEFlibqhull
#define qhDEFlibqhull 1

/*=========================== -included files ==============*/

/* user_r.h first for QHULL_CRTDBG */
#include "user_r.h"      /* user definable constants (e.g., realT). */

#include "mem_r.h"   /* Needed for qhT in libqhull_r.h */
#include "qset_r.h"   /* Needed for QHULL_LIB_CHECK */
/* include stat_r.h after defining boolT.  Needed for qhT in libqhull_r.h */

#include <setjmp.h>
#include <float.h>
#include <limits.h>
#include <time.h>
#include <stdio.h>

#ifndef __STDC__
#ifndef __cplusplus
#if     !defined(_MSC_VER)
#error  Neither __STDC__ nor __cplusplus is defined.  Please use strict ANSI C or C++ to compile
#error  Qhull.  You may need to turn off compiler extensions in your project configuration.  If
#error  your compiler is a standard C compiler, you can delete this warning from libqhull_r.h
#endif
#endif
#endif

/*============ constants and basic types ====================*/

extern const char qh_version[]; /* defined in global_r.c */
extern const char qh_version2[]; /* defined in global_r.c */

/*-<a                             href="qh-geom_r.htm#TOC"
  >--------------------------------</a><a name="coordT">-</a>

  coordT
    coordinates and coefficients are stored as realT (i.e., double)

  notes:
    Qhull works well if realT is 'float'.  If so joggle (QJ) is not effective.

    Could use 'float' for data and 'double' for calculations (realT vs. coordT)
      This requires many type casts, and adjusted error bounds.
      Also C compilers may do expressions in double anyway.
*/
#define coordT realT

/*-<a                             href="qh-geom_r.htm#TOC"
  >--------------------------------</a><a name="pointT">-</a>

  pointT
    a point is an array of coordinates, usually qh.hull_dim
    qh_pointid returns
      qh_IDnone if point==0 or qh is undefined
      qh_IDinterior for qh.interior_point
      qh_IDunknown if point is neither in qh.first_point... nor qh.other_points

  notes:
    qh.STOPcone and qh.STOPpoint assume that qh_IDunknown==-1 (other negative numbers indicate points)
    qh_IDunknown is also returned by getid_() for unknown facet, ridge, or vertex
*/
#define pointT coordT
typedef enum
{
    qh_IDnone= -3, qh_IDinterior= -2, qh_IDunknown= -1
}
qh_pointT;

/*-<a                             href="qh-qhull_r.htm#TOC"
  >--------------------------------</a><a name="flagT">-</a>

  flagT
    Boolean flag as a bit
*/
#define flagT unsigned int

/*-<a                             href="qh-qhull_r.htm#TOC"
  >--------------------------------</a><a name="boolT">-</a>

  boolT
    boolean value, either True or False

  notes:
    needed for portability
    Use qh_False/qh_True as synonyms
*/
#define boolT unsigned int
#ifdef False
#undef False
#endif
#ifdef True
#undef True
#endif
#define False 0
#define True 1
#define qh_False 0
#define qh_True 1

#include "stat_r.h"  /* needs boolT */

/*-<a                             href="qh-qhull_r.htm#TOC"
  >--------------------------------</a><a name="CENTERtype">-</a>

  qh_CENTER
    to distinguish facet->center
*/
typedef enum
{
    qh_ASnone= 0,    /* If not MERGING and not VORONOI */
    qh_ASvoronoi,    /* Set by qh_clearcenters on qh_prepare_output, or if not MERGING and VORONOI */
    qh_AScentrum     /* If MERGING (assumed during merging) */
}
qh_CENTER;

/*-<a                             href="qh-qhull_r.htm#TOC"
  >--------------------------------</a><a name="qh_PRINT">-</a>

  qh_PRINT
    output formats for printing (qh.PRINTout).
    'Fa' 'FV' 'Fc' 'FC'


   notes:
   some of these names are similar to qhT names.  The similar names are only
   used in switch statements in qh_printbegin() etc.
*/
typedef enum {qh_PRINTnone= 0,
  qh_PRINTarea, qh_PRINTaverage,           /* 'Fa' 'FV' 'Fc' 'FC' */
  qh_PRINTcoplanars, qh_PRINTcentrums,
  qh_PRINTfacets, qh_PRINTfacets_xridge,   /* 'f' 'FF' 'G' 'FI' 'Fi' 'Fn' */
  qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors,
  qh_PRINTnormals, qh_PRINTouter, qh_PRINTmaple, /* 'n' 'Fo' 'i' 'm' 'Fm' 'FM', 'o' */
  qh_PRINTincidences, qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff,
  qh_PRINToptions, qh_PRINTpointintersect, /* 'FO' 'Fp' 'FP' 'p' 'FQ' 'FS' */
  qh_PRINTpointnearest, qh_PRINTpoints, qh_PRINTqhull, qh_PRINTsize,
  qh_PRINTsummary, qh_PRINTtriangles,      /* 'Fs' 'Ft' 'Fv' 'FN' 'Fx' */
  qh_PRINTvertices, qh_PRINTvneighbors, qh_PRINTextremes,
  qh_PRINTEND} qh_PRINT;

/*-<a                             href="qh-qhull_r.htm#TOC"
  >--------------------------------</a><a name="qh_ALL">-</a>

  qh_ALL
    argument flag for selecting everything
*/
#define qh_ALL      True
#define qh_NOupper  True      /* argument for qh_findbest */
#define qh_IScheckmax  True   /* argument for qh_findbesthorizon */
#define qh_ISnewfacets  True  /* argument for qh_findbest */
#define qh_RESETvisible  True /* argument for qh_resetlists */

/*-<a                             href="qh-qhull_r.htm#TOC"
  >--------------------------------</a><a name="qh_ERR">-</a>

  qh_ERR...
    Qhull exit status codes, for indicating errors
    See: MSG_ERROR (6000) and MSG_WARNING (7000) [user_r.h]
*/
#define qh_ERRnone  0    /* no error occurred during qhull */
#define qh_ERRinput 1    /* input inconsistency */
#define qh_ERRsingular 2 /* singular input data, calls qh_printhelp_singular */
#define qh_ERRprec  3    /* precision error, calls qh_printhelp_degenerate */
#define qh_ERRmem   4    /* insufficient memory, matches mem_r.h */
#define qh_ERRqhull 5    /* internal error detected, matches mem_r.h, calls qh_printhelp_internal */
#define qh_ERRother 6    /* other error detected */
#define qh_ERRtopology 7 /* topology error, maybe due to nearly adjacent vertices, calls qh_printhelp_topology */
#define qh_ERRwide 8     /* wide facet error, maybe due to nearly adjacent vertices, calls qh_printhelp_wide */
#define qh_ERRdebug 9    /* qh_errexit from debugging code */

/*-<a                             href="qh-qhull_r.htm#TOC"
>--------------------------------</a><a name="qh_FILEstderr">-</a>

qh_FILEstderr
Fake stderr to distinguish error output from normal output
For C++ interface.  Must redefine qh_fprintf_qhull
*/
#define qh_FILEstderr ((FILE *)1)

/* ============ -structures- ====================
   each of the following structures is defined by a typedef
   all realT and coordT fields occur at the beginning of a structure
        (otherwise space may be wasted due to alignment)
   define all flags together and pack into 32-bit number

   DEFqhT and DEFsetT are likewise defined in mem_r.h, qset_r.h, and stat_r.h
*/

typedef struct vertexT vertexT;
typedef struct ridgeT ridgeT;
typedef struct facetT facetT;

#ifndef DEFqhT
#define DEFqhT 1
typedef struct qhT qhT;          /* defined below */
#endif

#ifndef DEFsetT
#define DEFsetT 1
typedef struct setT setT;        /* defined in qset_r.h */
#endif

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="facetT">-</a>

  facetT
    defines a facet

  notes:
   qhull() generates the hull as a list of facets.

  topological information:
    f.previous,next     doubly-linked list of facets, next is always defined
    f.vertices          set of vertices
    f.ridges            set of ridges
    f.neighbors         set of neighbors
    f.toporient         True if facet has top-orientation (else bottom)

  geometric information:
    f.offset,normal     hyperplane equation
    f.maxoutside        offset to outer plane -- all points inside
    f.center            centrum for testing convexity or Voronoi center for output
    f.simplicial        True if facet is simplicial
    f.flipped           True if facet does not include qh.interior_point

  for constructing hull:
    f.visible           True if facet on list of visible facets (will be deleted)
    f.newfacet          True if facet on list of newly created facets
    f.coplanarset       set of points coplanar with this facet
                        (includes near-inside points for later testing)
    f.outsideset        set of points outside of this facet
    f.furthestdist      distance to furthest point of outside set
    f.visitid           marks visited facets during a loop
    f.replace           replacement facet for to-be-deleted, visible facets
    f.samecycle,newcycle cycle of facets for merging into horizon facet

  see below for other flags and fields
*/
/* QhullFacet.cpp -- Update static initializer list for s_empty_facet if add or remove fields */
struct facetT {
#if !qh_COMPUTEfurthest
  coordT   furthestdist;/* distance to furthest point of outsideset */
#endif
#if qh_MAXoutside
  coordT   maxoutside;  /* max computed distance of point to facet
                        Before QHULLfinished this is an approximation
                        since maxdist not always set for qh_mergefacet
                        Actual outer plane is +DISTround and
                        computed outer plane is +2*DISTround.
                        Initial maxoutside is qh.DISTround, otherwise distance tests need to account for DISTround */
#endif
  coordT   offset;      /* exact offset of hyperplane from origin */
  coordT  *normal;      /* normal of hyperplane, hull_dim coefficients */
                        /*   if f.tricoplanar, shared with a neighbor */
  union {               /* in order of testing */
   realT   area;        /* area of facet, only in io_r.c if  f.isarea */
   facetT *replace;     /* replacement facet for qh.NEWfacets with f.visible
                             NULL if qh_mergedegen_redundant, interior, or !NEWfacets */
   facetT *samecycle;   /* cycle of facets from the same visible/horizon intersection,
                             if ->newfacet */
   facetT *newcycle;    /*  in horizon facet, current samecycle of new facets */
   facetT *trivisible;  /* visible facet for ->tricoplanar facets during qh_triangulate() */
   facetT *triowner;    /* owner facet for ->tricoplanar, !isarea facets w/ ->keepcentrum */
  }f;
  coordT  *center;      /* set according to qh.CENTERtype */
                        /*   qh_ASnone:    no center (not MERGING) */
                        /*   qh_AScentrum: centrum for testing convexity (qh_getcentrum) */
                        /*                 assumed qh_AScentrum while merging */
                        /*   qh_ASvoronoi: Voronoi center (qh_facetcenter) */
                        /* after constructing the hull, it may be changed (qh_clearcenter) */
                        /* if tricoplanar and !keepcentrum, shared with a neighbor */
  facetT  *previous;    /* previous facet in the facet_list or NULL, for C++ interface */
  facetT  *next;        /* next facet in the facet_list or facet_tail */
  setT    *vertices;    /* vertices for this facet, inverse sorted by ID
                           if simplicial, 1st vertex was apex/furthest
                           qh_reduce_vertices removes extraneous vertices via qh_remove_extravertices
                           if f.visible, vertices may be on qh.del_vertices */
  setT    *ridges;      /* explicit ridges for nonsimplicial facets or nonsimplicial neighbors.
                           For simplicial facets, neighbors define the ridges
                           qh_makeridges() converts simplicial facets by creating ridges prior to merging
                           If qh.NEWtentative, new facets have horizon ridge, but not vice versa
                           if f.visible && qh.NEWfacets, ridges is empty */
  setT    *neighbors;   /* neighbors of the facet.  Neighbors may be f.visible
                           If simplicial, the kth neighbor is opposite the kth vertex and the
                           first neighbor is the horizon facet for the first vertex.
                           dupridges marked by qh_DUPLICATEridge (0x01) and qh_MERGEridge (0x02)
                           if f.visible && qh.NEWfacets, neighbors is empty */
  setT    *outsideset;  /* set of points outside this facet
                           if non-empty, last point is furthest
                           if NARROWhull, includes coplanars (less than qh.MINoutside) for partitioning*/
  setT    *coplanarset; /* set of points coplanar with this facet
                           >= qh.min_vertex and <= facet->max_outside
                           a point is assigned to the furthest facet
                           if non-empty, last point is furthest away */
  unsigned int visitid; /* visit_id, for visiting all neighbors,
                           all uses are independent */
  unsigned int id;      /* unique identifier from qh.facet_id, 1..qh.facet_id, 0 is sentinel, printed as 'f%d' */
  unsigned int nummerge:9; /* number of merges */
#define qh_MAXnummerge 511 /* 2^9-1 */
                        /* 23 flags (at most 23 due to nummerge), printed by "flags:" in io_r.c */
  flagT    tricoplanar:1; /* True if TRIangulate and simplicial and coplanar with a neighbor */
                          /*   all tricoplanars share the same apex */
                          /*   all tricoplanars share the same ->center, ->normal, ->offset, ->maxoutside */
                          /*     ->keepcentrum is true for the owner.  It has the ->coplanareset */
                          /*   if ->degenerate, does not span facet (one logical ridge) */
                          /*   during qh_triangulate, f.trivisible points to original facet */
  flagT    newfacet:1;  /* True if facet on qh.newfacet_list (new/qh.first_newfacet or merged) */
  flagT    visible:1;   /* True if visible facet (will be deleted) */
  flagT    toporient:1; /* True if created with top orientation
                           after merging, use ridge orientation */
  flagT    simplicial:1;/* True if simplicial facet, ->ridges may be implicit */
  flagT    seen:1;      /* used to perform operations only once, like visitid */
  flagT    seen2:1;     /* used to perform operations only once, like visitid */
  flagT    flipped:1;   /* True if facet is flipped */
  flagT    upperdelaunay:1; /* True if facet is upper envelope of Delaunay triangulation */
  flagT    notfurthest:1; /* True if last point of outsideset is not furthest */

/*-------- flags primarily for output ---------*/
  flagT    good:1;      /* True if a facet marked good for output */
  flagT    isarea:1;    /* True if facet->f.area is defined */

/*-------- flags for merging ------------------*/
  flagT    dupridge:1;  /* True if facet has one or more dupridge in a new facet (qh_matchneighbor),
                             a dupridge has a subridge shared by more than one new facet */
  flagT    mergeridge:1; /* True if facet or neighbor has a qh_MERGEridge (qh_mark_dupridges)
                            ->normal defined for mergeridge and mergeridge2 */
  flagT    mergeridge2:1; /* True if neighbor has a qh_MERGEridge (qh_mark_dupridges) */
  flagT    coplanarhorizon:1;  /* True if horizon facet is coplanar at last use */
  flagT     mergehorizon:1; /* True if will merge into horizon (its first neighbor w/ f.coplanarhorizon). */
  flagT     cycledone:1;/* True if mergecycle_all already done */
  flagT    tested:1;    /* True if facet convexity has been tested (false after merge */
  flagT    keepcentrum:1; /* True if keep old centrum after a merge, or marks owner for ->tricoplanar
                             Set by qh_updatetested if more than qh_MAXnewcentrum extra vertices
                             Set by qh_mergefacet if |maxdist| > qh.WIDEfacet */
  flagT    newmerge:1;  /* True if facet is newly merged for reducevertices */
  flagT    degenerate:1; /* True if facet is degenerate (degen_mergeset or ->tricoplanar) */
  flagT    redundant:1;  /* True if facet is redundant (degen_mergeset)
                         Maybe merge degenerate and redundant to gain another flag */
};


/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="ridgeT">-</a>

  ridgeT
    defines a ridge

  notes:
  a ridge is hull_dim-1 simplex between two neighboring facets.  If the
  facets are non-simplicial, there may be more than one ridge between
  two facets.  E.G. a 4-d hypercube has two triangles between each pair
  of neighboring facets.

  topological information:
    vertices            a set of vertices
    top,bottom          neighboring facets with orientation

  geometric information:
    tested              True if ridge is clearly convex
    nonconvex           True if ridge is non-convex
*/
/* QhullRidge.cpp -- Update static initializer list for s_empty_ridge if add or remove fields */
struct ridgeT {
  setT    *vertices;    /* vertices belonging to this ridge, inverse sorted by ID
                           NULL if a degen ridge (matchsame) */
  facetT  *top;         /* top facet for this ridge */
  facetT  *bottom;      /* bottom facet for this ridge
                        ridge oriented by odd/even vertex order and top/bottom */
  unsigned int id;      /* unique identifier.  Same size as vertex_id, printed as 'r%d' */
  flagT    seen:1;      /* used to perform operations only once */
  flagT    tested:1;    /* True when ridge is tested for convexity by centrum or opposite vertices */
  flagT    nonconvex:1; /* True if getmergeset detected a non-convex neighbor
                           only one ridge between neighbors may have nonconvex */
  flagT    mergevertex:1; /* True if pending qh_appendvertexmerge due to
                             qh_maybe_duplicateridge or qh_maybe_duplicateridges
                             disables check for duplicate vertices in qh_checkfacet */
  flagT    mergevertex2:1; /* True if qh_drop_mergevertex of MRGvertices, printed but not used */
  flagT    simplicialtop:1; /* True if top was simplicial (original vertices) */
  flagT    simplicialbot:1; /* True if bottom was simplicial (original vertices)
                             use qh_test_centrum_merge if top and bot, need to retest since centrum may change */
};

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="vertexT">-</a>

  vertexT
     defines a vertex

  topological information:
    next,previous       doubly-linked list of all vertices
    neighbors           set of adjacent facets (only if qh.VERTEXneighbors)

  geometric information:
    point               array of DIM3 coordinates
*/
/* QhullVertex.cpp -- Update static initializer list for s_empty_vertex if add or remove fields */
struct vertexT {
  vertexT *next;        /* next vertex in vertex_list or vertex_tail */
  vertexT *previous;    /* previous vertex in vertex_list or NULL, for C++ interface */
  pointT  *point;       /* hull_dim coordinates (coordT) */
  setT    *neighbors;   /* neighboring facets of vertex, qh_vertexneighbors()
                           initialized in io_r.c or after first merge
                           qh_update_vertices for qh_addpoint or qh_triangulate
                           updated by merges
                           qh_order_vertexneighbors by 2-d (orientation) 3-d (adjacency), n-d (f.visitid,id) */
  unsigned int id;      /* unique identifier, 1..qh.vertex_id,  0 for sentinel, printed as 'r%d' */
  unsigned int visitid; /* for use with qh.vertex_visit, size must match */
  flagT    seen:1;      /* used to perform operations only once */
  flagT    seen2:1;     /* another seen flag */
  flagT    deleted:1;   /* vertex will be deleted via qh.del_vertices */
  flagT    delridge:1;  /* vertex belonged to a deleted ridge, cleared by qh_reducevertices */
  flagT    newfacet:1;  /* true if vertex is in a new facet
                           vertex is on qh.newvertex_list and it has a facet on qh.newfacet_list
                           or vertex is on qh.newvertex_list due to qh_newvertices while merging
                           cleared by qh_resetlists */
  flagT    partitioned:1; /* true if deleted vertex has been partitioned */
};

/*======= -global variables -qh ============================*/

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh">-</a>

  qhT
   All global variables for qhull are in qhT.  It includes qhmemT, qhstatT, and rbox globals

   This version of Qhull is reentrant, but it is not thread-safe.

   Do not run separate threads on the same instance of qhT.

   QHULL_LIB_CHECK checks that a program and the corresponding
   qhull library were built with the same type of header files.

   QHULL_LIB_TYPE is QHULL_NON_REENTRANT, QHULL_QH_POINTER, or QHULL_REENTRANT
*/

#define QHULL_NON_REENTRANT 0
#define QHULL_QH_POINTER 1
#define QHULL_REENTRANT 2

#define QHULL_LIB_TYPE QHULL_REENTRANT

#define QHULL_LIB_CHECK qh_lib_check(QHULL_LIB_TYPE, sizeof(qhT), sizeof(vertexT), sizeof(ridgeT), sizeof(facetT), sizeof(setT), sizeof(qhmemT));
#define QHULL_LIB_CHECK_RBOX qh_lib_check(QHULL_LIB_TYPE, sizeof(qhT), sizeof(vertexT), sizeof(ridgeT), sizeof(facetT), 0, 0);

struct qhT {

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-const">-</a>

  qh constants
    configuration flags and constants for Qhull

  notes:
    The user configures Qhull by defining flags.  They are
    copied into qh by qh_setflags().  qh-quick_r.htm#options defines the flags.
*/
  boolT ALLpoints;        /* true 'Qs' if search all points for initial simplex */
  boolT ALLOWshort;       /* true 'Qa' allow input with fewer or more points than coordinates */
  boolT ALLOWwarning;     /* true 'Qw' if allow option warnings */
  boolT ALLOWwide;        /* true 'Q12' if allow wide facets and wide dupridges, c.f. qh_WIDEmaxoutside */
  boolT ANGLEmerge;       /* true 'Q1' if sort potential merges by type/angle instead of type/distance  */
  boolT APPROXhull;       /* true 'Wn' if MINoutside set */
  realT MINoutside;       /*   Minimum distance for an outside point ('Wn' or 2*qh.MINvisible) */
  boolT ANNOTATEoutput;   /* true 'Ta' if annotate output with message codes */
  boolT ATinfinity;       /* true 'Qz' if point num_points-1 is "at-infinity"
                             for improving precision in Delaunay triangulations */
  boolT AVOIDold;         /* true 'Q4' if avoid old->new merges */
  boolT BESToutside;      /* true 'Qf' if partition points into best outsideset */
  boolT CDDinput;         /* true 'Pc' if input uses CDD format (1.0/offset first) */
  boolT CDDoutput;        /* true 'PC' if print normals in CDD format (offset first) */
  boolT CHECKduplicates;  /* true 'Q15' if qh_maybe_duplicateridges after each qh_mergefacet */
  boolT CHECKfrequently;  /* true 'Tc' if checking frequently */
  realT premerge_cos;     /*   'A-n'   cos_max when pre merging */
  realT postmerge_cos;    /*   'An'    cos_max when post merging */
  boolT DELAUNAY;         /* true 'd' or 'v' if computing DELAUNAY triangulation */
  boolT DOintersections;  /* true 'Gh' if print hyperplane intersections */
  int   DROPdim;          /* drops dim 'GDn' for 4-d -> 3-d output */
  boolT FLUSHprint;       /* true 'Tf' if flush after qh_fprintf for segfaults */
  boolT FORCEoutput;      /* true 'Po' if forcing output despite degeneracies */
  int   GOODpoint;        /* 'QGn' or 'QG-n' (n+1, n-1), good facet if visible from point n (or not) */
  pointT *GOODpointp;     /*   the actual point */
  boolT GOODthreshold;    /* true 'Pd/PD' if qh.lower_threshold/upper_threshold defined
                             set if qh.UPPERdelaunay (qh_initbuild)
                             false if qh.SPLITthreshold */
  int   GOODvertex;       /* 'QVn' or 'QV-n' (n+1, n-1), good facet if vertex for point n (or not) */
  pointT *GOODvertexp;     /*   the actual point */
  boolT HALFspace;        /* true 'Hn,n,n' if halfspace intersection */
  boolT ISqhullQh;        /* Set by Qhull.cpp on initialization */
  int   IStracing;        /* 'Tn' trace execution, 0=none, 1=least, 4=most, -1=events */
  int   KEEParea;         /* 'PAn' number of largest facets to keep */
  boolT KEEPcoplanar;     /* true 'Qc' if keeping nearest facet for coplanar points */
  boolT KEEPinside;       /* true 'Qi' if keeping nearest facet for inside points
                              set automatically if 'd Qc' */
  int   KEEPmerge;        /* 'PMn' number of facets to keep with most merges */
  realT KEEPminArea;      /* 'PFn' minimum facet area to keep */
  realT MAXcoplanar;      /* 'Un' max distance below a facet to be coplanar*/
  int   MAXwide;          /* 'QWn' max ratio for wide facet, otherwise error unless Q12-allow-wide */
  boolT MERGEexact;       /* true 'Qx' if exact merges (concave, degen, dupridge, flipped)
                             tested by qh_checkzero and qh_test_*_merge */
  boolT MERGEindependent; /* true if merging independent sets of coplanar facets. 'Q2' disables */
  boolT MERGING;          /* true if exact-, pre- or post-merging, with angle and centrum tests */
  realT   premerge_centrum;  /*   'C-n' centrum_radius when pre merging.  Default is round-off */
  realT   postmerge_centrum; /*   'Cn' centrum_radius when post merging.  Default is round-off */
  boolT MERGEpinched;     /* true 'Q14' if merging pinched vertices due to dupridge */
  boolT MERGEvertices;    /* true if merging redundant vertices, 'Q3' disables or qh.hull_dim > qh_DIMmergeVertex */
  realT MINvisible;       /* 'Vn' min. distance for a facet to be visible */
  boolT NOnarrow;         /* true 'Q10' if no special processing for narrow distributions */
  boolT NOnearinside;     /* true 'Q8' if ignore near-inside points when partitioning, qh_check_points may fail */
  boolT NOpremerge;       /* true 'Q0' if no defaults for C-0 or Qx */
  boolT ONLYgood;         /* true 'Qg' if process points with good visible or horizon facets */
  boolT ONLYmax;          /* true 'Qm' if only process points that increase max_outside */
  boolT PICKfurthest;     /* true 'Q9' if process furthest of furthest points*/
  boolT POSTmerge;        /* true if merging after buildhull ('Cn' or 'An') */
  boolT PREmerge;         /* true if merging during buildhull ('C-n' or 'A-n') */
                        /* NOTE: some of these names are similar to qh_PRINT names */
  boolT PRINTcentrums;    /* true 'Gc' if printing centrums */
  boolT PRINTcoplanar;    /* true 'Gp' if printing coplanar points */
  int   PRINTdim;         /* print dimension for Geomview output */
  boolT PRINTdots;        /* true 'Ga' if printing all points as dots */
  boolT PRINTgood;        /* true 'Pg' if printing good facets
                             PGood set if 'd', 'PAn', 'PFn', 'PMn', 'QGn', 'QG-n', 'QVn', or 'QV-n' */
  boolT PRINTinner;       /* true 'Gi' if printing inner planes */
  boolT PRINTneighbors;   /* true 'PG' if printing neighbors of good facets */
  boolT PRINTnoplanes;    /* true 'Gn' if printing no planes */
  boolT PRINToptions1st;  /* true 'FO' if printing options to stderr */
  boolT PRINTouter;       /* true 'Go' if printing outer planes */
  boolT PRINTprecision;   /* false 'Pp' if not reporting precision problems */
  qh_PRINT PRINTout[qh_PRINTEND]; /* list of output formats to print */
  boolT PRINTridges;      /* true 'Gr' if print ridges */
  boolT PRINTspheres;     /* true 'Gv' if print vertices as spheres */
  boolT PRINTstatistics;  /* true 'Ts' if printing statistics to stderr */
  boolT PRINTsummary;     /* true 's' if printing summary to stderr */
  boolT PRINTtransparent; /* true 'Gt' if print transparent outer ridges */
  boolT PROJECTdelaunay;  /* true if DELAUNAY, no readpoints() and
                             need projectinput() for Delaunay in qh_init_B */
  int   PROJECTinput;     /* number of projected dimensions 'bn:0Bn:0' */
  boolT RANDOMdist;       /* true 'Rn' if randomly change distplane and setfacetplane */
  realT RANDOMfactor;     /*    maximum random perturbation */
  realT RANDOMa;          /*    qh_randomfactor is randr * RANDOMa + RANDOMb */
  realT RANDOMb;
  boolT RANDOMoutside;    /* true 'Qr' if select a random outside point */
  int   REPORTfreq;       /* 'TFn' buildtracing reports every n facets */
  int   REPORTfreq2;      /* tracemerging reports every REPORTfreq/2 facets */
  int   RERUN;            /* 'TRn' rerun qhull n times (qh.build_cnt) */
  int   ROTATErandom;     /* 'QRn' n<-1 random seed, n==-1 time is seed, n==0 random rotation by time, n>0 rotate input */
  boolT SCALEinput;       /* true 'Qbk' if scaling input */
  boolT SCALElast;        /* true 'Qbb' if scale last coord to max prev coord */
  boolT SETroundoff;      /* true 'En' if qh.DISTround is predefined */
  boolT SKIPcheckmax;     /* true 'Q5' if skip qh_check_maxout, qh_check_points may fail */
  boolT SKIPconvex;       /* true 'Q6' if skip convexity testing during pre-merge */
  boolT SPLITthresholds;  /* true 'Pd/PD' if upper_/lower_threshold defines a region
                               else qh.GOODthresholds
                               set if qh.DELAUNAY (qh_initbuild)
                               used only for printing (!for qh.ONLYgood) */
  int   STOPadd;          /* 'TAn' 1+n for stop after adding n vertices */
  int   STOPcone;         /* 'TCn' 1+n for stopping after cone for point n */
                          /*       also used by qh_build_withresart for err exit*/
  int   STOPpoint;        /* 'TVn' 'TV-n' 1+n for stopping after/before(-)
                                        adding point n */
  int   TESTpoints;       /* 'QTn' num of test points after qh.num_points.  Test points always coplanar. */
  boolT TESTvneighbors;   /*  true 'Qv' if test vertex neighbors at end */
  int   TRACElevel;       /* 'Tn' conditional IStracing level */
  int   TRACElastrun;     /*  qh.TRACElevel applies to last qh.RERUN */
  int   TRACEpoint;       /* 'TPn' start tracing when point n is a vertex, use qh_IDunknown (-1) after qh_buildhull and qh_postmerge */
  realT TRACEdist;        /* 'TWn' start tracing when merge distance too big */
  int   TRACEmerge;       /* 'TMn' start tracing before this merge */
  boolT TRIangulate;      /* true 'Qt' if triangulate non-simplicial facets */
  boolT TRInormals;       /* true 'Q11' if triangulate duplicates ->normal and ->center (sets Qt) */
  boolT UPPERdelaunay;    /* true 'Qu' if computing furthest-site Delaunay */
  boolT USEstdout;        /* true 'Tz' if using stdout instead of stderr */
  boolT VERIFYoutput;     /* true 'Tv' if verify output at end of qhull */
  boolT VIRTUALmemory;    /* true 'Q7' if depth-first processing in buildhull */
  boolT VORONOI;          /* true 'v' if computing Voronoi diagram, also sets qh.DELAUNAY */

  /*--------input constants ---------*/
  realT AREAfactor;       /* 1/(hull_dim-1)! for converting det's to area */
  boolT DOcheckmax;       /* true if calling qh_check_maxout (!qh.SKIPcheckmax && qh.MERGING) */
  char  *feasible_string;  /* feasible point 'Hn,n,n' for halfspace intersection */
  coordT *feasible_point;  /*    as coordinates, both malloc'd */
  boolT GETarea;          /* true 'Fa', 'FA', 'FS', 'PAn', 'PFn' if compute facet area/Voronoi volume in io_r.c */
  boolT KEEPnearinside;   /* true if near-inside points in coplanarset */
  int   hull_dim;         /* dimension of hull, set by initbuffers */
  int   input_dim;        /* dimension of input, set by initbuffers */
  int   num_points;       /* number of input points */
  pointT *first_point;    /* array of input points, see POINTSmalloc */
  boolT POINTSmalloc;     /*   true if qh.first_point/num_points allocated */
  pointT *input_points;   /* copy of original qh.first_point for input points for qh_joggleinput */
  boolT input_malloc;     /* true if qh.input_points malloc'd */
  char  qhull_command[256];/* command line that invoked this program */
  int   qhull_commandsiz2; /*    size of qhull_command at qh_clear_outputflags */
  char  rbox_command[256]; /* command line that produced the input points */
  char  qhull_options[512];/* descriptive list of options */
  int   qhull_optionlen;  /*    length of last line */
  int   qhull_optionsiz;  /*    size of qhull_options at qh_build_withrestart */
  int   qhull_optionsiz2; /*    size of qhull_options at qh_clear_outputflags */
  int   run_id;           /* non-zero, random identifier for this instance of qhull */
  boolT VERTEXneighbors;  /* true if maintaining vertex neighbors */
  boolT ZEROcentrum;      /* true if 'C-0' or 'C-0 Qx' and not post-merging or 'A-n'.  Sets ZEROall_ok */
  realT *upper_threshold; /* don't print if facet->normal[k]>=upper_threshold[k]
                             must set either GOODthreshold or SPLITthreshold
                             if qh.DELAUNAY, default is 0.0 for upper envelope (qh_initbuild) */
  realT *lower_threshold; /* don't print if facet->normal[k] <=lower_threshold[k] */
  realT *upper_bound;     /* scale point[k] to new upper bound */
  realT *lower_bound;     /* scale point[k] to new lower bound
                             project if both upper_ and lower_bound == 0 */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-prec">-</a>

  qh precision constants
    precision constants for Qhull

  notes:
    qh_detroundoff [geom2_r.c] computes the maximum roundoff error for distance
    and other computations.  It also sets default values for the
    qh constants above.
*/
  realT ANGLEround;       /* max round off error for angles */
  realT centrum_radius;   /* max centrum radius for convexity ('Cn' + 2*qh.DISTround) */
  realT cos_max;          /* max cosine for convexity (roundoff added) */
  realT DISTround;        /* max round off error for distances, qh.SETroundoff ('En') overrides qh_distround */
  realT MAXabs_coord;     /* max absolute coordinate */
  realT MAXlastcoord;     /* max last coordinate for qh_scalelast */
  realT MAXoutside;       /* max target for qh.max_outside/f.maxoutside, base for qh_RATIO...
                             recomputed at qh_addpoint, unrelated to qh_MAXoutside */
  realT MAXsumcoord;      /* max sum of coordinates */
  realT MAXwidth;         /* max rectilinear width of point coordinates */
  realT MINdenom_1;       /* min. abs. value for 1/x */
  realT MINdenom;         /*    use divzero if denominator < MINdenom */
  realT MINdenom_1_2;     /* min. abs. val for 1/x that allows normalization */
  realT MINdenom_2;       /*    use divzero if denominator < MINdenom_2 */
  realT MINlastcoord;     /* min. last coordinate for qh_scalelast */
  realT *NEARzero;        /* hull_dim array for near zero in gausselim */
  realT NEARinside;       /* keep points for qh_check_maxout if close to facet */
  realT ONEmerge;         /* max distance for merging simplicial facets */
  realT outside_err;      /* application's epsilon for coplanar points
                             qh_check_bestdist() qh_check_points() reports error if point outside */
  realT WIDEfacet;        /* size of wide facet for skipping ridge in
                             area computation and locking centrum */
  boolT NARROWhull;       /* set in qh_initialhull if angle < qh_MAXnarrow */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-codetern">-</a>

  qh internal constants
    internal constants for Qhull
*/
  char qhull[sizeof("qhull")]; /* "qhull" for checking ownership while debugging */
  jmp_buf errexit;        /* exit label for qh_errexit, defined by setjmp() and NOerrexit */
  char    jmpXtra[40];    /* extra bytes in case jmp_buf is defined wrong by compiler */
  jmp_buf restartexit;    /* restart label for qh_errexit, defined by setjmp() and ALLOWrestart */
  char    jmpXtra2[40];   /* extra bytes in case jmp_buf is defined wrong by compiler*/
  FILE *  fin;            /* pointer to input file, init by qh_initqhull_start2 */
  FILE *  fout;           /* pointer to output file */
  FILE *  ferr;           /* pointer to error file */
  pointT *interior_point; /* center point of the initial simplex*/
  int     normal_size;    /* size in bytes for facet normals and point coords */
  int     center_size;    /* size in bytes for Voronoi centers */
  int     TEMPsize;       /* size for small, temporary sets (in quick mem) */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-lists">-</a>

  qh facet and vertex lists
    defines lists of facets, new facets, visible facets, vertices, and
    new vertices.  Includes counts, next ids, and trace ids.
  see:
    qh_resetlists()
*/
  facetT *facet_list;     /* first facet */
  facetT *facet_tail;     /* end of facet_list (dummy facet with id 0 and next==NULL) */
  facetT *facet_next;     /* next facet for buildhull()
                             previous facets do not have outside sets
                             NARROWhull: previous facets may have coplanar outside sets for qh_outcoplanar */
  facetT *newfacet_list;  /* list of new facets to end of facet_list
                             qh_postmerge sets newfacet_list to facet_list */
  facetT *visible_list;   /* list of visible facets preceding newfacet_list,
                             end of visible list if !facet->visible, same as newfacet_list
                             qh_findhorizon sets visible_list at end of facet_list
                             qh_willdelete prepends to visible_list
                             qh_triangulate appends mirror facets to visible_list at end of facet_list
                             qh_postmerge sets visible_list to facet_list
                             qh_deletevisible deletes the visible facets */
  int       num_visible;  /* current number of visible facets */
  unsigned int tracefacet_id; /* set at init, then can print whenever */
  facetT  *tracefacet;    /*   set in newfacet/mergefacet, undone in delfacet and qh_errexit */
  unsigned int traceridge_id; /* set at init, then can print whenever */
  ridgeT  *traceridge;    /*   set in newridge, undone in delridge, errexit, errexit2, makenew_nonsimplicial, mergecycle_ridges */
  unsigned int tracevertex_id; /* set at buildtracing, can print whenever */
  vertexT *tracevertex;   /*   set in newvertex, undone in delvertex and qh_errexit */
  vertexT *vertex_list;   /* list of all vertices, to vertex_tail */
  vertexT *vertex_tail;   /*      end of vertex_list (dummy vertex with ID 0, next NULL) */
  vertexT *newvertex_list; /* list of vertices in newfacet_list, to vertex_tail
                             all vertices have 'newfacet' set */
  int   num_facets;       /* number of facets in facet_list
                             includes visible faces (num_visible) */
  int   num_vertices;     /* number of vertices in facet_list */
  int   num_outside;      /* number of points in outsidesets (for tracing and RANDOMoutside)
                               includes coplanar outsideset points for NARROWhull/qh_outcoplanar() */
  int   num_good;         /* number of good facets (after qh_findgood_all or qh_markkeep) */
  unsigned int facet_id;  /* ID of next, new facet from newfacet() */
  unsigned int ridge_id;  /* ID of next, new ridge from newridge() */
  unsigned int vertex_id; /* ID of next, new vertex from newvertex() */
  unsigned int first_newfacet; /* ID of first_newfacet for qh_buildcone, or 0 if none */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-var">-</a>

  qh global variables
    defines minimum and maximum distances, next visit ids, several flags,
    and other global variables.
    initialize in qh_initbuild or qh_maxmin if used in qh_buildhull
*/
  unsigned long hulltime; /* ignore time to set up input and randomize */
                          /*   use 'unsigned long' to avoid wrap-around errors */
  boolT ALLOWrestart;     /* true if qh_joggle_restart can use qh.restartexit */
  int   build_cnt;        /* number of calls to qh_initbuild */
  qh_CENTER CENTERtype;   /* current type of facet->center, qh_CENTER */
  int   furthest_id;      /* pointid of furthest point, for tracing */
  int   last_errcode;     /* last errcode from qh_fprintf, reset in qh_build_withrestart */
  facetT *GOODclosest;    /* closest facet to GOODthreshold in qh_findgood */
  pointT *coplanar_apex;  /* last apex declared a coplanar point by qh_getpinchedmerges, prevents infinite loop */
  boolT hasAreaVolume;    /* true if totarea, totvol was defined by qh_getarea */
  boolT hasTriangulation; /* true if triangulation created by qh_triangulate */
  boolT isRenameVertex;   /* true during qh_merge_pinchedvertices, disables duplicate ridge vertices in qh_checkfacet */
  realT JOGGLEmax;        /* set 'QJn' if randomly joggle input. 'QJ'/'QJ0.0' sets default (qh_detjoggle) */
  boolT maxoutdone;       /* set qh_check_maxout(), cleared by qh_addpoint() */
  realT max_outside;      /* maximum distance from a point to a facet,
                               before roundoff, not simplicial vertices
                               actual outer plane is +DISTround and
                               computed outer plane is +2*DISTround */
  realT max_vertex;       /* maximum distance (>0) from vertex to a facet,
                               before roundoff, due to a merge */
  realT min_vertex;       /* minimum distance (<0) from vertex to a facet,
                               before roundoff, due to a merge
                               if qh.JOGGLEmax, qh_makenewplanes sets it
                               recomputed if qh.DOcheckmax, default -qh.DISTround */
  boolT NEWfacets;        /* true while visible facets invalid due to new or merge
                              from qh_makecone/qh_attachnewfacets to qh_resetlists */
  boolT NEWtentative;     /* true while new facets are tentative due to !qh.IGNOREpinched or qh.ONLYgood
                              from qh_makecone to qh_attachnewfacets */
  boolT findbestnew;      /* true if partitioning calls qh_findbestnew */
  boolT findbest_notsharp; /* true if new facets are at least 90 degrees */
  boolT NOerrexit;        /* true if qh.errexit is not available, cleared after setjmp.  See qh.ERREXITcalled */
  realT PRINTcradius;     /* radius for printing centrums */
  realT PRINTradius;      /* radius for printing vertex spheres and points */
  boolT POSTmerging;      /* true when post merging */
  int   printoutvar;      /* temporary variable for qh_printbegin, etc. */
  int   printoutnum;      /* number of facets printed */
  unsigned int repart_facetid; /* previous facetid to prevent recursive qh_partitioncoplanar+qh_partitionpoint */
  int   retry_addpoint;   /* number of retries of qh_addpoint due to merging pinched vertices */
  boolT QHULLfinished;    /* True after qhull() is finished */
  realT totarea;          /* 'FA': total facet area computed by qh_getarea, hasAreaVolume */
  realT totvol;           /* 'FA': total volume computed by qh_getarea, hasAreaVolume */
  unsigned int visit_id;  /* unique ID for searching neighborhoods, */
  unsigned int vertex_visit; /* unique ID for searching vertices, reset with qh_buildtracing */
  boolT WAScoplanar;      /* True if qh_partitioncoplanar (qh_check_maxout) */
  boolT ZEROall_ok;       /* True if qh_checkzero always succeeds */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-set">-</a>

  qh global sets
    defines sets for merging, initial simplex, hashing, extra input points,
    and deleted vertices
*/
  setT *facet_mergeset;   /* temporary set of merges to be done */
  setT *degen_mergeset;   /* temporary set of degenerate and redundant merges */
  setT *vertex_mergeset;  /* temporary set of vertex merges */
  setT *hash_table;       /* hash table for matching ridges in qh_matchfacets
                             size is setsize() */
  setT *other_points;     /* additional points */
  setT *del_vertices;     /* vertices to partition and delete with visible
                             facets.  v.deleted is set for checkfacet */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-buf">-</a>

  qh global buffers
    defines buffers for maxtrix operations, input, and error messages
*/
  coordT *gm_matrix;      /* (dim+1)Xdim matrix for geom_r.c */
  coordT **gm_row;        /* array of gm_matrix rows */
  char* line;             /* malloc'd input line of maxline+1 chars */
  int maxline;
  coordT *half_space;     /* malloc'd input array for halfspace (qh.normal_size+coordT) */
  coordT *temp_malloc;    /* malloc'd input array for points */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-static">-</a>

  qh static variables
    defines static variables for individual functions

  notes:
    do not use 'static' within a function.  Multiple instances of qhull
    may exist.

    do not assume zero initialization, 'QPn' may cause a restart
*/
  boolT ERREXITcalled;    /* true during qh_errexit (prevents duplicate calls).  see qh.NOerrexit */
  boolT firstcentrum;     /* for qh_printcentrum */
  boolT old_randomdist;   /* save RANDOMdist flag during io, tracing, or statistics */
  setT *coplanarfacetset; /* set of coplanar facets for searching qh_findbesthorizon() */
  realT last_low;         /* qh_scalelast parameters for qh_setdelaunay */
  realT last_high;
  realT last_newhigh;
  realT lastcpu;          /* for qh_buildtracing */
  int   lastfacets;       /*   last qh.num_facets */
  int   lastmerges;       /*   last zzval_(Ztotmerge) */ 
  int   lastplanes;       /*   last zzval_(Zsetplane) */ 
  int   lastdist;         /*   last zzval_(Zdistplane) */ 
  unsigned int lastreport; /*  last qh.facet_id */
  int mergereport;        /* for qh_tracemerging */
  setT *old_tempstack;    /* for saving qh->qhmem.tempstack in save_qhull */
  int   ridgeoutnum;      /* number of ridges for 4OFF output (qh_printbegin,etc) */

/*-<a                             href="qh-globa_r.htm#TOC"
  >--------------------------------</a><a name="qh-const">-</a>

  qh memory management, rbox globals, and statistics

  Replaces global data structures defined for libqhull
*/
  int     last_random;    /* Last random number from qh_rand (random_r.c) */
  jmp_buf rbox_errexit;   /* errexit from rboxlib_r.c, defined by qh_rboxpoints() only */
  char    jmpXtra3[40];   /* extra bytes in case jmp_buf is defined wrong by compiler */
  int     rbox_isinteger;
  double  rbox_out_offset;
  void *  cpp_object;     /* C++ pointer.  Currently used by RboxPoints.qh_fprintf_rbox */
  void *  cpp_other;      /* C++ pointer.  Reserved for other users */
  void *  cpp_user;       /* C++ pointer.  Currently used by QhullUser.qh_fprintf */

  /* Last, otherwise zero'd by qh_initqhull_start2 (global_r.c */
  qhmemT  qhmem;          /* Qhull managed memory (mem_r.h) */
  /* After qhmem because its size depends on the number of statistics */
  qhstatT qhstat;         /* Qhull statistics (stat_r.h) */
};

/*=========== -macros- =========================*/

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="otherfacet_">-</a>

  otherfacet_(ridge, facet)
    return neighboring facet for a ridge in facet
*/
#define otherfacet_(ridge, facet) \
                        (((ridge)->top == (facet)) ? (ridge)->bottom : (ridge)->top)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="getid_">-</a>

  getid_(p)
    return int ID for facet, ridge, or vertex
    return qh_IDunknown(-1) if NULL
    return 0 if facet_tail or vertex_tail
*/
#define getid_(p)       ((p) ? (int)((p)->id) : qh_IDunknown)

/*============== FORALL macros ===================*/

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FORALLfacets">-</a>

  FORALLfacets { ... }
    assign 'facet' to each facet in qh.facet_list

  notes:
    uses 'facetT *facet;'
    assumes last facet is a sentinel
    assumes qh defined

  see:
    FORALLfacet_( facetlist )
*/
#define FORALLfacets for (facet=qh->facet_list;facet && facet->next;facet=facet->next)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FORALLpoints">-</a>

  FORALLpoints { ... }
    assign 'point' to each point in qh.first_point, qh.num_points

  notes:
    assumes qh defined

  declare:
    coordT *point, *pointtemp;
*/
#define FORALLpoints FORALLpoint_(qh, qh->first_point, qh->num_points)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FORALLpoint_">-</a>

  FORALLpoint_(qh, points, num) { ... }
    assign 'point' to each point in points array of num points

  declare:
    coordT *point, *pointtemp;
*/
#define FORALLpoint_(qh, points, num) for (point=(points), \
      pointtemp= (points)+qh->hull_dim*(num); point < pointtemp; point += qh->hull_dim)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FORALLvertices">-</a>

  FORALLvertices { ... }
    assign 'vertex' to each vertex in qh.vertex_list

  declare:
    vertexT *vertex;

  notes:
    assumes qh.vertex_list terminated by NULL or a sentinel (v.next==NULL)
    assumes qh defined
*/
#define FORALLvertices for (vertex=qh->vertex_list;vertex && vertex->next;vertex= vertex->next)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHfacet_">-</a>

  FOREACHfacet_( facets ) { ... }
    assign 'facet' to each facet in facets

  declare:
    facetT *facet, **facetp;

  notes:
    assumes set is not modified

  see:
    <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHfacet_(facets)    FOREACHsetelement_(facetT, facets, facet)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHneighbor_">-</a>

  FOREACHneighbor_( facet ) { ... }
    assign 'neighbor' to each neighbor in facet->neighbors

  FOREACHneighbor_( vertex ) { ... }
    assign 'neighbor' to each neighbor in vertex->neighbors

  declare:
    facetT *neighbor, **neighborp;

  notes:
    assumes set is not modified

  see:
    <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHneighbor_(facet)  FOREACHsetelement_(facetT, facet->neighbors, neighbor)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHpoint_">-</a>

  FOREACHpoint_( points ) { ... }
    assign 'point' to each point in points set

  declare:
    pointT *point, **pointp;

  notes:
    assumes set is not modified

  see:
    <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHpoint_(points)    FOREACHsetelement_(pointT, points, point)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHridge_">-</a>

  FOREACHridge_( ridges ) { ... }
    assign 'ridge' to each ridge in ridges set

  declare:
    ridgeT *ridge, **ridgep;

  notes:
    assumes set is not modified

  see:
    <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHridge_(ridges)    FOREACHsetelement_(ridgeT, ridges, ridge)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHvertex_">-</a>

  FOREACHvertex_( vertices ) { ... }
    assign 'vertex' to each vertex in vertices set

  declare:
    vertexT *vertex, **vertexp;

  notes:
    assumes set is not modified

  see:
    <a href="qset_r.h#FOREACHsetelement_">FOREACHsetelement_</a>
*/
#define FOREACHvertex_(vertices) FOREACHsetelement_(vertexT, vertices,vertex)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHfacet_i_">-</a>

  FOREACHfacet_i_(qh, facets ) { ... }
    assign 'facet' and 'facet_i' for each facet in facets set

  declare:
    facetT *facet;
    int     facet_n, facet_i;

  see:
    <a href="qset_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
*/
#define FOREACHfacet_i_(qh, facets)    FOREACHsetelement_i_(qh, facetT, facets, facet)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHneighbor_i_">-</a>

  FOREACHneighbor_i_(qh, facet ) { ... }
    assign 'neighbor' and 'neighbor_i' for each neighbor in facet->neighbors

  declare:
    facetT *neighbor;
    int     neighbor_n, neighbor_i;

  notes:
    see <a href="qset_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
    for facet neighbors of vertex, need to define a new macro
*/
#define FOREACHneighbor_i_(qh, facet)  FOREACHsetelement_i_(qh, facetT, facet->neighbors, neighbor)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHpoint_i_">-</a>

  FOREACHpoint_i_(qh, points ) { ... }
    assign 'point' and 'point_i' for each point in points set

  declare:
    pointT *point;
    int     point_n, point_i;

  see:
    <a href="qset_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
*/
#define FOREACHpoint_i_(qh, points)    FOREACHsetelement_i_(qh, pointT, points, point)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHridge_i_">-</a>

  FOREACHridge_i_(qh, ridges ) { ... }
    assign 'ridge' and 'ridge_i' for each ridge in ridges set

  declare:
    ridgeT *ridge;
    int     ridge_n, ridge_i;

  see:
    <a href="qset_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
*/
#define FOREACHridge_i_(qh, ridges)    FOREACHsetelement_i_(qh, ridgeT, ridges, ridge)

/*-<a                             href="qh-poly_r.htm#TOC"
  >--------------------------------</a><a name="FOREACHvertex_i_">-</a>

  FOREACHvertex_i_(qh, vertices ) { ... }
    assign 'vertex' and 'vertex_i' for each vertex in vertices set

  declare:
    vertexT *vertex;
    int     vertex_n, vertex_i;

  see:
    <a href="qset_r.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
*/
#define FOREACHvertex_i_(qh, vertices) FOREACHsetelement_i_(qh, vertexT, vertices, vertex)

#ifdef __cplusplus
extern "C" {
#endif

/********* -libqhull_r.c prototypes (duplicated from qhull_ra.h) **********************/

void    qh_qhull(qhT *qh);
boolT   qh_addpoint(qhT *qh, pointT *furthest, facetT *facet, boolT checkdist);
void    qh_errexit2(qhT *qh, int exitcode, facetT *facet, facetT *otherfacet);
void    qh_printsummary(qhT *qh, FILE *fp);

/********* -user_r.c prototypes (alphabetical) **********************/

void    qh_errexit(qhT *qh, int exitcode, facetT *facet, ridgeT *ridge);
void    qh_errprint(qhT *qh, const char* string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex);
int     qh_new_qhull(qhT *qh, int dim, int numpoints, coordT *points, boolT ismalloc,
                char *qhull_cmd, FILE *outfile, FILE *errfile);
int     qh_new_qhull_feaspoint(qhT *qh, int dim, int numpoints, coordT *points, boolT ismalloc,
                char *qhull_cmd, FILE *outfile, FILE *errfile, coordT* feaspoint);
void    qh_printfacetlist(qhT *qh, facetT *facetlist, setT *facets, boolT printall);
void    qh_printhelp_degenerate(qhT *qh, FILE *fp);
void    qh_printhelp_internal(qhT *qh, FILE *fp);
void    qh_printhelp_narrowhull(qhT *qh, FILE *fp, realT minangle);
void    qh_printhelp_singular(qhT *qh, FILE *fp);
void    qh_printhelp_topology(qhT *qh, FILE *fp);
void    qh_printhelp_wide(qhT *qh, FILE *fp);
void    qh_user_memsizes(qhT *qh);

/********* -usermem_r.c prototypes (alphabetical) **********************/
void    qh_exit(int exitcode);
void    qh_fprintf_stderr(int msgcode, const char *fmt, ... );
void    qh_free(void *mem);
void   *qh_malloc(size_t size);

/********* -userprintf_r.c and userprintf_rbox_r.c prototypes **********************/
void    qh_fprintf(qhT *qh, FILE *fp, int msgcode, const char *fmt, ... );
void    qh_fprintf_rbox(qhT *qh, FILE *fp, int msgcode, const char *fmt, ... );

/***** -geom_r.c/geom2_r.c/random_r.c prototypes (duplicated from geom_r.h, random_r.h) ****************/

facetT *qh_findbest(qhT *qh, pointT *point, facetT *startfacet,
                     boolT bestoutside, boolT newfacets, boolT noupper,
                     realT *dist, boolT *isoutside, int *numpart);
facetT *qh_findbestnew(qhT *qh, pointT *point, facetT *startfacet,
                     realT *dist, boolT bestoutside, boolT *isoutside, int *numpart);
boolT   qh_gram_schmidt(qhT *qh, int dim, realT **rows);
void    qh_outerinner(qhT *qh, facetT *facet, realT *outerplane, realT *innerplane);
void    qh_printsummary(qhT *qh, FILE *fp);
void    qh_projectinput(qhT *qh);
void    qh_randommatrix(qhT *qh, realT *buffer, int dim, realT **row);
void    qh_rotateinput(qhT *qh, realT **rows);
void    qh_scaleinput(qhT *qh);
void    qh_setdelaunay(qhT *qh, int dim, int count, pointT *points);
coordT  *qh_sethalfspace_all(qhT *qh, int dim, int count, coordT *halfspaces, pointT *feasible);

/***** -global_r.c prototypes (alphabetical) ***********************/

unsigned long qh_clock(qhT *qh);
void    qh_checkflags(qhT *qh, char *command, char *hiddenflags);
void    qh_clear_outputflags(qhT *qh);
void    qh_freebuffers(qhT *qh);
void    qh_freeqhull(qhT *qh, boolT allmem);
void    qh_init_A(qhT *qh, FILE *infile, FILE *outfile, FILE *errfile, int argc, char *argv[]);
void    qh_init_B(qhT *qh, coordT *points, int numpoints, int dim, boolT ismalloc);
void    qh_init_qhull_command(qhT *qh, int argc, char *argv[]);
void    qh_initbuffers(qhT *qh, coordT *points, int numpoints, int dim, boolT ismalloc);
void    qh_initflags(qhT *qh, char *command);
void    qh_initqhull_buffers(qhT *qh);
void    qh_initqhull_globals(qhT *qh, coordT *points, int numpoints, int dim, boolT ismalloc);
void    qh_initqhull_mem(qhT *qh);
void    qh_initqhull_outputflags(qhT *qh);
void    qh_initqhull_start(qhT *qh, FILE *infile, FILE *outfile, FILE *errfile);
void    qh_initqhull_start2(qhT *qh, FILE *infile, FILE *outfile, FILE *errfile);
void    qh_initthresholds(qhT *qh, char *command);
void    qh_lib_check(int qhullLibraryType, int qhTsize, int vertexTsize, int ridgeTsize, int facetTsize, int setTsize, int qhmemTsize);
void    qh_option(qhT *qh, const char *option, int *i, realT *r);
void    qh_zero(qhT *qh, FILE *errfile);

/***** -io_r.c prototypes (duplicated from io_r.h) ***********************/

void    qh_dfacet(qhT *qh, unsigned int id);
void    qh_dvertex(qhT *qh, unsigned int id);
void    qh_printneighborhood(qhT *qh, FILE *fp, qh_PRINT format, facetT *facetA, facetT *facetB, boolT printall);
void    qh_produce_output(qhT *qh);
coordT *qh_readpoints(qhT *qh, int *numpoints, int *dimension, boolT *ismalloc);


/********* -mem_r.c prototypes (duplicated from mem_r.h) **********************/

void qh_meminit(qhT *qh, FILE *ferr);
void qh_memfreeshort(qhT *qh, int *curlong, int *totlong);

/********* -poly_r.c/poly2_r.c prototypes (duplicated from poly_r.h) **********************/

void    qh_check_output(qhT *qh);
void    qh_check_points(qhT *qh);
setT   *qh_facetvertices(qhT *qh, facetT *facetlist, setT *facets, boolT allfacets);
facetT *qh_findbestfacet(qhT *qh, pointT *point, boolT bestoutside,
           realT *bestdist, boolT *isoutside);
vertexT *qh_nearvertex(qhT *qh, facetT *facet, pointT *point, realT *bestdistp);
pointT *qh_point(qhT *qh, int id);
setT   *qh_pointfacet(qhT *qh /* qh.facet_list */);
int     qh_pointid(qhT *qh, pointT *point);
setT   *qh_pointvertex(qhT *qh /* qh.facet_list */);
void    qh_setvoronoi_all(qhT *qh);
void    qh_triangulate(qhT *qh /* qh.facet_list */);

/********* -rboxlib_r.c prototypes **********************/
int     qh_rboxpoints(qhT *qh, char* rbox_command);
void    qh_errexit_rbox(qhT *qh, int exitcode);

/********* -stat_r.c prototypes (duplicated from stat_r.h) **********************/

void    qh_collectstatistics(qhT *qh);
void    qh_printallstatistics(qhT *qh, FILE *fp, const char *string);

#ifdef __cplusplus
} /* extern "C" */
#endif

#endif /* qhDEFlibqhull */