32#define MOVEPT(p) ((p).x += dx, (p).y += dy)
35static int GRID(
double x,
int s) {
36 const double required = ceil(x /
s);
42#define CVAL(v, s) ((v) >= 0 ? (v) / (s) : (((v) + 1) / (s)) - 1)
45#define CELL(p, s) ((p).x = CVAL((p).x, s), (p).y = CVAL((p).y, (s)))
69 a =
C * (double)ng - 1;
72 for (
size_t i = 0; i < ng; i++) {
74 W = bb.
UR.
x - bb.
LL.
x + 2 * margin;
75 H = bb.
UR.
y - bb.
LL.
y + 2 * margin;
79 d = b * b - 4.0 * a * c;
82 l1 = (-b + r) / (2 * a);
83 l2 = (-b - r) / (2 * a);
88 fprintf(stderr,
"Packing: compute grid size\n");
89 fprintf(stderr,
"a %f b %f c %f d %f r %f\n", a, b, c, d, r);
90 fprintf(stderr,
"root %d (%f) %d (%f)\n", root, l1, (
int)l2, l2);
91 fprintf(stderr,
" r1 %f r2 %f\n", a * l1 * l1 + b * l1 + c,
92 a * l2 * l2 + b * l2 + c);
101static int cmpf(
const void *
X,
const void *
Y) {
115static int sgn(
int x) {
return x > 0 ? 1 : -1; }
125 int d, x, y, ax, ay, sx, sy,
dx,
dy;
169 int ssize,
bool doS) {
187 for (
size_t j = 0; j <
ED_spl(e)->size; j++) {
204 for (; k < bz.
size; k++) {
232 const boxf bb = {.
LL = {.
x = round(bb0.
LL.
x), .y = round(bb0.
LL.
y)},
233 .UR = {.x = round(bb0.
UR.
x), .y = round(bb0.
UR.
y)}};
241 LL = (
pointf){.
x = round(LL.
x), .y = round(LL.
y)};
243 UR = (
pointf){.
x = round(UR.
x), .y = round(UR.
y)};
245 for (x = LL.
x; x <= UR.
x; x++)
246 for (y = LL.
y; y <= UR.
y; y++)
251 W =
GRID(bb0.
UR.
x - bb0.
LL.
x + 2 * margin, ssize);
252 H =
GRID(bb0.
UR.
y - bb0.
LL.
y + 2 * margin, ssize);
257 fprintf(stderr,
"%s no. cells %d W %d H %d\n",
s,
info->nc, W, H);
258 for (i = 0; i <
info->nc; i++)
259 fprintf(stderr,
" %.0f %.0f cell\n",
info->cells[i].x,
info->cells[i].y);
282 unsigned int margin = pinfo->
margin;
308 .
LL = {.
x = round(
GD_bb(subg).LL.x), .y = round(
GD_bb(subg).LL.y)},
309 .UR = {.x = round(
GD_bb(subg).UR.x), .y = round(
GD_bb(subg).UR.y)}};
322 for (
double x = bb.
LL.
x; x <= bb.
UR.
x; x++)
323 for (
double y = bb.
LL.
y; y <= bb.
UR.
y; y++)
335 pointf pt = {.
x = round(ptf.
x), .y = round(ptf.
y)};
339 .y = round(margin +
ND_ysize(n) / 2)};
343 LL = (
pointf){.
x = round(LL.
x), .y = round(LL.
y)};
345 UR = (
pointf){.
x = round(UR.
x), .y = round(UR.
y)};
347 for (
double x = LL.
x; x <= UR.
x; x++)
348 for (
double y = LL.
y; y <= UR.
y; y++)
352 pt = (
pointf){.
x = round(pt.
x), .y = round(pt.
y)};
358 pt = (
pointf){.
x = round(pt.
x), .y = round(pt.
y)};
376 pointf pt = {.
x = round(ptf.
x), .y = round(ptf.
y)};
379 .y = round(margin +
ND_ysize(n) / 2)};
383 LL = (
pointf){.
x = round(LL.
x), .y = round(LL.
y)};
385 UR = (
pointf){.
x = round(UR.
x), .y = round(UR.
y)};
387 for (
double x = LL.
x; x <= UR.
x; x++)
388 for (
double y = LL.
y; y <= UR.
y; y++)
392 pt = (
pointf){.
x = round(pt.
x), .y = round(pt.
y)};
406 fprintf(stderr,
"%s no. cells %d W %d H %d\n",
agnameof(g),
info->nc, W, H);
407 for (i = 0; i <
info->nc; i++)
408 fprintf(stderr,
" %.0f %.0f cell\n",
info->cells[i].x,
info->cells[i].y);
419 int step,
boxf *bbs) {
424 for (i = 0; i < n; i++) {
434 .y = round(bbs[
info->index].
LL.
y)};
435 place->
x = step * x - LL.
x;
436 place->
y = step * y - LL.
y;
439 for (i = 0; i < n; i++) {
448 fprintf(stderr,
"cc (%d cells) at (%d,%d) (%.0f,%.0f)\n", n, x, y, place->
x,
466 for (i = 0; i < n; i++) {
471 fprintf(stderr,
"cc (%d cells) at (%.0f,%.0f)\n", n, place->
x, place->
y);
480 int step,
unsigned int margin,
boxf *bbs) {
486 const int W =
GRID(bb.
UR.
x - bb.
LL.
x + 2 * margin, step);
487 const int H =
GRID(bb.
UR.
y - bb.
LL.
y + 2 * margin, step);
488 if (
fits(-W / 2, -H / 2,
info,
ps, place, step, bbs))
494 const double W = ceil(bb.
UR.
x - bb.
LL.
x);
495 const double H = ceil(bb.
UR.
y - bb.
LL.
y);
497 for (bnd = 1;; bnd++) {
506 for (; x > -bnd; x--)
509 for (; y > -bnd; y--)
517 for (bnd = 1;; bnd++) {
520 for (; y > -bnd; y--)
529 for (; x > -bnd; x--)
542 int i, c_cnt =
info->nc;
544 fprintf(stderr,
"%s\n", pfx);
545 for (i = 0; i < c_cnt; i++) {
546 fprintf(stderr,
"%.0f %.0f box\n", cells[i].x, cells[i].y);
552static int ucmpf(
const void *
X,
const void *
Y,
void *user_values) {
557 const unsigned int dX = userVals[x->
index];
558 const unsigned int dY = userVals[y->
index];
567static int acmpf(
const void *
X,
const void *
Y) {
586static void INC(
bool m,
size_t *c,
size_t *r,
size_t nc,
size_t nr) {
618 nc = (ng + (nr - 1)) / nr;
621 nc = (ng + (nr - 1)) / nr;
627 nr = (ng + (nc - 1)) / nc;
630 nr = (ng + (nc - 1)) / nc;
636 rowMajor ?
"row major" :
"column major", nr, nc);
637 double *widths =
gv_calloc(nc + 1,
sizeof(
double));
638 double *heights =
gv_calloc(nr + 1,
sizeof(
double));
641 for (
size_t i = 0; i < ng; i++, ip++) {
649 for (
size_t i = 0; i < ng; i++) {
661 for (
size_t i = 0; i < ng; i++, ip++) {
663 widths[c] = fmax(widths[c], ip->
width);
664 heights[r] = fmax(heights[r], ip->
height);
665 INC(rowMajor, &c, &r, nc, nr);
670 for (
size_t i = 0; i <= nc; i++) {
677 for (
size_t i = nr; 0 < i; i--) {
686 for (
size_t i = 0; i < ng; i++, ip++) {
688 const size_t idx = ip->
index;
691 places[idx].
x = round(widths[c]);
693 places[idx].
x = round(widths[c + 1] - (bb.
UR.
x - bb.
LL.
x));
696 round((widths[c] + widths[c + 1] - bb.
UR.
x - bb.
LL.
x) / 2.0);
698 places[idx].
y = round(heights[r] - (bb.
UR.
y - bb.
LL.
y));
700 places[idx].
y = round(heights[r + 1]);
703 round((heights[r] + heights[r + 1] - bb.
UR.
y - bb.
LL.
y) / 2.0);
704 INC(rowMajor, &c, &r, nc, nr);
721 fprintf(stderr,
"step size = %d\n", stepSize);
727 for (
size_t i = 0; i < ng; i++) {
734 for (
size_t i = 0; i < ng; i++) {
741 for (
size_t i = 0; i < ng; i++)
746 for (
size_t i = 0; i < ng; i++)
752 for (
size_t i = 0; i < ng; i++)
753 fprintf(stderr,
"pos[%" PRISIZE_T "] %.0f %.0f\n", i, places[i].x,
788 bool *fixed = pinfo->
fixed;
790 boxf fixed_bb = {{0, 0}, {0, 0}};
797 for (
size_t i = 0; i < ng; i++) {
800 if (fixed && fixed[i]) {
802 .
LL = {.
x = round(
GD_bb(g).LL.x), .y = round(
GD_bb(g).LL.y)},
803 .UR = {.x = round(
GD_bb(g).UR.x), .y = round(
GD_bb(g).UR.y)}};
805 fixed_bb.
LL.
x = fmin(bb.
LL.
x, fixed_bb.
LL.
x);
806 fixed_bb.
LL.
y = fmin(bb.
LL.
y, fixed_bb.
LL.
y);
807 fixed_bb.
UR.
x = fmax(bb.
UR.
x, fixed_bb.
UR.
x);
808 fixed_bb.
UR.
y = fmax(bb.
UR.
y, fixed_bb.
UR.
y);
814 fprintf(stderr,
"bb[%s] %.5g %.5g %.5g %.5g\n",
agnameof(g),
821 for (
size_t i = 0; i < ng; i++)
822 bbs[i] =
GD_bb(gs[i]);
825 fprintf(stderr,
"step size = %d\n", stepSize);
838 for (
size_t i = 0; i < ng; i++) {
851 for (
size_t i = 0; i < ng; i++) {
859 for (
size_t i = 0; i < ng; i++) {
863 for (
size_t i = 0; i < ng; i++) {
869 for (
size_t i = 0; i < ng; i++)
875 for (
size_t i = 0; i < ng; i++)
882 for (
size_t i = 0; i < ng; i++)
883 fprintf(stderr,
"pos[%" PRISIZE_T "] %.0f %.0f\n", i, places[i].x,
903 for (
size_t i = 0; i < ng; i++) {
912 for (
size_t i = 0; i < ng; i++) {
913 s =
agget(gs[i],
"sortv");
914 if (
s && sscanf(
s,
"%d", &v) > 0 && v >= 0)
959 for (
size_t i = 0; i < ng; i++) {
985 for (
size_t j = 0; j <
ED_spl(e)->size; j++) {
987 for (
size_t k = 0; k < bz.
size; k++)
1049 for (
size_t i = 0; i < ng; i++) {
1056 const double dx = p.
x;
1057 const double dy = p.
y;
1116 for (
size_t i = 0; i < ng; i++) {
1133 info.doSplines =
true;
1148 while (more && (c = *p)) {
1221 p += strlen(
"array");
1223 if (sscanf(p,
"%d", &i) > 0 && i > 0)
1227 if (sscanf(p + strlen(
"aspect"),
"%f", &v) > 0 && v > 0)
1231 }
else if (
streq(p,
"cluster")) {
1233 }
else if (
streq(p,
"graph")) {
1235 }
else if (
streq(p,
"node")) {
1241 fprintf(stderr,
"pack info:\n");
1244 fprintf(stderr,
" aspect %f\n", pinfo->
aspect);
1245 fprintf(stderr,
" size %d\n", pinfo->
sz);
1246 fprintf(stderr,
" flags %d\n", pinfo->
flags);
1272 if ((p =
agget(g,
"pack"))) {
1273 if (sscanf(p,
"%d", &i) == 1 && i >= 0)
1275 else if (*p ==
't' || *p ==
'T')
1288 fprintf(stderr,
" margin %u\n", pinfo->
margin);
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
void compute_bb(graph_t *g)
#define X(prefix, name, str, type, subtype,...)
#define PS2INCH(a_points)
geometric functions (e.g. on points and boxes)
static pointf add_pointf(pointf p, pointf q)
static pointf sub_pointf(pointf p, pointf q)
int agnnodes(Agraph_t *g)
char * agget(void *obj, char *name)
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
char * agnameof(void *)
returns a string descriptor for the object.
static int genPoly(Agraph_t *root, Agraph_t *g, ginfo *info, int ssize, pack_info *pinfo, pointf center)
pack_mode getPackModeInfo(Agraph_t *g, pack_mode dflt, pack_info *pinfo)
pack_mode parsePackModeInfo(const char *p, pack_mode dflt, pack_info *pinfo)
static pointf * arrayRects(size_t ng, boxf *gs, pack_info *pinfo)
static int fits(int x, int y, ginfo *info, PointSet *ps, pointf *place, int step, boxf *bbs)
static const char * chkFlags(const char *p, pack_info *pinfo)
static int ucmpf(const void *X, const void *Y, void *user_values)
Sort by user values.
static int sgn(int x)
sgn, as defined in Graphics Gems I, §11.8, pp. 99
pack_mode getPackMode(Agraph_t *g, pack_mode dflt)
static const char * mode2Str(pack_mode m)
static int cmpf(const void *X, const void *Y)
static pointf * polyRects(size_t ng, boxf *gs, pack_info *pinfo)
static void shiftGraph(Agraph_t *g, double dx, double dy)
pointf * putRects(size_t ng, boxf *bbs, pack_info *pinfo)
int packSubgraphs(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
static void placeGraph(size_t i, ginfo *info, PointSet *ps, pointf *place, int step, unsigned int margin, boxf *bbs)
int pack_graph(size_t ng, Agraph_t **gs, Agraph_t *root, bool *fixed)
Pack subgraphs followed by postprocessing.
int getPack(Agraph_t *g, int not_def, int dflt)
int packRects(size_t ng, boxf *bbs, pack_info *pinfo)
static void placeFixed(ginfo *info, PointSet *ps, pointf *place, pointf center)
int packGraphs(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
static int GRID(double x, int s)
given cell size s, how many cells are required by size x?
static void fillLine(pointf p, pointf q, PointSet *ps)
static int computeStep(size_t ng, boxf *bbs, unsigned int margin)
static int acmpf(const void *X, const void *Y)
Sort by height + width.
static pointf * polyGraphs(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *pinfo)
static void fillEdge(Agedge_t *e, pointf p, PointSet *ps, double dx, double dy, int ssize, bool doS)
int shiftGraphs(size_t ng, Agraph_t **gs, pointf *pp, Agraph_t *root, bool doSplines)
pack_mode getPackInfo(Agraph_t *g, pack_mode dflt, int dfltMargin, pack_info *pinfo)
static void genBox(boxf bb0, ginfo *info, int ssize, unsigned int margin, pointf center, char *s)
pointf * putGraphs(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *pinfo)
static void shiftEdge(Agedge_t *e, double dx, double dy)
Translate all of the edge components by the given offset.
support for connected components
void addPS(PointSet *ps, double x, double y)
void insertPS(PointSet *ps, pointf pt)
void freePS(PointSet *ps)
pointf * pointsOf(PointSet *ps)
int inPS(PointSet *ps, pointf pt)
point containers PointSet and PointMap
void dotneato_postprocess(Agraph_t *g)
#define PRISIZE_T
PRIu64 alike for printing size_t
qsort with carried along context
static void gv_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *, void *), void *arg)
qsort with an extra state parameter, ala qsort_r
static bool startswith(const char *s, const char *prefix)
does the string s begin with the string prefix?
static bool streq(const char *a, const char *b)
are a and b equal?
size_t index
index in original array
result of partitioning available space, part of maze
size_t index
index in original array
pointf * cells
cells in covering polyomino
bool doSplines
use splines in constructing graph shape
static point center(point vertex[], size_t n)