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