Graphviz  2.41.20170921.2350
tree_map.c
Go to the documentation of this file.
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 
17 static 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  */
100 rectangle* 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  */
120 rectangle 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 }
#define MAX(a, b)
Definition: agerror.c:17
#define N_NEW(n, t)
Definition: memory.h:36
#define MIN(a, b)
Definition: arith.h:35
rectangle * tree_map(int n, real *area, rectangle fillrec)
Definition: tree_map.c:100
rectangle rectangle_new(real x, real y, real width, real height)
Definition: tree_map.c:120
Definition: grammar.c:79
#define NULL
Definition: logic.h:39
EXTERN unsigned char Verbose
Definition: globals.h:64
real size[2]
Definition: tree_map.h:21
#define real
Definition: general.h:34