source: anuga_core/source/anuga/fit_interpolate/ptinpoly.h @ 5181

Last change on this file since 5181 was 4656, checked in by duncan, 17 years ago

Ponit in polygon C code. Currently not connected to ANUGA.

File size: 6.4 KB
Line 
1/* ptinpoly.h - point in polygon inside/outside algorithms header file.
2 *
3 * by Eric Haines, 3D/Eye Inc, erich@eye.com
4 */
5
6/* Define CONVEX to compile for testing only convex polygons (when possible,
7 * this is faster) */
8/* #define CONVEX */
9
10/* Define HYBRID to compile triangle fan test for CONVEX with exterior edges
11 * meaning an early exit (faster - recommended).
12 */
13/* #define HYBRID */
14
15/* Define DISPLAY to display test triangle and test points on screen */
16/* #define DISPLAY */
17
18/* Define RANDOM to randomize order of edges for exterior test (faster -
19 * recommended). */
20/* #define RANDOM */
21
22/* Define SORT to sort triangle edges and areas for half-plane and Spackman
23 * tests (faster - recommended).
24 * The bad news with SORT for non-convex testing is that this usually messes
25 * up any coherence for the triangle fan tests, meaning that points on an
26 * interior edge can be mis-classified (very rare, except when -c is used).
27 * In other words, if a point lands on an edge between two test triangles,
28 * normally it will be inside only one - sorting messes up the test order and
29 * makes it so that the point can be inside two.
30 */
31/* #define SORT */
32
33/* Define WINDING if a non-zero winding number should be used as the criterion
34 * for being inside the polygon.  Only used by the general crossings test and
35 * Weiler test.  The winding number computed for each is the number of
36 * counter-clockwise loops the polygon makes around the point.
37 */
38/* #define WINDING */
39
40/* =========================== System Related ============================= */
41
42/* define your own random number generator, change as needed */
43/* SRAN initializes random number generator, if needed */
44#define SRAN()          srand48(1)
45/* RAN01 returns a double from [0..1) */
46#define RAN01()         drand48()
47double  drand48() ;
48
49/* On systems without drand48() you might do this instead (though check if
50 * rand()'s divisor is correct for your machine):
51#define SRAN()          srand(1)
52#define RAN01()         ((double)rand() / 32768.0)
53*/
54
55/* =========== Grid stuff ================================================= */
56
57#define GR_FULL_VERT    0x01    /* line crosses vertically */
58#define GR_FULL_HORZ    0x02    /* line crosses horizontally */
59
60typedef struct {
61    double      xa,ya ;
62    double      minx, maxx, miny, maxy ;
63    double      ax, ay ;
64    double      slope, inv_slope ;
65} GridRec, *pGridRec;
66
67#define GC_BL_IN        0x0001  /* bottom left corner is in (else out) */
68#define GC_BR_IN        0x0002  /* bottom right corner is in (else out) */
69#define GC_TL_IN        0x0004  /* top left corner is in (else out) */
70#define GC_TR_IN        0x0008  /* top right corner is in (else out) */
71#define GC_L_EDGE_HIT   0x0010  /* left edge is crossed */
72#define GC_R_EDGE_HIT   0x0020  /* right edge is crossed */
73#define GC_B_EDGE_HIT   0x0040  /* bottom edge is crossed */
74#define GC_T_EDGE_HIT   0x0080  /* top edge is crossed */
75#define GC_B_EDGE_PARITY        0x0100  /* bottom edge parity */
76#define GC_T_EDGE_PARITY        0x0200  /* top edge parity */
77#define GC_AIM_L        (0<<10) /* aim towards left edge */
78#define GC_AIM_B        (1<<10) /* aim towards bottom edge */
79#define GC_AIM_R        (2<<10) /* aim towards right edge */
80#define GC_AIM_T        (3<<10) /* aim towards top edge */
81#define GC_AIM_C        (4<<10) /* aim towards a corner */
82#define GC_AIM          0x1c00
83
84#define GC_L_EDGE_CLEAR GC_L_EDGE_HIT
85#define GC_R_EDGE_CLEAR GC_R_EDGE_HIT
86#define GC_B_EDGE_CLEAR GC_B_EDGE_HIT
87#define GC_T_EDGE_CLEAR GC_T_EDGE_HIT
88
89#define GC_ALL_EDGE_CLEAR       (GC_L_EDGE_HIT | \
90                                 GC_R_EDGE_HIT | \
91                                 GC_B_EDGE_HIT | \
92                                 GC_T_EDGE_HIT )
93
94typedef struct {
95    short               tot_edges ;
96    unsigned short      gc_flags ;
97    GridRec             *gr ;
98} GridCell, *pGridCell;
99
100typedef struct {
101    int         xres, yres ;    /* grid size */
102    int         tot_cells ;     /* xres * yres */
103    double      minx, maxx, miny, maxy ;        /* bounding box */
104    double      xdelta, ydelta ;
105    double      inv_xdelta, inv_ydelta ;
106    double      *glx, *gly ;
107    GridCell    *gc ;
108} GridSet, *pGridSet ;
109
110
111#ifdef  CONVEX
112/* =========== Inclusion stuff ============================================ */
113typedef struct {
114    double      dot ;           /* angle to beginning of edge */
115    double      ex, ey, ec ;    /* edge equation */
116} InclusionSet, *pInclusionSet ;
117
118typedef struct {
119    int             flip_edge ; /* clockwise/counterclockwise */
120    int             hi_start ;  /* hi start for binary search: numverts-1 */
121    double          ax, ay ;    /* anchor edge vector */
122    double          qx, qy ;    /* anchor point */
123    pInclusionSet    pis ;
124} InclusionAnchor, *pInclusionAnchor ;
125#endif  /* end CONVEX */
126
127/* =========== Half-Plane stuff =========================================== */
128
129typedef struct {
130    double      vx, vy, c ;     /* edge equation  vx*X + vy*Y + c = 0 */
131#ifdef CONVEX
132#ifdef HYBRID
133    int         ext_flag ;      /* TRUE == exterior edge of polygon */
134#endif
135#endif
136} PlaneSet, *pPlaneSet ;
137
138
139#ifdef  CONVEX
140#ifdef  SORT
141/* Size sorting structure for half-planes */
142typedef struct {
143    double      size ;
144    pPlaneSet   pps ;
145} SizePlanePair, *pSizePlanePair ;
146#endif
147#endif
148
149
150/* =========== Spackman (precomputed barycentric) stuff =================== */
151typedef struct {
152    double      u1p, u2, v1p, v2, inv_u1, inv_u2, inv_v1 ;
153    int         u1_nonzero ;
154} SpackmanSet, *pSpackmanSet ;
155
156
157
158/* =========== Trapezoid stuff ============================================ */
159/* how many bins shall we put the edges into? */
160#define TOT_BINS        1000    /* absolutely the maximum number of bins */
161
162/* add a little to the limits of the polygon bounding box to avoid precision
163 * problems.
164 */
165#define EPSILON         0.00001
166
167/* The following structure is associated with a polygon */
168typedef struct {
169    int         id ;            /* vertex number of edge */
170    int         full_cross ;    /* 1 if extends from top to bottom */
171    double      minx, maxx ;    /* X bounds for bin */
172} Edge, *pEdge ;
173
174typedef struct {
175    pEdge       *edge_set ;
176    double      minx, maxx ;    /* min and max for all edges in bin */
177    int         count ;
178} Trapezoid, *pTrapezoid ;
179
180typedef struct {
181    int         bins ;
182    double      minx, maxx ;    /* bounding box for polygon */
183    double      miny, maxy ;
184    double      ydelta ;        /* (maxy - miny)/bins */
185    double      inv_ydelta ;
186    Trapezoid   *trapz ;
187} TrapezoidSet, *pTrapezoidSet ;
188
189
190#ifdef  CONVEX
191pPlaneSet       ExteriorSetup() ;
192void    ExteriorCleanup() ;
193
194pInclusionAnchor        InclusionSetup() ;
195void    InclusionCleanup() ;
196
197#ifdef  SORT
198int     CompareSizePlanePairs() ;
199#endif
200#endif
201
202pPlaneSet       PlaneSetup() ;
203void    PlaneCleanup() ;
204
205pSpackmanSet    SpackmanSetup() ;
206void    SpackmanCleanup() ;
207
208void    TrapezoidCleanup() ;
209void    TrapBound() ;
210int     CompareEdges() ;
211void    TrapezoidSetup() ;
212
213void    GridSetup() ;
214int     AddGridRecAlloc() ;
215void    GridCleanup() ;
Note: See TracBrowser for help on using the repository browser.