« back to all changes in this revision
Viewing changes to src/qhull.h
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Rafael Laboissiere
- Date: 2004-02-01 01:14:13 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20040201011413-gok3tzufxn804osb
Tags: 2003.1-1
* New upstream release. There are backward incompatibilities in the code
and the soversion was bumped to libqhull5.
* debian/rules:
- Major rewrite of build and install rules, since we are using now the
upstream tarball generated with "make dist".
- Added config rule.
- Use dpatch to patch src/user.h (enable qh_QHpointer).
* debian/control:
- Removed build-dependencies on autoconf, automake, and libtool.
- Build-depends on dpatch.
- Changed section of libqhull-dev package to libdevel.
* debian/libqhull-dev.files: Added usr/share/doc/libqhull5/src
directory.
and the soversion was bumped to libqhull5.
* debian/rules:
- Major rewrite of build and install rules, since we are using now the
upstream tarball generated with "make dist".
- Added config rule.
- Use dpatch to patch src/user.h (enable qh_QHpointer).
* debian/control:
- Removed build-dependencies on autoconf, automake, and libtool.
- Build-depends on dpatch.
- Changed section of libqhull-dev package to libdevel.
* debian/libqhull-dev.files: Added usr/share/doc/libqhull5/src
directory.
- files added:
- Makefile.am
- config
- debian/patches
- files removed:
- Makefile.prefix
- src/liba
- src/libso
- files modified:
- Announce.txt
- eg/q_eg *
added
removed
src/qhull.h
6
6
7
7
see qh-qhull.htm, qhull_a.h
8
8
9
copyright (c) 1993-2001, The Geometry Center
9
copyright (c) 1993-2003, The Geometry Center
10
10
11
defines qh_qh, global data structure for qhull.
12
13
11
NOTE: access to qh_qh is via the 'qh' macro. This allows
14
12
qh_qh to be either a pointer or a structure. An example
15
13
of using qh is "qh DROPdim" which accesses the DROPdim
16
14
field of qh_qh. Similarly, access to qh_qhstat is via
17
15
the 'qhstat' macro.
18
16
19
17
includes function prototypes for qhull.c, geom.c, global.c, io.c, user.c
20
18
21
19
use mem.h for mem.c
22
20
use qset.h for qset.c
23
21
24
22
see unix.c for an example of using qhull.h
25
23
26
24
recompile qhull if you change this file
27
25
*/
28
26
41
39
#include <Desk.h>
42
40
#endif
43
41
44
#ifndef __STDC__
42
#ifndef __STDC__
45
43
#ifndef __cplusplus
46
44
#if !_MSC_VER
47
45
#error Neither __STDC__ nor __cplusplus is defined. Please use strict ANSI C or C++ to compile
48
#error Qhull. You may need to turn off compiler extensions in your project configuration. If
46
#error Qhull. You may need to turn off compiler extensions in your project configuration. If
49
47
#error your compiler is a standard C compiler, you can delete this warning from qhull.h
50
48
#endif
51
49
#endif
55
53
56
54
/*============ constants and basic types ====================*/
57
55
56
extern char *qh_version; /* defined in global.c */
57
58
58
/*-<a href="qh-geom.htm#TOC"
59
59
>--------------------------------</a><a name="coordT">-</a>
60
60
61
61
coordT
62
62
coordinates and coefficients are stored as realT (i.e., double)
63
63
67
67
Also C compilers may do expressions in double anyway.
68
68
*/
69
69
#define coordT realT
70
70
71
/*-<a href="qh-geom.htm#TOC"
71
72
>--------------------------------</a><a name="pointT">-</a>
72
73
73
74
pointT
74
75
a point is an array of DIM3 coordinates
75
76
*/
85
86
86
87
/*-<a href="qh-qhull.htm#TOC"
87
88
>--------------------------------</a><a name="boolT">-</a>
88
89
89
90
boolT
90
91
boolean value, either True or False
91
92
104
105
105
106
/*-<a href="qh-qhull.htm#TOC"
106
107
>--------------------------------</a><a name="CENTERtype">-</a>
107
108
108
109
qh_CENTER
109
110
to distinguish facet->center
110
111
*/
116
117
117
118
/*-<a href="qh-qhull.htm#TOC"
118
119
>--------------------------------</a><a name="qh_PRINT">-</a>
119
120
120
121
qh_PRINT
121
122
output formats for printing (qh.PRINTout).
122
123
'Fa' 'FV' 'Fc' 'FC'
131
132
qh_PRINTcoplanars, qh_PRINTcentrums,
132
133
qh_PRINTfacets, qh_PRINTfacets_xridge, /* 'f' 'FF' 'G' 'FI' 'Fi' 'Fn' */
133
134
qh_PRINTgeom, qh_PRINTids, qh_PRINTinner, qh_PRINTneighbors,
134
qh_PRINTnormals, qh_PRINTouter, /* 'n' 'Fo' 'i' 'm' 'Fm' 'o' */
135
qh_PRINTnormals, qh_PRINTouter, qh_PRINTmaple, /* 'n' 'Fo' 'i' 'm' 'Fm' 'FM', 'o' */
135
136
qh_PRINTincidences, qh_PRINTmathematica, qh_PRINTmerges, qh_PRINToff,
136
137
qh_PRINToptions, qh_PRINTpointintersect, /* 'FO' 'Fp' 'FP' 'p' 'FQ' 'FS' */
137
138
qh_PRINTpointnearest, qh_PRINTpoints, qh_PRINTqhull, qh_PRINTsize,
141
142
142
143
/*-<a href="qh-qhull.htm#TOC"
143
144
>--------------------------------</a><a name="qh_ALL">-</a>
144
145
145
146
qh_ALL
146
147
argument flag for selecting everything
147
148
*/
181
182
182
183
/*-<a href="qh-poly.htm#TOC"
183
184
>--------------------------------</a><a name="facetT">-</a>
184
185
185
186
facetT
186
187
defines a facet
187
188
188
189
notes:
189
qhull() generates the hull as a list of facets.
190
qhull() generates the hull as a list of facets.
190
191
191
192
topological information:
192
193
f.previous,next doubly-linked list of facets
194
195
f.ridges set of ridges
195
196
f.neighbors set of neighbors
196
197
f.toporient True if facet has top-orientation (else bottom)
197
198
198
199
geometric information:
199
200
f.offset,normal hyperplane equation
200
201
f.maxoutside offset to outer plane -- all points inside
201
202
f.center centrum for testing convexity
202
203
f.simplicial True if facet is simplicial
203
204
f.flipped True if facet does not include qh.interior_point
204
205
205
206
for constructing hull:
206
207
f.visible True if facet on list of visible facets (will be deleted)
207
208
f.newfacet True if facet on list of newly created facets
212
213
f.visitid marks visited facets during a loop
213
214
f.replace replacement facet for to-be-deleted, visible facets
214
215
f.samecycle,newcycle cycle of facets for merging into horizon facet
215
216
216
217
see below for other flags and fields
217
218
*/
218
219
struct facetT {
226
227
Actual outer plane is +DISTround and
227
228
computed outer plane is +2*DISTround */
228
229
#endif
229
coordT offset; /* exact offset of hyperplane from origin */
230
coordT offset; /* exact offset of hyperplane from origin */
230
231
coordT *normal; /* normal of hyperplane, hull_dim coefficients */
231
232
/* if tricoplanar, shared with a neighbor */
232
233
union { /* in order of testing */
248
249
if simplicial, 1st vertex was apex/furthest */
249
250
setT *ridges; /* explicit ridges for nonsimplicial facets.
250
251
for simplicial facets, neighbors defines ridge */
251
setT *neighbors; /* neighbors of the facet. If simplicial, the kth
252
setT *neighbors; /* neighbors of the facet. If simplicial, the kth
252
253
neighbor is opposite the kth vertex, and the first
253
254
neighbor is the horizon facet for the first vertex*/
254
255
setT *outsideset; /* set of points outside this facet
305
306
306
307
ridgeT
307
308
defines a ridge
308
309
309
310
notes:
310
311
a ridge is DIM3-1 simplex between two neighboring facets. If the
311
312
facets are non-simplicial, there may be more than one ridge between
315
316
topological information:
316
317
vertices a set of vertices
317
318
top,bottom neighboring facets with orientation
318
319
319
320
geometric information:
320
321
tested True if ridge is clearly convex
321
nonconvex True if ridge is non-convex
322
nonconvex True if ridge is non-convex
322
323
*/
323
324
struct ridgeT {
324
325
setT *vertices; /* vertices belonging to this ridge, inverse sorted by ID
328
329
unsigned id:24; /* unique identifier, =>room for 8 flags */
329
330
flagT seen:1; /* used to perform operations only once */
330
331
flagT tested:1; /* True when ridge is tested for convexity */
331
flagT nonconvex:1; /* True if getmergeset detected a non-convex neighbor
332
flagT nonconvex:1; /* True if getmergeset detected a non-convex neighbor
332
333
only one ridge between neighbors may have nonconvex */
333
334
};
334
335
335
336
/*-<a href="qh-poly.htm#TOC"
336
337
>--------------------------------</a><a name="vertexT">-</a>
337
338
338
339
vertexT
339
340
defines a vertex
340
341
341
342
topological information:
342
343
next,previous doubly-linked list of all vertices
343
344
neighbors set of adjacent facets (only if qh.VERTEXneighbors)
344
345
345
346
geometric information:
346
347
point array of DIM3 coordinates
347
348
*/
362
363
363
364
/*======= -global variables -qh ============================*/
364
365
365
extern char qh_version[];
366
367
366
/*-<a href="qh-globa.htm#TOC"
368
367
>--------------------------------</a><a name="qh">-</a>
369
368
370
369
qh
371
370
all global variables for qhull are in qh, qhmem, and qhstat
372
371
373
372
notes:
374
373
qhmem is defined in mem.h and qhstat is defined in stat.h
375
access to qh_qh is via the "qh" macro. See qh_QHpointer in user.h
374
Access to qh_qh is via the "qh" macro. See qh_QHpointer in user.h
376
375
*/
377
typedef struct qhT qhT;
376
typedef struct qhT qhT;
378
377
#if qh_QHpointer
379
378
#define qh qh_qh->
380
379
extern qhT *qh_qh; /* allocated in global.c */
390
389
391
390
qh constants
392
391
configuration flags and constants for Qhull
393
392
394
393
notes:
395
394
The user configures Qhull by defining flags. They are
396
395
copied into qh by qh_setflags(). qh-quick.htm#options defines the flags.
400
399
boolT APPROXhull; /* true 'Wn' if MINoutside set */
401
400
realT MINoutside; /* 'Wn' min. distance for an outside point */
402
401
boolT ATinfinity; /* true 'Qz' if point num_points-1 is "at-infinity"
403
for improving precision in Delaunay triangulations */
402
for improving precision in Delaunay triangulations */
404
403
boolT AVOIDold; /* true 'Q4' if avoid old->new merges */
405
404
boolT BESToutside; /* true 'Qf' if partition points into best outsideset */
406
405
boolT CDDinput; /* true 'Pc' if input uses CDD format (1.0/offset first) */
414
413
boolT FORCEoutput; /* true 'Po' if forcing output despite degeneracies */
415
414
int GOODpoint; /* 1+n for 'QGn', good facet if visible/not(-) from point n*/
416
415
pointT *GOODpointp; /* the actual point */
417
boolT GOODthreshold; /* true if qh lower_threshold/upper_threshold defined
416
boolT GOODthreshold; /* true if qh lower_threshold/upper_threshold defined
418
417
false if qh SPLITthreshold */
419
418
int GOODvertex; /* 1+n, good facet if vertex for point n */
420
419
pointT *GOODvertexp; /* the actual point */
422
421
int IStracing; /* trace execution, 0=none, 1=least, 4=most, -1=events */
423
422
int KEEParea; /* 'PAn' number of largest facets to keep */
424
423
boolT KEEPcoplanar; /* true 'Qc' if keeping nearest facet for coplanar points */
425
boolT KEEPinside; /* true 'Qi' if keeping nearest facet for inside points
424
boolT KEEPinside; /* true 'Qi' if keeping nearest facet for inside points
426
425
set automatically if 'd Qc' */
427
426
int KEEPmerge; /* 'PMn' number of facets to keep with most merges */
428
427
realT KEEPminArea; /* 'PFn' minimum facet area to keep */
482
481
used only for printing (not for qh ONLYgood) */
483
482
int STOPcone; /* 'TCn' 1+n for stopping after cone for point n*/
484
483
/* also used by qh_build_withresart for err exit*/
485
int STOPpoint; /* 'TVn' 'TV-n' 1+n for stopping after/before(-)
484
int STOPpoint; /* 'TVn' 'TV-n' 1+n for stopping after/before(-)
486
485
adding point n */
486
int TESTpoints; /* 'QTn' num of test points after qh.num_points. Test points always coplanar. */
487
487
boolT TESTvneighbors; /* true 'Qv' if test vertex neighbors at end */
488
488
int TRACElevel; /* 'Tn' conditional IStracing level */
489
489
int TRACElastrun; /* qh.TRACElevel applies to last qh.RERUN */
523
523
if Delaunay, default is 0.0 for upper envelope */
524
524
realT *lower_threshold; /* don't print if facet->normal[k] <=lower_threshold[k] */
525
525
realT *upper_bound; /* scale point[k] to new upper bound */
526
realT *lower_bound; /* scale point[k] to new lower bound
526
realT *lower_bound; /* scale point[k] to new lower bound
527
527
project if both upper_ and lower_bound == 0 */
528
528
529
529
/*-<a href="qh-globa.htm#TOC"
531
531
532
532
qh precision constants
533
533
precision constants for Qhull
534
534
535
535
notes:
536
536
qh_detroundoff() computes the maximum roundoff error for distance
537
537
and other computations. It also sets default values for the
554
554
realT *NEARzero; /* hull_dim array for near zero in gausselim */
555
555
realT NEARinside; /* keep points for qh_check_maxout if close to facet */
556
556
realT ONEmerge; /* max distance for merging simplicial facets */
557
realT outside_err; /* application's epsilon for coplanar points
557
realT outside_err; /* application's epsilon for coplanar points
558
558
qh_check_bestdist() qh_check_points() reports error if point outside */
559
559
realT WIDEfacet; /* size of wide facet for skipping ridge in
560
560
area computation and locking centrum */
591
591
facetT *facet_list; /* first facet */
592
592
facetT *facet_tail; /* end of facet_list (dummy facet) */
593
593
facetT *facet_next; /* next facet for buildhull()
594
previous facets do not have outside sets
594
previous facets do not have outside sets
595
595
NARROWhull: previous facets may have coplanar outside sets for qh_outcoplanar */
596
596
facetT *newfacet_list; /* list of new facets to end of facet_list */
597
597
facetT *visible_list; /* list of visible facets preceeding newfacet_list,
608
608
int num_facets; /* number of facets in facet_list
609
609
includes visble faces (num_visible) */
610
610
int num_vertices; /* number of vertices in facet_list */
611
int num_outside; /* number of points in outsidesets (for tracing and RANDOMoutside)
611
int num_outside; /* number of points in outsidesets (for tracing and RANDOMoutside)
612
612
includes coplanar outsideset points for NARROWhull/qh_outcoplanar() */
613
613
int num_good; /* number of good facets (after findgood_all) */
614
614
unsigned facet_id; /* ID of next, new facet from newfacet() */
640
640
before roundoff, due to a merge */
641
641
realT min_vertex; /* minimum distance (<0) from vertex to a facet,
642
642
before roundoff, due to a merge
643
if qh.JOGGLEmax, qh_makenewplanes sets it
643
if qh.JOGGLEmax, qh_makenewplanes sets it
644
644
recomputed if qh.DOcheckmax, default -qh.DISTround */
645
645
boolT NEWfacets; /* true while visible facets invalid due to new or merge
646
646
from makecone/attachnewfacets to deletevisible */
662
662
663
663
/*-<a href="qh-globa.htm#TOC"
664
664
>--------------------------------</a><a name="qh-set">-</a>
665
665
666
666
qh global sets
667
667
defines sets for merging, initial simplex, hashing, extra input points,
668
668
and deleted vertices
669
669
*/
670
670
setT *facet_mergeset; /* temporary set of merges to be done */
671
671
setT *degen_mergeset; /* temporary set of degenerate and redundant merges */
672
setT *hash_table; /* hash table for matching ridges in qh_matchfacets
672
setT *hash_table; /* hash table for matching ridges in qh_matchfacets
673
673
size is setsize() */
674
674
setT *other_points; /* additional points (first is qh interior_point) */
675
setT *del_vertices; /* vertices to partition and delete with visible
675
setT *del_vertices; /* vertices to partition and delete with visible
676
676
facets. Have deleted set for checkfacet */
677
677
678
678
/*-<a href="qh-globa.htm#TOC"
679
679
>--------------------------------</a><a name="qh-buf">-</a>
680
680
681
681
qh global buffers
682
682
defines buffers for maxtrix operations, input, and error messages
683
683
*/
690
690
691
691
/*-<a href="qh-globa.htm#TOC"
692
692
>--------------------------------</a><a name="qh-static">-</a>
693
693
694
694
qh static variables
695
695
defines static variables for individual functions
696
696
697
697
notes:
698
698
do not use 'static' within a function. Multiple instances of qhull
699
699
may exist.
718
718
719
719
/*-<a href="qh-poly.htm#TOC"
720
720
>--------------------------------</a><a name="otherfacet_">-</a>
721
721
722
722
otherfacet_(ridge, facet)
723
723
return neighboring facet for a ridge in facet
724
724
*/
727
727
728
728
/*-<a href="qh-poly.htm#TOC"
729
729
>--------------------------------</a><a name="getid_">-</a>
730
730
731
731
getid_(p)
732
732
return ID for facet, ridge, or vertex
733
733
return MAXINT if NULL (-1 causes type conversion error )
738
738
739
739
/*-<a href="qh-poly.htm#TOC"
740
740
>--------------------------------</a><a name="FORALLfacets">-</a>
741
741
742
742
FORALLfacets { ... }
743
743
assign 'facet' to each facet in qh.facet_list
744
744
745
745
notes:
746
746
uses 'facetT *facet;'
747
747
assumes last facet is a sentinel
748
748
749
749
see:
750
FORALLfacet_( facetlist )
750
FORALLfacet_( facetlist )
751
751
*/
752
752
#define FORALLfacets for (facet=qh facet_list;facet && facet->next;facet=facet->next)
753
753
754
754
/*-<a href="qh-poly.htm#TOC"
755
755
>--------------------------------</a><a name="FORALLpoints">-</a>
756
756
757
757
FORALLpoints { ... }
758
758
assign 'point' to each point in qh.first_point, qh.num_points
759
759
764
764
765
765
/*-<a href="qh-poly.htm#TOC"
766
766
>--------------------------------</a><a name="FORALLpoint_">-</a>
767
767
768
768
FORALLpoint_( points, num) { ... }
769
769
assign 'point' to each point in points array of num points
770
770
776
776
777
777
/*-<a href="qh-poly.htm#TOC"
778
778
>--------------------------------</a><a name="FORALLvertices">-</a>
779
779
780
780
FORALLvertices { ... }
781
781
assign 'vertex' to each vertex in qh.vertex_list
782
782
783
783
declare:
784
784
vertexT *vertex;
785
785
790
790
791
791
/*-<a href="qh-poly.htm#TOC"
792
792
>--------------------------------</a><a name="FOREACHfacet_">-</a>
793
793
794
794
FOREACHfacet_( facets ) { ... }
795
795
assign 'facet' to each facet in facets
796
796
797
797
declare:
798
798
facetT *facet, **facetp;
799
799
804
804
805
805
/*-<a href="qh-poly.htm#TOC"
806
806
>--------------------------------</a><a name="FOREACHneighbor_">-</a>
807
807
808
808
FOREACHneighbor_( facet ) { ... }
809
809
assign 'neighbor' to each neighbor in facet->neighbors
810
810
811
811
FOREACHneighbor_( vertex ) { ... }
812
812
assign 'neighbor' to each neighbor in vertex->neighbors
813
813
814
814
declare:
815
815
facetT *neighbor, **neighborp;
816
816
821
821
822
822
/*-<a href="qh-poly.htm#TOC"
823
823
>--------------------------------</a><a name="FOREACHpoint_">-</a>
824
824
825
825
FOREACHpoint_( points ) { ... }
826
826
assign 'point' to each point in points set
827
827
828
828
declare:
829
829
pointT *point, **pointp;
830
830
835
835
836
836
/*-<a href="qh-poly.htm#TOC"
837
837
>--------------------------------</a><a name="FOREACHridge_">-</a>
838
838
839
839
FOREACHridge_( ridges ) { ... }
840
840
assign 'ridge' to each ridge in ridges set
841
841
842
842
declare:
843
843
ridgeT *ridge, **ridgep;
844
844
849
849
850
850
/*-<a href="qh-poly.htm#TOC"
851
851
>--------------------------------</a><a name="FOREACHvertex_">-</a>
852
852
853
853
FOREACHvertex_( vertices ) { ... }
854
854
assign 'vertex' to each vertex in vertices set
855
855
856
856
declare:
857
857
vertexT *vertex, **vertexp;
858
858
863
863
864
864
/*-<a href="qh-poly.htm#TOC"
865
865
>--------------------------------</a><a name="FOREACHfacet_i_">-</a>
866
866
867
867
FOREACHfacet_i_( facets ) { ... }
868
868
assign 'facet' and 'facet_i' for each facet in facets set
869
869
870
870
declare:
871
871
facetT *facet;
872
872
int facet_n, facet_i;
878
878
879
879
/*-<a href="qh-poly.htm#TOC"
880
880
>--------------------------------</a><a name="FOREACHneighbor_i_">-</a>
881
881
882
882
FOREACHneighbor_i_( facet ) { ... }
883
883
assign 'neighbor' and 'neighbor_i' for each neighbor in facet->neighbors
884
884
885
885
FOREACHneighbor_i_( vertex ) { ... }
886
886
assign 'neighbor' and 'neighbor_i' for each neighbor in vertex->neighbors
887
887
888
888
declare:
889
889
facetT *neighbor;
890
890
int neighbor_n, neighbor_i;
896
896
897
897
/*-<a href="qh-poly.htm#TOC"
898
898
>--------------------------------</a><a name="FOREACHpoint_i_">-</a>
899
899
900
900
FOREACHpoint_i_( points ) { ... }
901
901
assign 'point' and 'point_i' for each point in points set
902
902
903
903
declare:
904
904
pointT *point;
905
905
int point_n, point_i;
911
911
912
912
/*-<a href="qh-poly.htm#TOC"
913
913
>--------------------------------</a><a name="FOREACHridge_i_">-</a>
914
914
915
915
FOREACHridge_i_( ridges ) { ... }
916
916
assign 'ridge' and 'ridge_i' for each ridge in ridges set
917
917
918
918
declare:
919
919
ridgeT *ridge;
920
920
int ridge_n, ridge_i;
949
949
950
950
void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge);
951
951
void qh_errprint(char* string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex);
952
int qh_new_qhull (int dim, int numpoints, coordT *points, boolT ismalloc,
952
int qh_new_qhull (int dim, int numpoints, coordT *points, boolT ismalloc,
953
953
char *qhull_cmd, FILE *outfile, FILE *errfile);
954
954
void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall);
955
955
void qh_user_memsizes (void);
956
956
957
957
/***** -geom.c/geom2.c prototypes (duplicated from geom.h) ****************/
958
958
959
facetT *qh_findbest (pointT *point, facetT *startfacet,
959
facetT *qh_findbest (pointT *point, facetT *startfacet,
960
960
boolT bestoutside, boolT newfacets, boolT noupper,
961
961
realT *dist, boolT *isoutside, int *numpart);
962
962
facetT *qh_findbestnew (pointT *point, facetT *startfacet,
Loggerhead is a web-based interface for Breezy
Version: 2.0.1