Graphviz
13.0.0~dev.20250402.0402
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
53
extern
double
drand48
(
void
);
54
#endif
55
56
typedef
struct
{
57
int
vnum
;
58
int
next
;
/* Circularly linked list */
59
int
prev
;
/* describing the monotone */
60
int
marked
;
/* polygon */
61
}
monchain_t
;
62
63
typedef
struct
{
64
pointf
pt
;
65
int
vnext[4];
/* next vertices for the 4 chains */
66
int
vpos[4];
/* position of v in the 4 chains */
67
int
nextfree
;
68
}
vertexchain_t
;
69
70
static
int
chain_idx
;
71
static
size_t
mon_idx
;
72
/* Table to hold all the monotone */
73
/* polygons . Each monotone polygon */
74
/* is a circularly linked list */
75
static
monchain_t
*
mchain
;
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 */
82
static
vertexchain_t
*
vert
;
83
/* contains position of any vertex in */
84
/* the monotone chain for the polygon */
85
static
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
92
static
void
93
convert
(
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
119
static
int
120
store
(
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
144
static
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 */
158
static
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 */
173
static
bool
174
inside_polygon
(
trap_t
*t,
segment_t
* seg)
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
190
static
double
191
get_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 */
209
static
void
210
get_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
*/
261
static
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 */
319
static
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
trap_t
*t;
323
size_t
mnew;
324
int
v0, v1;
325
326
if
(!
is_valid_trap
(trnum) ||
bitarray_get
(*visited, trnum))
327
return
;
328
329
t = &tr->
data
[trnum];
330
331
bitarray_set
(visited, trnum,
true
);
332
333
if
(t->
hi
.
y
> t->
lo
.
y
+
C_EPS
&&
fp_equal
(seg[t->
lseg
].
v0
.
x
, seg[t->
lseg
].
v1
.
x
) &&
334
fp_equal
(seg[t->
rseg
].
v0
.
x
, seg[t->
rseg
].
v1
.
x
)) {
335
boxf
newbox = {0};
336
if
(flip) {
337
newbox.
LL
.
x
= t->
lo
.
y
;
338
newbox.
LL
.
y
= -seg[t->
rseg
].
v0
.
x
;
339
newbox.
UR
.
x
= t->
hi
.
y
;
340
newbox.
UR
.
y
= -seg[t->
lseg
].
v0
.
x
;
341
}
else
{
342
newbox.
LL
.
x
= seg[t->
lseg
].
v0
.
x
;
343
newbox.
LL
.
y
= t->
lo
.
y
;
344
newbox.
UR
.
x
= seg[t->
rseg
].
v0
.
x
;
345
newbox.
UR
.
y
= t->
hi
.
y
;
346
}
347
boxes_append(decomp, newbox);
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
(!
is_valid_trap
(t->
u0
) && !
is_valid_trap
(t->
u1
)) {
361
if
(
is_valid_trap
(t->
d0
) &&
is_valid_trap
(t->
d1
)) {
// downward opening triangle
362
v0 = tr->
data
[t->
d1
].
lseg
;
363
v1 = t->
lseg
;
364
if
(from == t->
d1
)
365
{
366
mnew =
make_new_monotone_poly
(mcur, v1, v0);
367
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
368
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
369
}
370
else
371
{
372
mnew =
make_new_monotone_poly
(mcur, v0, v1);
373
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
374
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
375
}
376
}
377
else
378
{
379
/* Just traverse all neighbours */
380
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
381
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
382
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
383
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
384
}
385
}
386
387
else
if
(!
is_valid_trap
(t->
d0
) && !
is_valid_trap
(t->
d1
)) {
388
if
(
is_valid_trap
(t->
u0
) &&
is_valid_trap
(t->
u1
)) {
// upward opening triangle
389
v0 = t->
rseg
;
390
v1 = tr->
data
[t->
u0
].
rseg
;
391
if
(from == t->
u1
)
392
{
393
mnew =
make_new_monotone_poly
(mcur, v1, v0);
394
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
395
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
396
}
397
else
398
{
399
mnew =
make_new_monotone_poly
(mcur, v0, v1);
400
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
401
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
402
}
403
}
404
else
405
{
406
/* Just traverse all neighbours */
407
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
408
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
409
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
410
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
411
}
412
}
413
414
else
if
(
is_valid_trap
(t->
u0
) &&
is_valid_trap
(t->
u1
)) {
415
if
(
is_valid_trap
(t->
d0
) &&
is_valid_trap
(t->
d1
)) {
// downward + upward cusps
416
v0 = tr->
data
[t->
d1
].
lseg
;
417
v1 = tr->
data
[t->
u0
].
rseg
;
418
if
((dir ==
TR_FROM_DN
&& t->
d1
== from) ||
419
(dir ==
TR_FROM_UP
&& t->
u1
== from))
420
{
421
mnew =
make_new_monotone_poly
(mcur, v1, v0);
422
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
423
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
424
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
425
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
426
}
427
else
428
{
429
mnew =
make_new_monotone_poly
(mcur, v0, v1);
430
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
431
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
432
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
433
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
434
}
435
}
436
else
/* only downward cusp */
437
{
438
if
(
equal_to
(t->
lo
, seg[t->
lseg
].
v1
)) {
439
v0 = tr->
data
[t->
u0
].
rseg
;
440
v1 = seg[t->
lseg
].
next
;
441
442
if
(dir ==
TR_FROM_UP
&& t->
u0
== from)
443
{
444
mnew =
make_new_monotone_poly
(mcur, v1, v0);
445
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
446
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
447
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
448
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
449
}
450
else
451
{
452
mnew =
make_new_monotone_poly
(mcur, v0, v1);
453
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
454
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
455
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
456
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
457
}
458
}
459
else
460
{
461
v0 = t->
rseg
;
462
v1 = tr->
data
[t->
u0
].
rseg
;
463
if
(dir ==
TR_FROM_UP
&& t->
u1
== from)
464
{
465
mnew =
make_new_monotone_poly
(mcur, v1, v0);
466
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
467
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
468
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
469
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
470
}
471
else
472
{
473
mnew =
make_new_monotone_poly
(mcur, v0, v1);
474
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
475
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
476
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
477
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
478
}
479
}
480
}
481
}
482
else
if
(
is_valid_trap
(t->
u0
) ||
is_valid_trap
(t->
u1
)) {
// no downward cusp
483
if
(
is_valid_trap
(t->
d0
) &&
is_valid_trap
(t->
d1
)) {
// only upward cusp
484
if
(
equal_to
(t->
hi
, seg[t->
lseg
].
v0
)) {
485
v0 = tr->
data
[t->
d1
].
lseg
;
486
v1 = t->
lseg
;
487
if
(!(dir ==
TR_FROM_DN
&& t->
d0
== from))
488
{
489
mnew =
make_new_monotone_poly
(mcur, v1, v0);
490
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
491
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
492
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
493
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
494
}
495
else
496
{
497
mnew =
make_new_monotone_poly
(mcur, v0, v1);
498
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
499
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
500
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
501
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
502
}
503
}
504
else
505
{
506
v0 = tr->
data
[t->
d1
].
lseg
;
507
v1 = seg[t->
rseg
].
next
;
508
509
if
(dir ==
TR_FROM_DN
&& t->
d1
== from)
510
{
511
mnew =
make_new_monotone_poly
(mcur, v1, v0);
512
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
513
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
514
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
515
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
516
}
517
else
518
{
519
mnew =
make_new_monotone_poly
(mcur, v0, v1);
520
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
521
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
522
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
523
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
524
}
525
}
526
}
527
else
/* no cusp */
528
{
529
if
(
equal_to
(t->
hi
, seg[t->
lseg
].
v0
) &&
equal_to
(t->
lo
, seg[t->
rseg
].
v0
)) {
530
v0 = t->
rseg
;
531
v1 = t->
lseg
;
532
if
(dir ==
TR_FROM_UP
)
533
{
534
mnew =
make_new_monotone_poly
(mcur, v1, v0);
535
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
536
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
537
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
538
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
539
}
540
else
541
{
542
mnew =
make_new_monotone_poly
(mcur, v0, v1);
543
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
544
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
545
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
546
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
547
}
548
}
549
else
if
(
equal_to
(t->
hi
, seg[t->
rseg
].
v1
) &&
550
equal_to
(t->
lo
, seg[t->
lseg
].
v1
)) {
551
v0 = seg[t->
rseg
].
next
;
552
v1 = seg[t->
lseg
].
next
;
553
554
if
(dir ==
TR_FROM_UP
)
555
{
556
mnew =
make_new_monotone_poly
(mcur, v1, v0);
557
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
558
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
559
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d1
, trnum, flip,
TR_FROM_UP
);
560
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
d0
, trnum, flip,
TR_FROM_UP
);
561
}
562
else
563
{
564
mnew =
make_new_monotone_poly
(mcur, v0, v1);
565
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
566
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
567
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u0
, trnum, flip,
TR_FROM_DN
);
568
traverse_polygon
(visited, decomp, seg, tr, mnew, t->
u1
, trnum, flip,
TR_FROM_DN
);
569
}
570
}
571
else
/* no split possible */
572
{
573
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u0
, trnum, flip,
TR_FROM_DN
);
574
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d0
, trnum, flip,
TR_FROM_UP
);
575
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
u1
, trnum, flip,
TR_FROM_DN
);
576
traverse_polygon
(visited, decomp, seg, tr, mcur, t->
d1
, trnum, flip,
TR_FROM_UP
);
577
}
578
}
579
}
580
}
581
582
static
void
583
monotonate_trapezoids
(
int
nsegs,
segment_t
*seg,
traps_t
*tr,
584
int
flip, boxes_t *decomp) {
585
int
i;
586
bitarray_t
visited =
bitarray_new
(tr->
length
);
587
588
mchain
=
gv_calloc
(tr->
length
,
sizeof
(
monchain_t
));
589
vert
=
gv_calloc
(nsegs + 1,
sizeof
(
vertexchain_t
));
590
mon
=
gv_calloc
(nsegs,
sizeof
(
int
));
591
592
/* First locate a trapezoid which lies inside the polygon */
593
/* and which is triangular */
594
size_t
j;
595
for
(j = 0; j < tr->
length
; j++)
596
if
(
inside_polygon
(&tr->
data
[j], seg))
break
;
597
const
size_t
tr_start = j;
598
599
/* Initialise the mon data-structure and start spanning all the */
600
/* trapezoids within the polygon */
601
602
for
(i = 1; i <= nsegs; i++) {
603
mchain
[i].
prev
= seg[i].
prev
;
604
mchain
[i].
next
= seg[i].
next
;
605
mchain
[i].
vnum
= i;
606
vert
[i].
pt
= seg[i].
v0
;
607
vert
[i].
vnext
[0] = seg[i].
next
;
/* next vertex */
608
vert
[i].
vpos
[0] = i;
/* locn. of next vertex */
609
vert
[i].
nextfree
= 1;
610
}
611
612
chain_idx
= nsegs;
613
mon_idx
= 0;
614
mon
[0] = 1;
/* position of any vertex in the first */
615
/* chain */
616
617
/* traverse the polygon */
618
if
(
is_valid_trap
(tr->
data
[tr_start].
u0
))
619
traverse_polygon
(&visited, decomp, seg, tr, 0, tr_start,
620
tr->
data
[tr_start].
u0
, flip,
TR_FROM_UP
);
621
else
if
(
is_valid_trap
(tr->
data
[tr_start].
d0
))
622
traverse_polygon
(&visited, decomp, seg, tr, 0, tr_start,
623
tr->
data
[tr_start].
d0
, flip,
TR_FROM_DN
);
624
625
bitarray_reset
(&visited);
626
free
(
mchain
);
627
free
(
vert
);
628
free
(
mon
);
629
}
630
631
static
bool
rectIntersect
(
boxf
*d,
const
boxf
r0,
const
boxf
r1) {
632
double
t = fmax(r0.
LL
.
x
, r1.
LL
.
x
);
633
d->
UR
.
x
= fmin(r0.
UR
.
x
, r1.
UR
.
x
);
634
d->
LL
.
x
= t;
635
636
t = fmax(r0.
LL
.
y
, r1.
LL
.
y
);
637
d->
UR
.
y
= fmin(r0.
UR
.
y
, r1.
UR
.
y
);
638
d->
LL
.
y
= t;
639
640
return
!(d->
LL
.
x
>= d->
UR
.
x
|| d->
LL
.
y
>= d->
UR
.
y
);
641
}
642
643
#if DEBUG > 1
644
static
void
645
dumpTrap (
trap_t
* tr,
int
n)
646
{
647
int
i;
648
for
(i = 1; i <= n; i++) {
649
tr++;
650
fprintf(stderr,
"%d : %d %d (%f,%f) (%f,%f) %"
PRISIZE_T
" %"
PRISIZE_T
651
" %"
PRISIZE_T
" %"
PRISIZE_T
"\n"
, i, tr->
lseg
, tr->
rseg
,
652
tr->
hi
.
x
, tr->
hi
.
y
, tr->
lo
.
x
, tr->
lo
.
y
, tr->
u0
, tr->
u1
, tr->
d0
,
653
tr->
d1
);
654
fprintf(stderr,
" %"
PRISIZE_T
" %"
PRISIZE_T
" %d %d\n"
, tr->
sink
,
655
tr->
usave
, tr->
uside
, tr->
state
);
656
}
657
fprintf (stderr,
"====\n"
);
658
}
659
660
static
void
661
dumpSegs (
segment_t
* sg,
int
n)
662
{
663
int
i;
664
for
(i = 1; i <= n; i++) {
665
sg++;
666
fprintf(stderr,
"%d : (%f,%f) (%f,%f) %d %"
PRISIZE_T
" %"
PRISIZE_T
667
" %d %d\n"
, i, sg->
v0
.
x
, sg->
v0
.
y
, sg->
v1
.
x
, sg->
v1
.
y
,
668
(
int
)sg->
is_inserted
, sg->
root0
, sg->
root1
, sg->
next
, sg->
prev
);
669
}
670
fprintf (stderr,
"====\n"
);
671
}
672
#endif
673
674
boxf
*
partition
(
cell
*cells,
size_t
ncells,
size_t
*nrects,
boxf
bb) {
675
const
size_t
nsegs = 4 * (ncells + 1);
676
segment_t
* segs =
gv_calloc
(nsegs + 1,
sizeof
(
segment_t
));
677
int
* permute =
gv_calloc
(nsegs,
sizeof
(
int
));
678
679
if
(
DEBUG
) {
680
fprintf(stderr,
"cells = %"
PRISIZE_T
" segs = %"
PRISIZE_T
681
" traps = dynamic\n"
, ncells, nsegs);
682
}
683
genSegments
(cells, ncells, bb, segs, 0);
684
if
(
DEBUG
) {
685
fprintf(stderr,
"%"
PRISIZE_T
"\n\n"
, ncells + 1);
686
for
(
size_t
i = 1; i <= nsegs; i++) {
687
if
(i%4 == 1) fprintf(stderr,
"4\n"
);
688
fprintf (stderr,
"%f %f\n"
, segs[i].v0.x, segs[i].
v0
.
y
);
689
if
(i%4 == 0) fprintf(stderr,
"\n"
);
690
}
691
}
692
srand48
(173);
693
generateRandomOrdering
(nsegs, permute);
694
assert(nsegs <= INT_MAX);
695
traps_t
hor_traps =
construct_trapezoids
((
int
)nsegs, segs, permute);
696
if
(
DEBUG
) {
697
fprintf (stderr,
"hor traps = %"
PRISIZE_T
"\n"
, hor_traps.
length
);
698
}
699
boxes_t hor_decomp = {0};
700
monotonate_trapezoids
((
int
)nsegs, segs, &hor_traps, 0, &hor_decomp);
701
free
(hor_traps.
data
);
702
703
genSegments
(cells, ncells, bb, segs, 1);
704
generateRandomOrdering
(nsegs, permute);
705
traps_t
ver_traps =
construct_trapezoids
((
int
)nsegs, segs, permute);
706
if
(
DEBUG
) {
707
fprintf (stderr,
"ver traps = %"
PRISIZE_T
"\n"
, ver_traps.
length
);
708
}
709
boxes_t vert_decomp = {0};
710
monotonate_trapezoids
((
int
)nsegs, segs, &ver_traps, 1, &vert_decomp);
711
free
(ver_traps.
data
);
712
713
boxes_t rs = {0};
714
for
(
size_t
i = 0; i < boxes_size(&vert_decomp); ++i)
715
for
(
size_t
j = 0; j < boxes_size(&hor_decomp); ++j) {
716
boxf
newbox = {0};
717
if
(
rectIntersect
(&newbox, boxes_get(&vert_decomp, i),
718
boxes_get(&hor_decomp, j)))
719
boxes_append(&rs, newbox);
720
}
721
722
free
(segs);
723
free
(permute);
724
boxes_free(&hor_decomp);
725
boxes_free(&vert_decomp);
726
*nrects = boxes_size(&rs);
727
return
boxes_detach(&rs);
728
}
last
static agxbuf last
last message
Definition
agerror.c:29
alloc.h
Memory allocation wrappers that exit on failure.
gv_calloc
static void * gv_calloc(size_t nmemb, size_t size)
Definition
alloc.h:26
bitarray.h
API for compacted arrays of booleans.
bitarray_new
static bitarray_t bitarray_new(size_t size_bits)
create an array of the given element length
Definition
bitarray.h:46
bitarray_get
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
Definition
bitarray.h:64
bitarray_set
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
bitarray_reset
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
Definition
bitarray.h:98
boxes.h
drand48
double drand48(void)
Definition
utils.c:1561
free
void free(void *)
gv_math.h
Arithmetic helper functions.
SWAP
#define SWAP(a, b)
Definition
gv_math.h:130
get_vertex_positions
static void get_vertex_positions(int v0, int v1, int *ip, int *iq)
Definition
partition.c:210
partition
boxf * partition(cell *cells, size_t ncells, size_t *nrects, boxf bb)
partitions space around cells (nodes) into rectangular tiles
Definition
partition.c:674
mon_idx
static size_t mon_idx
Definition
partition.c:71
NPOINTS
#define NPOINTS
Definition
partition.c:31
genSegments
static void genSegments(cell *cells, size_t ncells, boxf bb, segment_t *seg, int flip)
Definition
partition.c:144
newmon
#define newmon()
Definition
partition.c:88
TR_FROM_DN
#define TR_FROM_DN
Definition
partition.c:34
DOT
#define DOT(v0, v1)
Definition
partition.c:45
convert
static void convert(boxf bb, int flip, int ccw, pointf *pts)
Definition
partition.c:93
get_angle
static double get_angle(pointf *vp0, pointf *vpnext, pointf *vp1)
Definition
partition.c:191
srand48
#define srand48
Definition
partition.c:50
chain_idx
static int chain_idx
Definition
partition.c:70
generateRandomOrdering
static void generateRandomOrdering(size_t n, int *permute)
Definition
partition.c:158
make_new_monotone_poly
static size_t make_new_monotone_poly(size_t mcur, int v0, int v1)
Definition
partition.c:261
LENGTH
#define LENGTH(v0)
Definition
partition.c:47
mon
static int * mon
Definition
partition.c:85
mchain
static monchain_t * mchain
Definition
partition.c:75
rectIntersect
static bool rectIntersect(boxf *d, const boxf r0, const boxf r1)
Definition
partition.c:631
monotonate_trapezoids
static void monotonate_trapezoids(int nsegs, segment_t *seg, traps_t *tr, int flip, boxes_t *decomp)
Definition
partition.c:583
new_chain_element
#define new_chain_element()
Definition
partition.c:90
TR_FROM_UP
#define TR_FROM_UP
Definition
partition.c:33
inside_polygon
static bool inside_polygon(trap_t *t, segment_t *seg)
Definition
partition.c:174
DEBUG
#define DEBUG
Definition
partition.c:28
CROSS_SINE
#define CROSS_SINE(v0, v1)
Definition
partition.c:46
store
static int store(segment_t *seg, int first, pointf *pts)
Definition
partition.c:120
vert
static vertexchain_t * vert
Definition
partition.c:82
traverse_polygon
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
partition.h
function partition, subroutine of mkMaze
prisize_t.h
PRISIZE_T
#define PRISIZE_T
Definition
prisize_t.h:25
bitarray_t
Definition
bitarray.h:37
boxf
Definition
geom.h:41
boxf::UR
pointf UR
Definition
geom.h:41
boxf::LL
pointf LL
Definition
geom.h:41
cell
result of partitioning available space, part of maze
Definition
grid.h:33
monchain_t
Definition
partition.c:56
monchain_t::next
int next
Definition
partition.c:58
monchain_t::vnum
int vnum
Definition
partition.c:57
monchain_t::prev
int prev
Definition
partition.c:59
monchain_t::marked
int marked
Definition
partition.c:60
pointf_s
Definition
geom.h:29
pointf_s::x
double x
Definition
geom.h:29
pointf_s::y
double y
Definition
geom.h:29
segment_t
Definition
trap.h:28
segment_t::root0
size_t root0
Definition
trap.h:31
segment_t::v0
pointf v0
Definition
trap.h:29
segment_t::root1
size_t root1
root nodes in Q
Definition
trap.h:31
segment_t::prev
int prev
Definition
trap.h:33
segment_t::next
int next
Definition
trap.h:32
segment_t::v1
pointf v1
Definition
trap.h:29
segment_t::is_inserted
bool is_inserted
Definition
trap.h:30
trap_t
Definition
trap.h:39
trap_t::d1
size_t d1
Definition
trap.h:43
trap_t::rseg
int rseg
Definition
trap.h:40
trap_t::sink
size_t sink
pointer to corresponding in Q
Definition
trap.h:44
trap_t::lo
pointf lo
Definition
trap.h:41
trap_t::d0
size_t d0
Definition
trap.h:43
trap_t::state
int state
Definition
trap.h:47
trap_t::usave
size_t usave
I forgot what this means.
Definition
trap.h:45
trap_t::u1
size_t u1
Definition
trap.h:42
trap_t::hi
pointf hi
Definition
trap.h:41
trap_t::u0
size_t u0
Definition
trap.h:42
trap_t::uside
int uside
I forgot what this means.
Definition
trap.h:46
trap_t::lseg
int lseg
Definition
trap.h:40
traps_t
an array of trapezoids
Definition
trap.h:60
traps_t::length
size_t length
Definition
trap.h:61
traps_t::data
trap_t * data
Definition
trap.h:62
vertexchain_t
Definition
partition.c:63
vertexchain_t::nextfree
int nextfree
Definition
partition.c:67
vertexchain_t::vpos
int vpos[4]
Definition
partition.c:66
vertexchain_t::vnext
int vnext[4]
Definition
partition.c:65
vertexchain_t::pt
pointf pt
Definition
partition.c:64
trap.h
trapezoid elements and utilities for partition.c
ST_INVALID
#define ST_INVALID
Definition
trap.h:66
is_valid_trap
static bool is_valid_trap(size_t index)
Definition
trap.h:55
construct_trapezoids
traps_t construct_trapezoids(int, segment_t *, int *)
Definition
trapezoid.c:874
equal_to
static bool equal_to(pointf v0, pointf v1)
Definition
trap.h:93
greater_than
static bool greater_than(pointf v0, pointf v1)
Definition
trap.h:97
C_EPS
#define C_EPS
Definition
trap.h:68
fp_equal
static bool fp_equal(double s, double t)
Definition
trap.h:74
ccw
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
lib
ortho
partition.c
Generated by
1.9.8