Graphviz
13.1.3~dev.20250831.0023
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 <
common/geomprocs.h
>
15
#include <limits.h>
16
#include <
ortho/partition.h
>
17
#include <
ortho/trap.h
>
18
#include <math.h>
19
#include <stdbool.h>
20
#include <stdint.h>
21
#include <stdio.h>
22
#include <stdlib.h>
23
#include <
util/alloc.h
>
24
#include <
util/bitarray.h
>
25
#include <
util/gv_math.h
>
26
#include <
util/list.h
>
27
#include <
util/prisize_t.h
>
28
29
#ifndef DEBUG
30
#define DEBUG 0
31
#endif
32
33
#define NPOINTS 4
/* only rectangles */
34
35
#define TR_FROM_UP 1
/* for traverse-direction */
36
#define TR_FROM_DN 2
37
38
#define SP_SIMPLE_LRUP 1
/* for splitting trapezoids */
39
#define SP_SIMPLE_LRDN 2
40
#define SP_2UP_2DN 3
41
#define SP_2UP_LEFT 4
42
#define SP_2UP_RIGHT 5
43
#define SP_2DN_LEFT 6
44
#define SP_2DN_RIGHT 7
45
#define SP_NOSPLIT -1
46
47
#define DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)
48
#define CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)
49
#define LENGTH(v0) hypot((v0).x, (v0).y)
50
51
#ifndef HAVE_SRAND48
52
#define srand48 srand
53
#endif
54
#ifdef _WIN32
55
extern
double
drand48
(
void
);
56
#endif
57
58
typedef
struct
{
59
int
vnum
;
60
int
next
;
/* Circularly linked list */
61
int
prev
;
/* describing the monotone */
62
int
marked
;
/* polygon */
63
}
monchain_t
;
64
65
typedef
struct
{
66
pointf
pt
;
67
int
vnext[4];
/* next vertices for the 4 chains */
68
int
vpos[4];
/* position of v in the 4 chains */
69
int
nextfree
;
70
}
vertexchain_t
;
71
72
static
int
chain_idx
;
73
static
size_t
mon_idx
;
74
/* Table to hold all the monotone */
75
/* polygons . Each monotone polygon */
76
/* is a circularly linked list */
77
static
monchain_t
*
mchain
;
78
/* chain init. information. This */
79
/* is used to decide which */
80
/* monotone polygon to split if */
81
/* there are several other */
82
/* polygons touching at the same */
83
/* vertex */
84
static
vertexchain_t
*
vert
;
85
/* contains position of any vertex in */
86
/* the monotone chain for the polygon */
87
static
int
*
mon
;
88
89
/* return a new mon structure from the table */
90
#define newmon() (++mon_idx)
91
/* return a new chain element from the table */
92
#define new_chain_element() (++chain_idx)
93
94
static
void
95
convert
(
boxf
bb,
int
flip,
int
ccw
,
pointf
* pts)
96
{
97
pts[0] = bb.
LL
;
98
pts[2] = bb.
UR
;
99
if
(
ccw
) {
100
pts[1].
x
= bb.
UR
.
x
;
101
pts[1].
y
= bb.
LL
.
y
;
102
pts[3].
x
= bb.
LL
.
x
;
103
pts[3].
y
= bb.
UR
.
y
;
104
}
105
else
{
106
pts[1].
x
= bb.
LL
.
x
;
107
pts[1].
y
= bb.
UR
.
y
;
108
pts[3].
x
= bb.
UR
.
x
;
109
pts[3].
y
= bb.
LL
.
y
;
110
}
111
if
(flip) {
112
int
i;
113
for
(i = 0; i <
NPOINTS
; i++) {
114
pts[i] =
perp
(pts[i]);
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->
is_valid
)
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
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 =
LIST_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
LIST_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 =
LIST_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 =
LIST_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 =
LIST_GET
(tr, t->
d1
).lseg;
416
v1 =
LIST_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 =
LIST_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 =
LIST_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 =
LIST_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 =
LIST_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
581
static
void
582
monotonate_trapezoids
(
int
nsegs,
segment_t
*seg, traps_t *tr,
583
int
flip, boxes_t *decomp) {
584
int
i;
585
bitarray_t
visited =
bitarray_new
(
LIST_SIZE
(tr));
586
587
mchain
=
gv_calloc
(
LIST_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 <
LIST_SIZE
(tr); j++)
595
if
(
inside_polygon
(
LIST_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
(
LIST_GET
(tr, tr_start).u0))
618
traverse_polygon
(&visited, decomp, seg, tr, 0, tr_start,
619
LIST_GET
(tr, tr_start).u0, flip,
TR_FROM_UP
);
620
else
if
(
is_valid_trap
(
LIST_GET
(tr, tr_start).d0))
621
traverse_polygon
(&visited, decomp, seg, tr, 0, tr_start,
622
LIST_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
630
static
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
643
static
void
644
dumpTrap (
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 %s\n"
, tr->
sink
,
654
tr->
usave
, tr->
uside
, tr->
is_valid
?
"valid"
:
"invalid"
);
655
}
656
fprintf (stderr,
"====\n"
);
657
}
658
659
static
void
660
dumpSegs (
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
673
boxf
*
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"
,
LIST_SIZE
(&hor_traps));
697
}
698
boxes_t hor_decomp = {0};
699
monotonate_trapezoids
((
int
)nsegs, segs, &hor_traps, 0, &hor_decomp);
700
LIST_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"
,
LIST_SIZE
(&ver_traps));
707
}
708
boxes_t vert_decomp = {0};
709
monotonate_trapezoids
((
int
)nsegs, segs, &ver_traps, 1, &vert_decomp);
710
LIST_FREE
(&ver_traps);
711
712
boxes_t rs = {0};
713
for
(
size_t
i = 0; i <
LIST_SIZE
(&vert_decomp); ++i)
714
for
(
size_t
j = 0; j <
LIST_SIZE
(&hor_decomp); ++j) {
715
boxf
newbox = {0};
716
if
(
rectIntersect
(&newbox,
LIST_GET
(&vert_decomp, i),
717
LIST_GET
(&hor_decomp, j)))
718
LIST_APPEND
(&rs, newbox);
719
}
720
721
free
(segs);
722
free
(permute);
723
LIST_FREE
(&hor_decomp);
724
LIST_FREE
(&vert_decomp);
725
boxf
*ret;
726
LIST_DETACH
(&rs, &ret, nrects);
727
return
ret;
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:47
bitarray_get
static bool bitarray_get(bitarray_t self, size_t index)
get the value of the given element
Definition
bitarray.h:65
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:80
bitarray_reset
static void bitarray_reset(bitarray_t *self)
free underlying resources and leave a bit array empty
Definition
bitarray.h:114
boxes.h
drand48
double drand48(void)
Definition
utils.c:1548
geomprocs.h
geometric functions (e.g. on points and boxes)
perp
static pointf perp(pointf p)
Definition
geomprocs.h:146
free
void free(void *)
gv_math.h
Arithmetic helper functions.
SWAP
#define SWAP(a, b)
Definition
gv_math.h:131
list.h
type-generic dynamically expanding list
LIST_DETACH
#define LIST_DETACH(list, datap, sizep)
Definition
list.h:434
LIST_AT
#define LIST_AT(list, index)
Definition
list.h:178
LIST_SIZE
#define LIST_SIZE(list)
Definition
list.h:80
LIST_APPEND
#define LIST_APPEND(list, item)
Definition
list.h:132
LIST_FREE
#define LIST_FREE(list)
Definition
list.h:379
LIST_GET
#define LIST_GET(list, index)
Definition
list.h:165
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:673
mon_idx
static size_t mon_idx
Definition
partition.c:73
NPOINTS
#define NPOINTS
Definition
partition.c:33
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:90
TR_FROM_DN
#define TR_FROM_DN
Definition
partition.c:36
DOT
#define DOT(v0, v1)
Definition
partition.c:47
convert
static void convert(boxf bb, int flip, int ccw, pointf *pts)
Definition
partition.c:95
get_angle
static double get_angle(pointf *vp0, pointf *vpnext, pointf *vp1)
Definition
partition.c:191
srand48
#define srand48
Definition
partition.c:52
chain_idx
static int chain_idx
Definition
partition.c:72
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:49
mon
static int * mon
Definition
partition.c:87
mchain
static monchain_t * mchain
Definition
partition.c:77
rectIntersect
static bool rectIntersect(boxf *d, const boxf r0, const boxf r1)
Definition
partition.c:630
monotonate_trapezoids
static void monotonate_trapezoids(int nsegs, segment_t *seg, traps_t *tr, int flip, boxes_t *decomp)
Definition
partition.c:582
new_chain_element
#define new_chain_element()
Definition
partition.c:92
TR_FROM_UP
#define TR_FROM_UP
Definition
partition.c:35
inside_polygon
static bool inside_polygon(trap_t *t, segment_t *seg)
Definition
partition.c:174
DEBUG
#define DEBUG
Definition
partition.c:30
CROSS_SINE
#define CROSS_SINE(v0, v1)
Definition
partition.c:48
store
static int store(segment_t *seg, int first, pointf *pts)
Definition
partition.c:120
vert
static vertexchain_t * vert
Definition
partition.c:84
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:38
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:58
monchain_t::next
int next
Definition
partition.c:60
monchain_t::vnum
int vnum
Definition
partition.c:59
monchain_t::prev
int prev
Definition
partition.c:61
monchain_t::marked
int marked
Definition
partition.c:62
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:29
segment_t::root0
size_t root0
Definition
trap.h:32
segment_t::v0
pointf v0
Definition
trap.h:30
segment_t::root1
size_t root1
root nodes in Q
Definition
trap.h:32
segment_t::prev
int prev
Definition
trap.h:34
segment_t::next
int next
Definition
trap.h:33
segment_t::v1
pointf v1
Definition
trap.h:30
segment_t::is_inserted
bool is_inserted
Definition
trap.h:31
trap_t
Definition
trap.h:40
trap_t::d1
size_t d1
Definition
trap.h:44
trap_t::rseg
int rseg
Definition
trap.h:41
trap_t::sink
size_t sink
pointer to corresponding in Q
Definition
trap.h:45
trap_t::lo
pointf lo
Definition
trap.h:42
trap_t::d0
size_t d0
Definition
trap.h:44
trap_t::usave
size_t usave
I forgot what this means.
Definition
trap.h:46
trap_t::u1
size_t u1
Definition
trap.h:43
trap_t::hi
pointf hi
Definition
trap.h:42
trap_t::u0
size_t u0
Definition
trap.h:43
trap_t::uside
int uside
I forgot what this means.
Definition
trap.h:47
trap_t::is_valid
bool is_valid
Definition
trap.h:48
trap_t::lseg
int lseg
Definition
trap.h:41
vertexchain_t
Definition
partition.c:65
vertexchain_t::nextfree
int nextfree
Definition
partition.c:69
vertexchain_t::vpos
int vpos[4]
Definition
partition.c:68
vertexchain_t::vnext
int vnext[4]
Definition
partition.c:67
vertexchain_t::pt
pointf pt
Definition
partition.c:66
trap.h
trapezoid elements and utilities for partition.c
is_valid_trap
static bool is_valid_trap(size_t index)
Definition
trap.h:56
construct_trapezoids
traps_t construct_trapezoids(int, segment_t *, int *)
Definition
trapezoid.c:868
equal_to
static bool equal_to(pointf v0, pointf v1)
Definition
trap.h:88
greater_than
static bool greater_than(pointf v0, pointf v1)
Definition
trap.h:92
C_EPS
#define C_EPS
Definition
trap.h:63
fp_equal
static bool fp_equal(double s, double t)
Definition
trap.h:69
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