1 |
#ifndef _triangulate_h
|
2 |
#define _triangulate_h
|
3 |
|
4 |
#include <sys/types.h>
|
5 |
#include <stdlib.h>
|
6 |
#include <stdio.h>
|
7 |
|
8 |
typedef struct {
|
9 |
double x, y;
|
10 |
} point_t, vector_t;
|
11 |
|
12 |
|
13 |
/* Segment attributes */
|
14 |
|
15 |
typedef struct {
|
16 |
point_t v0, v1; /* two endpoints */
|
17 |
int is_inserted; /* inserted in trapezoidation yet ? */
|
18 |
int root0, root1; /* root nodes in Q */
|
19 |
int next; /* Next logical segment */
|
20 |
int prev; /* Previous segment */
|
21 |
} segment_t;
|
22 |
|
23 |
|
24 |
/* Trapezoid attributes */
|
25 |
|
26 |
typedef struct {
|
27 |
int lseg, rseg; /* two adjoining segments */
|
28 |
point_t hi, lo; /* max/min y-values */
|
29 |
int u0, u1;
|
30 |
int d0, d1;
|
31 |
int sink; /* pointer to corresponding in Q */
|
32 |
int usave, uside; /* I forgot what this means */
|
33 |
int state;
|
34 |
} trap_t;
|
35 |
|
36 |
|
37 |
/* Node attributes for every node in the query structure */
|
38 |
|
39 |
typedef struct {
|
40 |
int nodetype; /* Y-node or S-node */
|
41 |
int segnum;
|
42 |
point_t yval;
|
43 |
int trnum;
|
44 |
int parent; /* doubly linked DAG */
|
45 |
int left, right; /* children */
|
46 |
} node_t;
|
47 |
|
48 |
|
49 |
typedef struct {
|
50 |
int vnum;
|
51 |
int next; /* Circularly linked list */
|
52 |
int prev; /* describing the monotone */
|
53 |
int marked; /* polygon */
|
54 |
} monchain_t;
|
55 |
|
56 |
|
57 |
typedef struct {
|
58 |
point_t pt;
|
59 |
int vnext[4]; /* next vertices for the 4 chains */
|
60 |
int vpos[4]; /* position of v in the 4 chains */
|
61 |
int nextfree;
|
62 |
} vertexchain_t;
|
63 |
|
64 |
|
65 |
/* Node types */
|
66 |
|
67 |
#define T_X 1
|
68 |
#define T_Y 2
|
69 |
#define T_SINK 3
|
70 |
|
71 |
|
72 |
#define SEGSIZE 200 /* max# of segments. Determines how */
|
73 |
/* many points can be specified as */
|
74 |
/* input. If your datasets have large */
|
75 |
/* number of points, increase this */
|
76 |
/* value accordingly. */
|
77 |
|
78 |
#define QSIZE 8*SEGSIZE /* maximum table sizes */
|
79 |
#define TRSIZE 4*SEGSIZE /* max# trapezoids */
|
80 |
|
81 |
|
82 |
#define TRUE 1
|
83 |
#define FALSE 0
|
84 |
|
85 |
|
86 |
#define FIRSTPT 1 /* checking whether pt. is inserted */
|
87 |
#define LASTPT 2
|
88 |
|
89 |
|
90 |
#define INFINITY 1<<30
|
91 |
#define C_EPS 1.0e-7 /* tolerance value: Used for making */
|
92 |
/* all decisions about collinearity or */
|
93 |
/* left/right of segment. Decrease */
|
94 |
/* this value if the input points are */
|
95 |
/* spaced very close together */
|
96 |
|
97 |
|
98 |
#define S_LEFT 1 /* for merge-direction */
|
99 |
#define S_RIGHT 2
|
100 |
|
101 |
|
102 |
#define ST_VALID 1 /* for trapezium state */
|
103 |
#define ST_INVALID 2
|
104 |
|
105 |
|
106 |
#define SP_SIMPLE_LRUP 1 /* for splitting trapezoids */
|
107 |
#define SP_SIMPLE_LRDN 2
|
108 |
#define SP_2UP_2DN 3
|
109 |
#define SP_2UP_LEFT 4
|
110 |
#define SP_2UP_RIGHT 5
|
111 |
#define SP_2DN_LEFT 6
|
112 |
#define SP_2DN_RIGHT 7
|
113 |
#define SP_NOSPLIT -1
|
114 |
|
115 |
#define TR_FROM_UP 1 /* for traverse-direction */
|
116 |
#define TR_FROM_DN 2
|
117 |
|
118 |
#define TRI_LHS 1
|
119 |
#define TRI_RHS 2
|
120 |
|
121 |
|
122 |
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
|
123 |
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
|
124 |
|
125 |
#define CROSS(v0, v1, v2) (((v1).x - (v0).x)*((v2).y - (v0).y) - \
|
126 |
((v1).y - (v0).y)*((v2).x - (v0).x))
|
127 |
|
128 |
#define DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)
|
129 |
|
130 |
#define FP_EQUAL(s, t) (fabs(s - t) <= C_EPS)
|
131 |
|
132 |
|
133 |
|
134 |
/* Global variables */
|
135 |
|
136 |
extern node_t qs[QSIZE]; /* Query structure */
|
137 |
extern trap_t tr[TRSIZE]; /* Trapezoid structure */
|
138 |
extern segment_t seg[SEGSIZE]; /* Segment table */
|
139 |
|
140 |
|
141 |
/* Functions */
|
142 |
|
143 |
extern int monotonate_trapezoids(int);
|
144 |
extern int triangulate_monotone_polygons(int, int, int (*)[3]);
|
145 |
|
146 |
extern int _greater_than(point_t *, point_t *);
|
147 |
extern int _equal_to(point_t *, point_t *);
|
148 |
extern int _greater_than_equal_to(point_t *, point_t *);
|
149 |
extern int _less_than(point_t *, point_t *);
|
150 |
extern int locate_endpoint(point_t *, point_t *, int);
|
151 |
extern int construct_trapezoids(int);
|
152 |
|
153 |
extern int generate_random_ordering(int);
|
154 |
extern int choose_segment(void);
|
155 |
extern int read_segments(char *, int *);
|
156 |
extern int math_logstar_n(int);
|
157 |
extern int math_N(int, int);
|
158 |
|
159 |
#endif /* triangulate_h */
|