/[zanavi_public1]/navit/navit/maptool/poly2tri-c/001/seidel-1.0/triangulate.h
ZANavi

Contents of /navit/navit/maptool/poly2tri-c/001/seidel-1.0/triangulate.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 3662 byte(s)
new map version, lots of fixes and experimental new features
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 */

   
Visit the ZANavi Wiki