COVISE Core
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
Triangulator.h
Go to the documentation of this file.
1 /* This file is part of COVISE.
2 
3  You can use it under the terms of the GNU Lesser General Public License
4  version 2.1 or later, see lgpl-2.1.txt.
5 
6  * License: LGPL 2+ */
7 
8 //-*-Mode: C++;-*-
9 // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
10 // CLASS Triangulator
11 //
12 // Description: This class provides a triangulation algorithm
13 //
14 //
15 // Initial version: 11.12.2002 (CS)
16 //
17 // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
18 // (C) 2002 by VirCinity IT Consulting
19 // All Rights Reserved.
20 // +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
21 //
22 //
23 // $Id: Triangulator.h,v 1.4 2002/12/17 13:43:10 cs_te Exp $
24 //
25 #ifndef __TRIANGULATOR_INCLUDED
26 #define __TRIANGULATOR_INCLUDED
27 
28 #include <math.h>
29 
30 namespace covise
31 {
32 
33 bool FP_EQUAL(double s, double t);
34 int math_logstar_n(int n);
35 static const double C_EPS = 1.0e-20; /* tolerance value: Used for making */
36 /* all decisions about collinearity or */
37 /* left/right of segment. Decrease */
38 /* this value if the input points are */
39 /* spaced very close together */
40 
41 class _point_t;
42 
43 typedef class _point_t
44 {
45 private:
46 public:
47  double x;
48  double CROSS_SINE(const _point_t &v1)
49  {
50  return (x * (v1).y - (v1).x * y);
51  }
52  double y;
53  _point_t(double xx, double yy)
54  {
55  this->x = xx;
56  this->y = yy;
57  }
59  {
60  this->x = 0.0;
61  this->y = 0.0;
62  }
63  double LENGTH()
64  {
65  return (sqrt(x * x + y * y));
66  }
67  bool operator>(const _point_t &v1)
68  {
69  if (y > v1.y + C_EPS)
70  return true;
71  if (y < v1.y - C_EPS)
72  return false;
73  return (x > v1.x);
74  }
75  friend _point_t operator-(const _point_t &v0, const _point_t &v1)
76  {
77  return _point_t(v0.x - v1.x, v0.y - v1.y);
78  }
79  bool operator==(const _point_t &v1)
80  {
81  return (FP_EQUAL(y, v1.y) && FP_EQUAL(x, v1.x));
82  }
83  bool operator>=(const _point_t &v1)
84  {
85  if (y > v1.y + C_EPS)
86  return true;
87  if (y < v1.y - C_EPS)
88  return false;
89  return (x >= v1.x);
90  }
91  bool operator<(const _point_t &v1)
92  {
93  if (y < v1.y - C_EPS)
94  return true;
95  if (y > v1.y + C_EPS)
96  return false;
97  return (x < v1.x);
98  }
99  void setmax(const _point_t &v0, const _point_t &v1);
100  void setmin(const _point_t &v0, const _point_t &v1);
101 
102 } point_t, vector_t;
103 
104 /* Segment attributes */
105 
106 typedef struct
107 {
108  point_t v0, v1; /* two endpoints */
109  bool is_inserted; /* inserted in trapezoidation yet ? */
110  int root0, root1; /* root nodes in Q */
111  int next; /* Next logical segment */
112  int prev; /* Previous segment */
113 } segment_t;
114 
115 /* Trapezoid attributes */
116 
117 typedef struct
118 {
119  int lseg, rseg; /* two adjoining segments */
120  point_t hi, lo; /* max/min y-values */
121  int u0, u1;
122  int d0, d1;
123  int sink; /* pointer to corresponding in Q */
124  int usave, uside; /* I forgot what this means */
125  int state;
126 } trap_t;
127 
128 /* Node attributes for every node in the query structure */
129 
130 typedef class _node_t
131 {
132 public:
134  {
135  yval = point_t(0.0, 0.0);
136  }
137  int nodetype; /* Y-node or S-node */
138  int segnum;
140  int trnum;
141  int parent; /* doubly linked DAG */
142  int left, right; /* children */
143 } node_t;
144 
145 typedef struct
146 {
147  int vnum;
148  int next; /* Circularly linked list */
149  int prev; /* describing the monotone */
150  int marked; /* polygon */
151 } monchain_t;
152 
153 typedef struct
154 {
156  int vnext[4]; /* next vertices for the 4 chains */
157  int vpos[4]; /* position of v in the 4 chains */
158  int nextfree;
159 } vertexchain_t;
160 
161 static const int FIRSTPT = 1; /* checking whether pt. is inserted */
162 static const int LASTPT = 2;
163 static const int T_X = 1;
164 static const int T_Y = 2;
165 static const int T_SINK = 3;
166 #undef INFINITY
167 static const int INFINITY = 0x40000000;
168 static const int S_LEFT = 1; /* for merge-direction */
169 static const int S_RIGHT = 2;
170 static const int ST_VALID = 1; /* for trapezium state */
171 static const int ST_INVALID = 2;
172 static const int SP_SIMPLE_LRUP = 1; /* for splitting trapezoids */
173 static const int SP_SIMPLE_LRDN = 2;
174 static const int SP_2UP_2DN = 3;
175 static const int SP_2UP_LEFT = 4;
176 static const int SP_2UP_RIGHT = 5;
177 static const int SP_2DN_LEFT = 6;
178 static const int SP_2DN_RIGHT = 7;
179 static const int SP_NOSPLIT = -1;
180 static const int TR_FROM_UP = 1; /* for traverse-direction */
181 static const int TR_FROM_DN = 2;
182 static const int TRI_LHS = 1;
183 static const int TRI_RHS = 2;
184 
185 #ifndef MAX
186 #define MAX(a, b) (((a) > (b)) ? (a) : (b))
187 #endif
188 
189 #ifndef MIN
190 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
191 #endif
192 
193 #define CROSS(v0, v1, v2) (((v1).x - (v0).x) * ((v2).y - (v0).y) - ((v1).y - (v0).y) * ((v2).x - (v0).x))
194 
195 #define DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)
196 
198 {
199 private:
204  vertexchain_t *vert; /* chain init. information. This */
205  /* is used to decide which */
206  /* monotone polygon to split if */
207  /* there are several other */
208  /* polygons touching at the same */
209  /* vertex */
210  int *mon; /* contains position of any vertex in */
211  /* the monotone chain for the polygon */
212  int *visited;
214  int *permute;
216  int q_idx;
217  int tr_idx;
218  int _segsize; /* max# of segments. Determines how */
219  /* many points can be specified as */
220  /* input. If your datasets have large */
221  /* number of points, increase this */
222  /* value accordingly. */
223  int newnode(); /* Return a new node to be added into the query tree */
224  int newtrap(); /* Return a free trapezoid */
225  int init_query_structure(int segnum);
227  {
228  return _segsize;
229  }
230  int getQSize() /* maximum table sizes */
231  {
232  return 4 * _segsize;
233  }
234  int getTRSize() /* max# trapezoids */
235  {
236  return 8 * _segsize;
237  }
238  bool is_left_of(int segnum, point_t &v);
239  bool inserted(int segnum, int whichpt);
240  int locate_endpoint(point_t &v, point_t &vo, int r);
241  int merge_trapezoids(int segnum, int tfirst, int tlast, int side);
242  int add_segment(int segnum);
243  int find_new_roots(int segnum);
244  int construct_trapezoids(int nseg);
245  int inside_polygon(trap_t &t);
246  /* return a new mon structure from the table */
247  int newmon();
248  /* return a new chain element from the table */
249  int new_chain_element();
250  double get_angle(const point_t &vp0, const point_t &vpnext, const point_t &vp1);
251  int get_vertex_positions(int v0, int v1, int &ip, int &iq);
252  int make_new_monotone_poly(int mcur, int v0, int v1);
253  int monotonate_trapezoids(int n);
254  int traverse_polygon(int mcur, int trnum, int from, int dir);
255  int triangulate_monotone_polygons(int nvert, int nmonpoly, int op[][3]);
256  int triangulate_single_polygon(int nvert, int posmax, int side, int op[][3]);
257  int choose_segment();
258  void initialize(int n);
259  void generate_random_ordering(int n);
260  bool isCCW(int size, double (*vertices)[2]);
261  void revert(int size, double (*vertices)[2]);
262  void makeCCW(int size, double (*vertices)[2]);
263  void makeCW(int size, double (*vertices)[2]);
264 
265 public:
266  bool _gotError;
267  Triangulator(int size);
268  ~Triangulator();
269  int triangulate_polygon(int ncontours, int cntr[], double (*vertices)[2], int (*triangles)[3]);
270  static int getTriangles(int numVert, float *x, float *y, int (*triangles)[3]);
271 };
272 }
273 #endif
274 //
275 // History:
276 //
277 // $Log: Triangulator.h,v $
278 // Revision 1.4 2002/12/17 13:43:10 cs_te
279 // -
280 //
281 // Revision 1.3 2002/12/17 13:34:48 ralf
282 // adapted for Windows
283 //
284 // Revision 1.2 2002/12/16 14:16:31 cs_te
285 // -
286 //
287 // Revision 1.1 2002/12/12 11:59:24 cs_te
288 // initial version
289 //
290 //
GLfloat v0
Definition: khronos-glext.h:6752
friend _point_t operator-(const _point_t &v0, const _point_t &v1)
Definition: Triangulator.h:75
Definition: Triangulator.h:197
struct in_addr ip
Definition: coSimClient.h:202
int monotonate_trapezoids(int n)
Definition: Triangulator.cpp:1382
int state
Definition: Triangulator.h:125
double y
Definition: Triangulator.h:52
point_t v1
Definition: Triangulator.h:108
static const int SP_SIMPLE_LRUP
Definition: Triangulator.h:172
segment_t * seg
Definition: Triangulator.h:202
int next
Definition: Triangulator.h:111
bool _gotError
Definition: Triangulator.h:266
int triangulate_single_polygon(int nvert, int posmax, int side, int op[][3])
Definition: Triangulator.cpp:1866
bool operator>=(const _point_t &v1)
Definition: Triangulator.h:83
_point_t()
Definition: Triangulator.h:58
int nodetype
Definition: Triangulator.h:137
int chain_idx
Definition: Triangulator.h:215
int traverse_polygon(int mcur, int trnum, int from, int dir)
Definition: Triangulator.cpp:1451
monchain_t * mchain
Definition: Triangulator.h:203
int marked
Definition: Triangulator.h:150
Definition: Triangulator.h:130
bool operator==(const _point_t &v1)
Definition: Triangulator.h:79
GLint GLint GLint GLint GLint GLint y
Definition: khronos-glext.h:6346
_node_t()
Definition: Triangulator.h:133
static int getTriangles(int numVert, float *x, float *y, int(*triangles)[3])
Definition: Triangulator.cpp:2185
int left
Definition: Triangulator.h:142
int * mon
Definition: Triangulator.h:210
~Triangulator()
Definition: Triangulator.cpp:120
GLdouble n
Definition: khronos-glext.h:8447
void makeCCW(int size, double(*vertices)[2])
Definition: Triangulator.cpp:2169
int choose_segment()
Definition: Triangulator.cpp:1948
int parent
Definition: Triangulator.h:141
bool FP_EQUAL(double s, double t)
Definition: Triangulator.cpp:55
int sink
Definition: Triangulator.h:123
int newnode()
Definition: Triangulator.cpp:158
static const int FIRSTPT
Definition: Triangulator.h:161
double x
Definition: Triangulator.h:47
int getTRSize()
Definition: Triangulator.h:234
static const int T_X
Definition: Triangulator.h:163
int add_segment(int segnum)
Definition: Triangulator.cpp:604
int mon_idx
Definition: Triangulator.h:215
GLdouble s
Definition: khronos-glext.h:6441
static const int SP_2DN_RIGHT
Definition: Triangulator.h:178
static const int TRI_LHS
Definition: Triangulator.h:182
bool operator>(const _point_t &v1)
Definition: Triangulator.h:67
Definition: Triangulator.h:145
int root1
Definition: Triangulator.h:110
int prev
Definition: Triangulator.h:112
static const int SP_2UP_2DN
Definition: Triangulator.h:174
bool operator<(const _point_t &v1)
Definition: Triangulator.h:91
int get_vertex_positions(int v0, int v1, int &ip, int &iq)
Definition: Triangulator.cpp:1265
static const int SP_2DN_LEFT
Definition: Triangulator.h:177
int nextfree
Definition: Triangulator.h:158
int getSegSize()
Definition: Triangulator.h:226
int q_idx
Definition: Triangulator.h:216
_point_t(double xx, double yy)
Definition: Triangulator.h:53
int triangulate_polygon(int ncontours, int cntr[], double(*vertices)[2], int(*triangles)[3])
Definition: Triangulator.cpp:2001
node_t * qs
Definition: Triangulator.h:200
static const int SP_2UP_RIGHT
Definition: Triangulator.h:176
GLsizeiptr size
Definition: khronos-glext.h:6610
void setmax(const _point_t &v0, const _point_t &v1)
int newmon()
Definition: Triangulator.cpp:139
int * visited
Definition: Triangulator.h:212
void generate_random_ordering(int n)
Definition: Triangulator.cpp:2081
point_t yval
Definition: Triangulator.h:139
GLint GLint GLint GLint GLint x
Definition: khronos-glext.h:6346
int d1
Definition: Triangulator.h:122
int make_new_monotone_poly(int mcur, int v0, int v1)
Definition: Triangulator.cpp:1319
static const int ST_INVALID
Definition: Triangulator.h:171
int math_logstar_n(int n)
Definition: Triangulator.cpp:60
GLdouble GLdouble GLdouble r
Definition: khronos-glext.h:6457
void setmin(const _point_t &v0, const _point_t &v1)
static const int T_SINK
Definition: Triangulator.h:165
const GLdouble * v
Definition: khronos-glext.h:6442
double get_angle(const point_t &vp0, const point_t &vpnext, const point_t &vp1)
Definition: Triangulator.cpp:1227
static const int SP_SIMPLE_LRDN
Definition: Triangulator.h:173
Definition: Triangulator.h:153
int construct_trapezoids(int nseg)
Definition: Triangulator.cpp:1197
int next
Definition: Triangulator.h:148
int triangulate_monotone_polygons(int nvert, int nmonpoly, int op[][3])
Definition: Triangulator.cpp:1761
int * permute
Definition: Triangulator.h:214
Definition: Triangulator.h:117
static const int ST_VALID
Definition: Triangulator.h:170
int u1
Definition: Triangulator.h:121
int _segsize
Definition: Triangulator.h:218
void revert(int size, double(*vertices)[2])
Definition: Triangulator.cpp:2153
int prev
Definition: Triangulator.h:149
int vnum
Definition: Triangulator.h:147
bool is_inserted
Definition: Triangulator.h:109
int inside_polygon(trap_t &t)
Definition: Triangulator.cpp:1247
static const int SP_2UP_LEFT
Definition: Triangulator.h:175
int locate_endpoint(point_t &v, point_t &vo, int r)
Definition: Triangulator.cpp:435
int trnum
Definition: Triangulator.h:140
Triangulator(int size)
Definition: Triangulator.cpp:85
class covise::_point_t point_t
int find_new_roots(int segnum)
Definition: Triangulator.cpp:1181
int op_idx
Definition: Triangulator.h:215
class covise::_node_t node_t
int new_chain_element()
Definition: Triangulator.cpp:131
int segnum
Definition: Triangulator.h:138
bool isCCW(int size, double(*vertices)[2])
Definition: Triangulator.cpp:2139
int newtrap()
Definition: Triangulator.cpp:177
int merge_trapezoids(int segnum, int tfirst, int tlast, int side)
Definition: Triangulator.cpp:519
static const int LASTPT
Definition: Triangulator.h:162
int getQSize()
Definition: Triangulator.h:230
int tr_idx
Definition: Triangulator.h:217
static const int TR_FROM_DN
Definition: Triangulator.h:181
Definition: Triangulator.h:106
double LENGTH()
Definition: Triangulator.h:63
GLdouble GLdouble t
Definition: khronos-glext.h:6449
static const int S_LEFT
Definition: Triangulator.h:168
int init_query_structure(int segnum)
Definition: Triangulator.cpp:265
trap_t * tr
Definition: Triangulator.h:201
double CROSS_SINE(const _point_t &v1)
Definition: Triangulator.h:48
point_t lo
Definition: Triangulator.h:120
static const int TR_FROM_UP
Definition: Triangulator.h:180
static const int T_Y
Definition: Triangulator.h:164
void makeCW(int size, double(*vertices)[2])
Definition: Triangulator.cpp:2177
point_t pt
Definition: Triangulator.h:155
static const int TRI_RHS
Definition: Triangulator.h:183
vertexchain_t * vert
Definition: Triangulator.h:204
static const int INFINITY
Definition: Triangulator.h:167
static const int SP_NOSPLIT
Definition: Triangulator.h:179
void initialize(int n)
Definition: Triangulator.cpp:1958
GLfloat GLfloat v1
Definition: khronos-glext.h:6753
bool is_left_of(int segnum, point_t &v)
Definition: Triangulator.cpp:356
Definition: Triangulator.h:43
static const int S_RIGHT
Definition: Triangulator.h:169
int uside
Definition: Triangulator.h:124
int rseg
Definition: Triangulator.h:119
int choose_idx
Definition: Triangulator.h:213
class covise::_point_t vector_t
bool inserted(int segnum, int whichpt)
Definition: Triangulator.cpp:426
int right
Definition: Triangulator.h:142
static const double C_EPS
Definition: Triangulator.h:35