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