1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "render.h"
15#include "tree_map.h"
16
17static void squarify(int n, real *area, rectangle *recs, int nadded, real maxarea, real minarea, real totalarea,
18 real 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 real w = MIN(fillrec.size[0], fillrec.size[1]);
29 int i;
30
31 if (n <= 0) return;
32
33 if (Verbose) {
34 fprintf(stderr, "trying to add to rect {%f +/- %f, %f +/- %f}\n",fillrec.x[0], fillrec.size[0], fillrec.x[1], fillrec.size[1]);
35 fprintf(stderr, "total added so far = %d\n", nadded);
36 }
37
38 if (nadded == 0){
39 nadded = 1;
40 maxarea = minarea = area[0];
41 asp = MAX(area[0]/(w*w), (w*w)/area[0]);
42 totalarea = area[0];
43 squarify(n, area, recs, nadded, maxarea, minarea, totalarea, asp, fillrec);
44 } else {
45 real newmaxarea, newminarea, s, h, maxw, minw, newasp, hh, ww, xx, yy;
46 if (nadded < n){
47 newmaxarea = MAX(maxarea, area[nadded]);
48 newminarea = MIN(minarea, area[nadded]);
49 s = totalarea + area[nadded];
50 h = s/w;
51 maxw = newmaxarea/h;
52 minw = newminarea/h;
53 newasp = MAX(h/minw, maxw/h);/* same as MAX{s^2/(w^2*newminarea), (w^2*newmaxarea)/(s^2)}*/
54 }
55 if (nadded < n && newasp <= asp){/* aspectio improved, keep adding */
56 squarify(n, area, recs, ++nadded, newmaxarea, newminarea, s, newasp, fillrec);
57 } else {
58 /* aspectio worsen if add another area, fixed the already added recs */
59 if (Verbose) fprintf(stderr,"adding %d items, total area = %f, w = %f, area/w=%f\n",nadded, totalarea, w, totalarea/w);
60 if (w == fillrec.size[0]){/* tall rec. fix the items along x direction, left to right, at top*/
61 hh = totalarea/w;
62 xx = fillrec.x[0] - fillrec.size[0]/2;
63 for (i = 0; i < nadded; i++){
64 recs[i].size[1] = hh;
65 ww = area[i]/hh;
66 recs[i].size[0] = ww;
67 recs[i].x[1] = fillrec.x[1] + 0.5*(fillrec.size[1]) - hh/2;
68 recs[i].x[0] = xx + ww/2;
69 xx += ww;
70 }
71 fillrec.x[1] -= hh/2;/* the new empty space is below the filled space */
72 fillrec.size[1] -= hh;
73 } else {/* short rec. fix along y top to bot, at left*/
74 ww = totalarea/w;
75 yy = fillrec.x[1] + fillrec.size[1]/2;
76 for (i = 0; i < nadded; i++){
77 recs[i].size[0] = ww;
78 hh = area[i]/ww;
79 recs[i].size[1] = hh;
80 recs[i].x[0] = fillrec.x[0] - 0.5*(fillrec.size[0]) + ww/2;
81 recs[i].x[1] = yy - hh/2;
82 yy -= hh;
83 }
84 fillrec.x[0] += ww/2;/* the new empty space is right of the filled space */
85 fillrec.size[0] -= ww;
86 }
87 squarify(n - nadded, area + nadded, recs + nadded, 0, 0., 0., 0., 1., fillrec);
88 }
89
90 }
91}
92
93/* tree_map:
94 * Perform a squarified treemap layout on a single level.
95 * n - number of rectangles
96 * area - area of rectangles
97 * fillred - rectangle to be filled
98 * return array of rectangles
99 */
100rectangle* tree_map(int n, real *area, rectangle fillrec){
101 /* fill a rectangle rec with n items, each item i has area[i] area. */
102 rectangle *recs;
103 int i;
104 real total = 0, minarea = 1., maxarea = 0., asp = 1, totalarea = 0;
105 int nadded = 0;
106
107 for (i = 0; i < n; i++) total += area[i];
108 /* make sure there is enough area */
109 if (total > fillrec.size[0] * fillrec.size[1] + 0.001)
110 return NULL;
111
112 recs = N_NEW(n,rectangle);
113 squarify(n, area, recs, nadded, maxarea, minarea, totalarea, asp, fillrec);
114 return recs;
115}
116
117/* rectangle_new:
118 * Create and initialize a new rectangle structure
119 */
120rectangle rectangle_new(real x, real y, real width, real height){
121 rectangle r;
122 r.x[0] = x;
123 r.x[1] = y;
124 r.size[0] = width;
125 r.size[1] = height;
126 return r;
127}
128