1 |
#include <triangulate.h>
|
2 |
#include <math.h>
|
3 |
|
4 |
#define CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)
|
5 |
#define LENGTH(v0) (sqrt((v0).x * (v0).x + (v0).y * (v0).y))
|
6 |
|
7 |
static monchain_t mchain[TRSIZE]; /* Table to hold all the monotone */
|
8 |
/* polygons . Each monotone polygon */
|
9 |
/* is a circularly linked list */
|
10 |
|
11 |
static vertexchain_t vert[SEGSIZE]; /* chain init. information. This */
|
12 |
/* is used to decide which */
|
13 |
/* monotone polygon to split if */
|
14 |
/* there are several other */
|
15 |
/* polygons touching at the same */
|
16 |
/* vertex */
|
17 |
|
18 |
static int mon[SEGSIZE]; /* contains position of any vertex in */
|
19 |
/* the monotone chain for the polygon */
|
20 |
static int visited[TRSIZE];
|
21 |
static int chain_idx, op_idx, mon_idx;
|
22 |
|
23 |
|
24 |
static int triangulate_single_polygon(int, int, int, int (*)[3]);
|
25 |
static int traverse_polygon(int, int, int, int);
|
26 |
|
27 |
/* Function returns TRUE if the trapezoid lies inside the polygon */
|
28 |
static int inside_polygon(t)
|
29 |
trap_t *t;
|
30 |
{
|
31 |
int rseg = t->rseg;
|
32 |
|
33 |
if (t->state == ST_INVALID)
|
34 |
return 0;
|
35 |
|
36 |
if ((t->lseg <= 0) || (t->rseg <= 0))
|
37 |
return 0;
|
38 |
|
39 |
if (((t->u0 <= 0) && (t->u1 <= 0)) ||
|
40 |
((t->d0 <= 0) && (t->d1 <= 0))) /* triangle */
|
41 |
return (_greater_than(&seg[rseg].v1, &seg[rseg].v0));
|
42 |
|
43 |
return 0;
|
44 |
}
|
45 |
|
46 |
|
47 |
/* return a new mon structure from the table */
|
48 |
static int newmon()
|
49 |
{
|
50 |
return ++mon_idx;
|
51 |
}
|
52 |
|
53 |
|
54 |
/* return a new chain element from the table */
|
55 |
static int new_chain_element()
|
56 |
{
|
57 |
return ++chain_idx;
|
58 |
}
|
59 |
|
60 |
|
61 |
static double get_angle(vp0, vpnext, vp1)
|
62 |
point_t *vp0;
|
63 |
point_t *vpnext;
|
64 |
point_t *vp1;
|
65 |
{
|
66 |
point_t v0, v1;
|
67 |
|
68 |
v0.x = vpnext->x - vp0->x;
|
69 |
v0.y = vpnext->y - vp0->y;
|
70 |
|
71 |
v1.x = vp1->x - vp0->x;
|
72 |
v1.y = vp1->y - vp0->y;
|
73 |
|
74 |
if (CROSS_SINE(v0, v1) >= 0) /* sine is positive */
|
75 |
return DOT(v0, v1)/LENGTH(v0)/LENGTH(v1);
|
76 |
else
|
77 |
return (-1.0 * DOT(v0, v1)/LENGTH(v0)/LENGTH(v1) - 2);
|
78 |
}
|
79 |
|
80 |
|
81 |
/* (v0, v1) is the new diagonal to be added to the polygon. Find which */
|
82 |
/* chain to use and return the positions of v0 and v1 in p and q */
|
83 |
static int get_vertex_positions(v0, v1, ip, iq)
|
84 |
int v0;
|
85 |
int v1;
|
86 |
int *ip;
|
87 |
int *iq;
|
88 |
{
|
89 |
vertexchain_t *vp0, *vp1;
|
90 |
register int i;
|
91 |
double angle, temp;
|
92 |
int tp, tq;
|
93 |
|
94 |
vp0 = &vert[v0];
|
95 |
vp1 = &vert[v1];
|
96 |
|
97 |
/* p is identified as follows. Scan from (v0, v1) rightwards till */
|
98 |
/* you hit the first segment starting from v0. That chain is the */
|
99 |
/* chain of our interest */
|
100 |
|
101 |
angle = -4.0;
|
102 |
for (i = 0; i < 4; i++)
|
103 |
{
|
104 |
if (vp0->vnext[i] <= 0)
|
105 |
continue;
|
106 |
if ((temp = get_angle(&vp0->pt, &(vert[vp0->vnext[i]].pt),
|
107 |
&vp1->pt)) > angle)
|
108 |
{
|
109 |
angle = temp;
|
110 |
tp = i;
|
111 |
}
|
112 |
}
|
113 |
|
114 |
*ip = tp;
|
115 |
|
116 |
/* Do similar actions for q */
|
117 |
|
118 |
angle = -4.0;
|
119 |
for (i = 0; i < 4; i++)
|
120 |
{
|
121 |
if (vp1->vnext[i] <= 0)
|
122 |
continue;
|
123 |
if ((temp = get_angle(&vp1->pt, &(vert[vp1->vnext[i]].pt),
|
124 |
&vp0->pt)) > angle)
|
125 |
{
|
126 |
angle = temp;
|
127 |
tq = i;
|
128 |
}
|
129 |
}
|
130 |
|
131 |
*iq = tq;
|
132 |
|
133 |
return 0;
|
134 |
}
|
135 |
|
136 |
|
137 |
/* v0 and v1 are specified in anti-clockwise order with respect to
|
138 |
* the current monotone polygon mcur. Split the current polygon into
|
139 |
* two polygons using the diagonal (v0, v1)
|
140 |
*/
|
141 |
static int make_new_monotone_poly(mcur, v0, v1)
|
142 |
int mcur;
|
143 |
int v0;
|
144 |
int v1;
|
145 |
{
|
146 |
int p, q, ip, iq;
|
147 |
int mnew = newmon();
|
148 |
int i, j, nf0, nf1;
|
149 |
vertexchain_t *vp0, *vp1;
|
150 |
|
151 |
vp0 = &vert[v0];
|
152 |
vp1 = &vert[v1];
|
153 |
|
154 |
get_vertex_positions(v0, v1, &ip, &iq);
|
155 |
|
156 |
p = vp0->vpos[ip];
|
157 |
q = vp1->vpos[iq];
|
158 |
|
159 |
/* At this stage, we have got the positions of v0 and v1 in the */
|
160 |
/* desired chain. Now modify the linked lists */
|
161 |
|
162 |
i = new_chain_element(); /* for the new list */
|
163 |
j = new_chain_element();
|
164 |
|
165 |
mchain[i].vnum = v0;
|
166 |
mchain[j].vnum = v1;
|
167 |
|
168 |
mchain[i].next = mchain[p].next;
|
169 |
mchain[mchain[p].next].prev = i;
|
170 |
mchain[i].prev = j;
|
171 |
mchain[j].next = i;
|
172 |
mchain[j].prev = mchain[q].prev;
|
173 |
mchain[mchain[q].prev].next = j;
|
174 |
|
175 |
mchain[p].next = q;
|
176 |
mchain[q].prev = p;
|
177 |
|
178 |
nf0 = vp0->nextfree;
|
179 |
nf1 = vp1->nextfree;
|
180 |
|
181 |
vp0->vnext[ip] = v1;
|
182 |
|
183 |
vp0->vpos[nf0] = i;
|
184 |
vp0->vnext[nf0] = mchain[mchain[i].next].vnum;
|
185 |
vp1->vpos[nf1] = j;
|
186 |
vp1->vnext[nf1] = v0;
|
187 |
|
188 |
vp0->nextfree++;
|
189 |
vp1->nextfree++;
|
190 |
|
191 |
#ifdef DEBUG
|
192 |
fprintf(stderr, "make_poly: mcur = %d, (v0, v1) = (%d, %d)\n",
|
193 |
mcur, v0, v1);
|
194 |
fprintf(stderr, "next posns = (p, q) = (%d, %d)\n", p, q);
|
195 |
#endif
|
196 |
|
197 |
mon[mcur] = p;
|
198 |
mon[mnew] = i;
|
199 |
return mnew;
|
200 |
}
|
201 |
|
202 |
/* Main routine to get monotone polygons from the trapezoidation of
|
203 |
* the polygon.
|
204 |
*/
|
205 |
|
206 |
int monotonate_trapezoids(n)
|
207 |
int n;
|
208 |
{
|
209 |
register int i;
|
210 |
int tr_start;
|
211 |
|
212 |
memset((void *)vert, 0, sizeof(vert));
|
213 |
memset((void *)visited, 0, sizeof(visited));
|
214 |
memset((void *)mchain, 0, sizeof(mchain));
|
215 |
memset((void *)mon, 0, sizeof(mon));
|
216 |
|
217 |
/* First locate a trapezoid which lies inside the polygon */
|
218 |
/* and which is triangular */
|
219 |
for (i = 0; i < TRSIZE; i++)
|
220 |
if (inside_polygon(&tr[i]))
|
221 |
break;
|
222 |
tr_start = i;
|
223 |
|
224 |
/* Initialise the mon data-structure and start spanning all the */
|
225 |
/* trapezoids within the polygon */
|
226 |
|
227 |
#if 0
|
228 |
for (i = 1; i <= n; i++)
|
229 |
{
|
230 |
mchain[i].prev = i - 1;
|
231 |
mchain[i].next = i + 1;
|
232 |
mchain[i].vnum = i;
|
233 |
vert[i].pt = seg[i].v0;
|
234 |
vert[i].vnext[0] = i + 1; /* next vertex */
|
235 |
vert[i].vpos[0] = i; /* locn. of next vertex */
|
236 |
vert[i].nextfree = 1;
|
237 |
}
|
238 |
mchain[1].prev = n;
|
239 |
mchain[n].next = 1;
|
240 |
vert[n].vnext[0] = 1;
|
241 |
vert[n].vpos[0] = n;
|
242 |
chain_idx = n;
|
243 |
mon_idx = 0;
|
244 |
mon[0] = 1; /* position of any vertex in the first */
|
245 |
/* chain */
|
246 |
|
247 |
#else
|
248 |
|
249 |
for (i = 1; i <= n; i++)
|
250 |
{
|
251 |
mchain[i].prev = seg[i].prev;
|
252 |
mchain[i].next = seg[i].next;
|
253 |
mchain[i].vnum = i;
|
254 |
vert[i].pt = seg[i].v0;
|
255 |
vert[i].vnext[0] = seg[i].next; /* next vertex */
|
256 |
vert[i].vpos[0] = i; /* locn. of next vertex */
|
257 |
vert[i].nextfree = 1;
|
258 |
}
|
259 |
|
260 |
chain_idx = n;
|
261 |
mon_idx = 0;
|
262 |
mon[0] = 1; /* position of any vertex in the first */
|
263 |
/* chain */
|
264 |
|
265 |
#endif
|
266 |
|
267 |
/* traverse the polygon */
|
268 |
if (tr[tr_start].u0 > 0)
|
269 |
traverse_polygon(0, tr_start, tr[tr_start].u0, TR_FROM_UP);
|
270 |
else if (tr[tr_start].d0 > 0)
|
271 |
traverse_polygon(0, tr_start, tr[tr_start].d0, TR_FROM_DN);
|
272 |
|
273 |
/* return the number of polygons created */
|
274 |
return newmon();
|
275 |
}
|
276 |
|
277 |
|
278 |
/* recursively visit all the trapezoids */
|
279 |
static int traverse_polygon(mcur, trnum, from, dir)
|
280 |
int mcur;
|
281 |
int trnum;
|
282 |
int from;
|
283 |
int dir;
|
284 |
{
|
285 |
trap_t *t = &tr[trnum];
|
286 |
int howsplit, mnew;
|
287 |
int v0, v1, v0next, v1next;
|
288 |
int retval, tmp;
|
289 |
int do_switch = FALSE;
|
290 |
|
291 |
if ((trnum <= 0) || visited[trnum])
|
292 |
return 0;
|
293 |
|
294 |
visited[trnum] = TRUE;
|
295 |
|
296 |
/* We have much more information available here. */
|
297 |
/* rseg: goes upwards */
|
298 |
/* lseg: goes downwards */
|
299 |
|
300 |
/* Initially assume that dir = TR_FROM_DN (from the left) */
|
301 |
/* Switch v0 and v1 if necessary afterwards */
|
302 |
|
303 |
|
304 |
/* special cases for triangles with cusps at the opposite ends. */
|
305 |
/* take care of this first */
|
306 |
if ((t->u0 <= 0) && (t->u1 <= 0))
|
307 |
{
|
308 |
if ((t->d0 > 0) && (t->d1 > 0)) /* downward opening triangle */
|
309 |
{
|
310 |
v0 = tr[t->d1].lseg;
|
311 |
v1 = t->lseg;
|
312 |
if (from == t->d1)
|
313 |
{
|
314 |
do_switch = TRUE;
|
315 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
316 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
317 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
318 |
}
|
319 |
else
|
320 |
{
|
321 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
322 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
323 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
324 |
}
|
325 |
}
|
326 |
else
|
327 |
{
|
328 |
retval = SP_NOSPLIT; /* Just traverse all neighbours */
|
329 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
330 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
331 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
332 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
333 |
}
|
334 |
}
|
335 |
|
336 |
else if ((t->d0 <= 0) && (t->d1 <= 0))
|
337 |
{
|
338 |
if ((t->u0 > 0) && (t->u1 > 0)) /* upward opening triangle */
|
339 |
{
|
340 |
v0 = t->rseg;
|
341 |
v1 = tr[t->u0].rseg;
|
342 |
if (from == t->u1)
|
343 |
{
|
344 |
do_switch = TRUE;
|
345 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
346 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
347 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
348 |
}
|
349 |
else
|
350 |
{
|
351 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
352 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
353 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
354 |
}
|
355 |
}
|
356 |
else
|
357 |
{
|
358 |
retval = SP_NOSPLIT; /* Just traverse all neighbours */
|
359 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
360 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
361 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
362 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
363 |
}
|
364 |
}
|
365 |
|
366 |
else if ((t->u0 > 0) && (t->u1 > 0))
|
367 |
{
|
368 |
if ((t->d0 > 0) && (t->d1 > 0)) /* downward + upward cusps */
|
369 |
{
|
370 |
v0 = tr[t->d1].lseg;
|
371 |
v1 = tr[t->u0].rseg;
|
372 |
retval = SP_2UP_2DN;
|
373 |
if (((dir == TR_FROM_DN) && (t->d1 == from)) ||
|
374 |
((dir == TR_FROM_UP) && (t->u1 == from)))
|
375 |
{
|
376 |
do_switch = TRUE;
|
377 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
378 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
379 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
380 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
381 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
382 |
}
|
383 |
else
|
384 |
{
|
385 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
386 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
387 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
388 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
389 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
390 |
}
|
391 |
}
|
392 |
else /* only downward cusp */
|
393 |
{
|
394 |
if (_equal_to(&t->lo, &seg[t->lseg].v1))
|
395 |
{
|
396 |
v0 = tr[t->u0].rseg;
|
397 |
v1 = seg[t->lseg].next;
|
398 |
|
399 |
retval = SP_2UP_LEFT;
|
400 |
if ((dir == TR_FROM_UP) && (t->u0 == from))
|
401 |
{
|
402 |
do_switch = TRUE;
|
403 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
404 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
405 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
406 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
407 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
408 |
}
|
409 |
else
|
410 |
{
|
411 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
412 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
413 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
414 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
415 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
416 |
}
|
417 |
}
|
418 |
else
|
419 |
{
|
420 |
v0 = t->rseg;
|
421 |
v1 = tr[t->u0].rseg;
|
422 |
retval = SP_2UP_RIGHT;
|
423 |
if ((dir == TR_FROM_UP) && (t->u1 == from))
|
424 |
{
|
425 |
do_switch = TRUE;
|
426 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
427 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
428 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
429 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
430 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
431 |
}
|
432 |
else
|
433 |
{
|
434 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
435 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
436 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
437 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
438 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
439 |
}
|
440 |
}
|
441 |
}
|
442 |
}
|
443 |
else if ((t->u0 > 0) || (t->u1 > 0)) /* no downward cusp */
|
444 |
{
|
445 |
if ((t->d0 > 0) && (t->d1 > 0)) /* only upward cusp */
|
446 |
{
|
447 |
if (_equal_to(&t->hi, &seg[t->lseg].v0))
|
448 |
{
|
449 |
v0 = tr[t->d1].lseg;
|
450 |
v1 = t->lseg;
|
451 |
retval = SP_2DN_LEFT;
|
452 |
if (!((dir == TR_FROM_DN) && (t->d0 == from)))
|
453 |
{
|
454 |
do_switch = TRUE;
|
455 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
456 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
457 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
458 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
459 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
460 |
}
|
461 |
else
|
462 |
{
|
463 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
464 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
465 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
466 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
467 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
468 |
}
|
469 |
}
|
470 |
else
|
471 |
{
|
472 |
v0 = tr[t->d1].lseg;
|
473 |
v1 = seg[t->rseg].next;
|
474 |
|
475 |
retval = SP_2DN_RIGHT;
|
476 |
if ((dir == TR_FROM_DN) && (t->d1 == from))
|
477 |
{
|
478 |
do_switch = TRUE;
|
479 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
480 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
481 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
482 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
483 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
484 |
}
|
485 |
else
|
486 |
{
|
487 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
488 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
489 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
490 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
491 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
492 |
}
|
493 |
}
|
494 |
}
|
495 |
else /* no cusp */
|
496 |
{
|
497 |
if (_equal_to(&t->hi, &seg[t->lseg].v0) &&
|
498 |
_equal_to(&t->lo, &seg[t->rseg].v0))
|
499 |
{
|
500 |
v0 = t->rseg;
|
501 |
v1 = t->lseg;
|
502 |
retval = SP_SIMPLE_LRDN;
|
503 |
if (dir == TR_FROM_UP)
|
504 |
{
|
505 |
do_switch = TRUE;
|
506 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
507 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
508 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
509 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
510 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
511 |
}
|
512 |
else
|
513 |
{
|
514 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
515 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
516 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
517 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
518 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
519 |
}
|
520 |
}
|
521 |
else if (_equal_to(&t->hi, &seg[t->rseg].v1) &&
|
522 |
_equal_to(&t->lo, &seg[t->lseg].v1))
|
523 |
{
|
524 |
v0 = seg[t->rseg].next;
|
525 |
v1 = seg[t->lseg].next;
|
526 |
|
527 |
retval = SP_SIMPLE_LRUP;
|
528 |
if (dir == TR_FROM_UP)
|
529 |
{
|
530 |
do_switch = TRUE;
|
531 |
mnew = make_new_monotone_poly(mcur, v1, v0);
|
532 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
533 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
534 |
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
|
535 |
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
|
536 |
}
|
537 |
else
|
538 |
{
|
539 |
mnew = make_new_monotone_poly(mcur, v0, v1);
|
540 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
541 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
542 |
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
|
543 |
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
|
544 |
}
|
545 |
}
|
546 |
else /* no split possible */
|
547 |
{
|
548 |
retval = SP_NOSPLIT;
|
549 |
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
|
550 |
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
|
551 |
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
|
552 |
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
|
553 |
}
|
554 |
}
|
555 |
}
|
556 |
|
557 |
return retval;
|
558 |
}
|
559 |
|
560 |
|
561 |
/* For each monotone polygon, find the ymax and ymin (to determine the */
|
562 |
/* two y-monotone chains) and pass on this monotone polygon for greedy */
|
563 |
/* triangulation. */
|
564 |
/* Take care not to triangulate duplicate monotone polygons */
|
565 |
|
566 |
int triangulate_monotone_polygons(nvert, nmonpoly, op)
|
567 |
int nvert;
|
568 |
int nmonpoly;
|
569 |
int op[][3];
|
570 |
{
|
571 |
register int i;
|
572 |
point_t ymax, ymin;
|
573 |
int p, vfirst, posmax, posmin, v;
|
574 |
int vcount, processed;
|
575 |
|
576 |
#ifdef DEBUG
|
577 |
for (i = 0; i < nmonpoly; i++)
|
578 |
{
|
579 |
fprintf(stderr, "\n\nPolygon %d: ", i);
|
580 |
vfirst = mchain[mon[i]].vnum;
|
581 |
p = mchain[mon[i]].next;
|
582 |
fprintf (stderr, "%d ", mchain[mon[i]].vnum);
|
583 |
while (mchain[p].vnum != vfirst)
|
584 |
{
|
585 |
fprintf(stderr, "%d ", mchain[p].vnum);
|
586 |
p = mchain[p].next;
|
587 |
}
|
588 |
}
|
589 |
fprintf(stderr, "\n");
|
590 |
#endif
|
591 |
|
592 |
op_idx = 0;
|
593 |
for (i = 0; i < nmonpoly; i++)
|
594 |
{
|
595 |
vcount = 1;
|
596 |
processed = FALSE;
|
597 |
vfirst = mchain[mon[i]].vnum;
|
598 |
ymax = ymin = vert[vfirst].pt;
|
599 |
posmax = posmin = mon[i];
|
600 |
mchain[mon[i]].marked = TRUE;
|
601 |
p = mchain[mon[i]].next;
|
602 |
while ((v = mchain[p].vnum) != vfirst)
|
603 |
{
|
604 |
if (mchain[p].marked)
|
605 |
{
|
606 |
processed = TRUE;
|
607 |
break; /* break from while */
|
608 |
}
|
609 |
else
|
610 |
mchain[p].marked = TRUE;
|
611 |
|
612 |
if (_greater_than(&vert[v].pt, &ymax))
|
613 |
{
|
614 |
ymax = vert[v].pt;
|
615 |
posmax = p;
|
616 |
}
|
617 |
if (_less_than(&vert[v].pt, &ymin))
|
618 |
{
|
619 |
ymin = vert[v].pt;
|
620 |
posmin = p;
|
621 |
}
|
622 |
p = mchain[p].next;
|
623 |
vcount++;
|
624 |
}
|
625 |
|
626 |
if (processed) /* Go to next polygon */
|
627 |
continue;
|
628 |
|
629 |
if (vcount == 3) /* already a triangle */
|
630 |
{
|
631 |
op[op_idx][0] = mchain[p].vnum;
|
632 |
op[op_idx][1] = mchain[mchain[p].next].vnum;
|
633 |
op[op_idx][2] = mchain[mchain[p].prev].vnum;
|
634 |
op_idx++;
|
635 |
}
|
636 |
else /* triangulate the polygon */
|
637 |
{
|
638 |
v = mchain[mchain[posmax].next].vnum;
|
639 |
if (_equal_to(&vert[v].pt, &ymin))
|
640 |
{ /* LHS is a single line */
|
641 |
triangulate_single_polygon(nvert, posmax, TRI_LHS, op);
|
642 |
}
|
643 |
else
|
644 |
triangulate_single_polygon(nvert, posmax, TRI_RHS, op);
|
645 |
}
|
646 |
}
|
647 |
|
648 |
#ifdef DEBUG
|
649 |
for (i = 0; i < op_idx; i++)
|
650 |
fprintf(stderr, "tri #%d: (%d, %d, %d)\n", i, op[i][0], op[i][1],
|
651 |
op[i][2]);
|
652 |
#endif
|
653 |
return op_idx;
|
654 |
}
|
655 |
|
656 |
|
657 |
/* A greedy corner-cutting algorithm to triangulate a y-monotone
|
658 |
* polygon in O(n) time.
|
659 |
* Joseph O-Rourke, Computational Geometry in C.
|
660 |
*/
|
661 |
static int triangulate_single_polygon(nvert, posmax, side, op)
|
662 |
int nvert;
|
663 |
int posmax;
|
664 |
int side;
|
665 |
int op[][3];
|
666 |
{
|
667 |
register int v;
|
668 |
int rc[SEGSIZE], ri = 0; /* reflex chain */
|
669 |
int endv, tmp, vpos;
|
670 |
|
671 |
if (side == TRI_RHS) /* RHS segment is a single segment */
|
672 |
{
|
673 |
rc[0] = mchain[posmax].vnum;
|
674 |
tmp = mchain[posmax].next;
|
675 |
rc[1] = mchain[tmp].vnum;
|
676 |
ri = 1;
|
677 |
|
678 |
vpos = mchain[tmp].next;
|
679 |
v = mchain[vpos].vnum;
|
680 |
|
681 |
if ((endv = mchain[mchain[posmax].prev].vnum) == 0)
|
682 |
endv = nvert;
|
683 |
}
|
684 |
else /* LHS is a single segment */
|
685 |
{
|
686 |
tmp = mchain[posmax].next;
|
687 |
rc[0] = mchain[tmp].vnum;
|
688 |
tmp = mchain[tmp].next;
|
689 |
rc[1] = mchain[tmp].vnum;
|
690 |
ri = 1;
|
691 |
|
692 |
vpos = mchain[tmp].next;
|
693 |
v = mchain[vpos].vnum;
|
694 |
|
695 |
endv = mchain[posmax].vnum;
|
696 |
}
|
697 |
|
698 |
while ((v != endv) || (ri > 1))
|
699 |
{
|
700 |
if (ri > 0) /* reflex chain is non-empty */
|
701 |
{
|
702 |
if (CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
|
703 |
vert[rc[ri]].pt) > 0)
|
704 |
{ /* convex corner: cut if off */
|
705 |
op[op_idx][0] = rc[ri - 1];
|
706 |
op[op_idx][1] = rc[ri];
|
707 |
op[op_idx][2] = v;
|
708 |
op_idx++;
|
709 |
ri--;
|
710 |
}
|
711 |
else /* non-convex */
|
712 |
{ /* add v to the chain */
|
713 |
ri++;
|
714 |
rc[ri] = v;
|
715 |
vpos = mchain[vpos].next;
|
716 |
v = mchain[vpos].vnum;
|
717 |
}
|
718 |
}
|
719 |
else /* reflex-chain empty: add v to the */
|
720 |
{ /* reflex chain and advance it */
|
721 |
rc[++ri] = v;
|
722 |
vpos = mchain[vpos].next;
|
723 |
v = mchain[vpos].vnum;
|
724 |
}
|
725 |
} /* end-while */
|
726 |
|
727 |
/* reached the bottom vertex. Add in the triangle formed */
|
728 |
op[op_idx][0] = rc[ri - 1];
|
729 |
op[op_idx][1] = rc[ri];
|
730 |
op[op_idx][2] = v;
|
731 |
op_idx++;
|
732 |
ri--;
|
733 |
|
734 |
return 0;
|
735 |
}
|
736 |
|
737 |
|