Graphviz 13.0.0~dev.20241220.2304
Loading...
Searching...
No Matches
tree_map.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 <common/render.h>
12#include <math.h>
13#include <patchwork/tree_map.h>
14#include <util/alloc.h>
15#include <util/prisize_t.h>
16
17static void squarify(size_t n, double *area, rectangle *recs, size_t nadded, double maxarea, double minarea, double totalarea,
18 double asp, rectangle fillrec){
19 /* add a list of area in fillrec using squarified treemap alg.
20 n: number of items to add
21 area: area of these items, Sum to 1 (?).
22 nadded: number of items already added
23 maxarea: maxarea of already added items
24 minarea: min areas of already added items
25 asp: current worst aspect ratio of the already added items so far
26 fillrec: the rectangle to be filled in.
27 */
28 double w = fmin(fillrec.size[0], fillrec.size[1]);
29
30 if (n == 0) return;
31
32 if (Verbose) {
33 fprintf(stderr, "trying to add to rect {%f +/- %f, %f +/- %f}\n",fillrec.x[0], fillrec.size[0], fillrec.x[1], fillrec.size[1]);
34 fprintf(stderr, "total added so far = %" PRISIZE_T "\n", nadded);
35 }
36
37 if (nadded == 0){
38 nadded = 1;
39 maxarea = minarea = area[0];
40 asp = fmax(area[0] / (w * w), w * w / area[0]);
41 totalarea = area[0];
42 squarify(n, area, recs, nadded, maxarea, minarea, totalarea, asp, fillrec);
43 } else {
44 double newmaxarea, newminarea, s, h, maxw, minw, newasp, hh, ww, xx, yy;
45 if (nadded < n){
46 newmaxarea = fmax(maxarea, area[nadded]);
47 newminarea = fmin(minarea, area[nadded]);
48 s = totalarea + area[nadded];
49 h = s/w;
50 maxw = newmaxarea/h;
51 minw = newminarea/h;
52 newasp = fmax(h / minw, maxw / h);/* same as MAX{s^2/(w^2*newminarea), (w^2*newmaxarea)/(s^2)}*/
53 }
54 if (nadded < n && newasp <= asp){/* aspectio improved, keep adding */
55 squarify(n, area, recs, ++nadded, newmaxarea, newminarea, s, newasp, fillrec);
56 } else {
57 /* aspectio worsen if add another area, fixed the already added recs */
58 if (Verbose) fprintf(stderr, "adding %" PRISIZE_T
59 " items, total area = %f, w = %f, area/w=%f\n",
60 nadded, totalarea, w, totalarea/w);
61 if (fillrec.size[0] <= fillrec.size[1]) {
62 // tall rec. fix the items along x direction, left to right, at top
63 hh = totalarea/w;
64 xx = fillrec.x[0] - fillrec.size[0]/2;
65 for (size_t i = 0; i < nadded; i++){
66 recs[i].size[1] = hh;
67 ww = area[i]/hh;
68 recs[i].size[0] = ww;
69 recs[i].x[1] = fillrec.x[1] + 0.5*(fillrec.size[1]) - hh/2;
70 recs[i].x[0] = xx + ww/2;
71 xx += ww;
72 }
73 fillrec.x[1] -= hh/2;/* the new empty space is below the filled space */
74 fillrec.size[1] -= hh;
75 } else {/* short rec. fix along y top to bot, at left*/
76 ww = totalarea/w;
77 yy = fillrec.x[1] + fillrec.size[1]/2;
78 for (size_t i = 0; i < nadded; i++){
79 recs[i].size[0] = ww;
80 hh = area[i]/ww;
81 recs[i].size[1] = hh;
82 recs[i].x[0] = fillrec.x[0] - 0.5*(fillrec.size[0]) + ww/2;
83 recs[i].x[1] = yy - hh/2;
84 yy -= hh;
85 }
86 fillrec.x[0] += ww/2;/* the new empty space is right of the filled space */
87 fillrec.size[0] -= ww;
88 }
89 squarify(n - nadded, area + nadded, recs + nadded, 0, 0., 0., 0., 1., fillrec);
90 }
91
92 }
93}
94
95/* tree_map:
96 * Perform a squarified treemap layout on a single level.
97 * n - number of rectangles
98 * area - area of rectangles
99 * fillred - rectangle to be filled
100 * return array of rectangles
101 */
102rectangle* tree_map(size_t n, double *area, rectangle fillrec){
103 /* fill a rectangle rec with n items, each item i has area[i] area. */
104 double total = 0, minarea = 1., maxarea = 0., asp = 1, totalarea = 0;
105
106 for (size_t i = 0; i < n; i++) total += area[i];
107 /* make sure there is enough area */
108 if (total > fillrec.size[0] * fillrec.size[1] + 0.001)
109 return NULL;
110
111 rectangle *recs = gv_calloc(n, sizeof(rectangle));
112 squarify(n, area, recs, 0, maxarea, minarea, totalarea, asp, fillrec);
113 return recs;
114}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static bool Verbose
Definition gml2gv.c:23
node NULL
Definition grammar.y:163
#define PRISIZE_T
PRIu64 alike for printing size_t
Definition prisize_t.h:27
double x[2]
Definition tree_map.h:17
double size[2]
Definition tree_map.h:18
rectangle * tree_map(size_t n, double *area, rectangle fillrec)
Definition tree_map.c:102
static void squarify(size_t n, double *area, rectangle *recs, size_t nadded, double maxarea, double minarea, double totalarea, double asp, rectangle fillrec)
Definition tree_map.c:17
Definition grammar.c:93