Treemap/Algorithms
Treemap
A related interesting layout algorithm representing relative volume is squarified treemap
It would be an interesting tool for displaying a hierarchy or list of name/size pairs. It would make a good companion to the tree view for a side-by-side display.
-- Oleg Kobchenko <<DateTime(2007-06-23T22:12:10Z)>>
I have a treemap already implemented in J, and will make it available in the next day or so -- Chris Burke <<DateTime(2007-06-24T12:39:12Z)>>
Squarified Treemap Partitions
Following the example in the original algorithm,
The first step of our algorithm is to split the initial rectangle.We choose for a horizontal subdivision, because the original rectangle is wider than high. We next fill the left half. First we add a single rectangle (figure 4). The aspect ratio of this first rectangle is 8/3. Next we add a second rectangle, above the first. The aspect ratios improve to 3/2. However, if we add the next (area 4) above these original rectangles, the aspect ratio of this rectangle is 4/1. Therefore, we decide that we have reached an optimum for the left half in step two, and start processing the right half.
The initial subdivision we choose here is vertical, because the rectangle is higher than wide. In step 4 we add the rectangle with area 4, followed by the rectangle with area 3 in step 5. The aspect ratio decreases. Addition of the next (area 2) however does not improve the result, so we accept the result of step 5, and start to fill the right top partition.
These steps are repeated until all rectangles have been processed. Again, an optimal result can not be guaranteed, and counterexamples can be set up. The order in which the rectangles are processed is important.We found that a decreasing order usually gives the best results. The initially large rectangle is then filled in first with the larger subrectangles.
such J implementation below is possible. Collecting rectangles along the way will yield the sought layout. The actual tree (hierarchy) is done recursively for children on each level inside parent's rectangle, whose size is total of its children.
NB. squarified treemap partition
NB. add v ratio<1 of new rect
NB. x: w,h y: prev,next areas
add=: [:%^:(1&<) (>./@[ * [:*:+/@]) % (<./@[ * {:@] * */@[)
NB. step v number of affected items
NB. x: w,h y: list
step=: 4 : 0
p=. r=. 0
for_i. i.#y do.
if. r>R=. x add p,i{y do. i return. end.
r=. R [ p=. p+i{y
end.
#y
)
NB. shrink v w,h by new item
NB. x: w,h y: new area
shrink=: [ |.@]^:(>/@[) <./@[ , >./@[ * */@[ (- % [) ]
NB. part v partition in directions
NB. x: w,h y: list
part=: 4 : 0
z=. ''
while. #y do.
s=. x step y
z=. z,<p=. s{.y
y=. s}.y
x=. x shrink +/p
end.
z
)
Test
6 4 part 6 6 4 3 2 2 1 +---+---+-+-+-+ |6 6|4 3|2|2|1| +---+---+-+-+-+
{{{1}}}
+/6 6 3 2 2 19 (*/640 480) 307200 6 6 3 2 2 * (*/640 480) % +/6 6 3 2 2 97010.5 97010.5 48505.3 32336.8 32336.8 +/ 6 6 3 2 2 * (*/640 480) % +/6 6 3 2 2 307200
It's best to keep all calculations in floating point and uniformly make them integer (e.g. floor) explicitly before drawing to achieve precise touching (overlapping by 1 border pixel) rectangles.
-- Oleg Kobchenko <<DateTime(2007-07-04T03:30:34Z)>>
Squarified Treemap Rectangles
Continuing the partition approach we accumulate rectangles passing both X,Y and W,H. When partition ends (by worsening the ratio away from 1), the accumulated items are stacked along the shorter edge or its parent.
The view here is obtained with
400 600 rects (2000 ?@$ 100)^2000 ?@$ 10
There are three parts separating the processing layers (such approach allows reusing the algorithms in other generic applications).
- orientation aware operations stack and shrink with symmetrical processing
- partitioning iterators part and step, controlled by ratio
- small visualizer rects
NB. squarified treemap rectangles
NB. stack v row or column of items
NB. x: x,y,w,h y: items
stack=: 4 : 0
'X Y W H'=. x
if. W>H do.
w1=. (+/y) % H
h1=. H * (% +/) y
x1=. X
y1=. Y + +/\0,}:h1
else.
h1=. (+/y) % W
w1=. W * (% +/) y
y1=. Y
x1=. X + +/\0,}:w1
end.
x1,.y1,.w1,.h1
)
NB. shrink v rect by new items at edge
NB. x: x,y,w,h y: new items
shrink=: 4 : 0
'X Y W H'=. x
'x1 y1 w1 h1'=. ,x stack ,(W*H) - y
if. W>H do.
x1=. x1 + W-w1
else.
y1=. y1 + H-h1
end.
x1,y1,w1,h1
)
NB. =========================================================
NB. ratio v of new rect
NB. x: x,y,w,h y: prev,next areas
ratio=: [:%^:(1&<) (>./@[ * [:*:+/@]) % (<./@[ * {:@] * */@[)
NB. step v affected rects
NB. x: x,y,w,h y: list
step=: 4 : 0
p=. r=. 0
for_i. i.#y do.
if. r>R=. (2}.x) ratio p,i{y do. x stack i{.y return. end.
r=. R [ p=. p+i{y
end.
x stack y
)
NB. part v partition into rects
NB. x: x,y,w,h y: screen unit list
part=: 4 : 0
z=. i.0 4
while. #y do.
s=. #L=. x step y
z=. z,L
x=. x shrink +/s{.y
y=. s}.y
end.
z
)
NB. level v partition world units
NB. x: x,y,w,h y: world unit list
level=: 4 : 0
x part (*/2}.x) * (% +/) \:~y
)
align=: 2 ({. , 1+}.-{.)"1 [: <. 2 ({. , {.+}.)"1 ]
NB. =============================t==========================
NB. rects v show level in graphics
NB. eg. 600 400 rects 6 6 4 3 2 2 1
rects=: 600 400&$: : (4 : 0)
require 'gl2'
cocurrent conew >coname''
coinsert 'jgl2'
T=: y
f_close=: [: codestroy '' [ wd bind 'pclose'
p=. 'glpen 1,PS_SOLID [ glrgb 0 0 0 [ glclear i.0'
f_g_paint=: 3 : (p;'glrect"1 align T level~ 0 0,glqwh i.0')
wd 'pc f; pn *Squarified Treemap Rectangles'
wd 'xywh 0 0 ',(":x%2),';cc g isigraph rightmove bottommove;'
wd 'pas 0 0;pcenter;pshow;'
)
-- Oleg Kobchenko <<DateTime(2007-07-04T05:49:03Z)>>
Nested Treemap
To accomodate nested treemap, each level is processed recursively. The input is boxed hierarchy where each open item is an input to levels, i.e. list of sizes.
The view here is obtained with
400 600 nest randtree 5 4 5 10
The main verb to generate nested rectanlges is tree, which is very simple and just calls levels to do the work recursively.
To generate an example randtree is used.
randtree 3 4 5 10 +-------+--------------------+----+-------------+ |3 3 2 8|+-------+----------+|10 9|+-+-+-------+| | ||+-+---+|2 5 10 1 2|| ||4|1|8 7 4 8|| | |||7|4 5|| || |+-+-+-------+| | ||+-+---+| || | | | |+-------+----------+| | | +-------+--------------------+----+-------------+
A slightly modified GUI verb nest produces graphicsl result. Items on each open level (leaves) are colored with a common color, i.e. color distinuishes containers and items inside containers are the same color.
NB. =========================================================
NB. randtree v random tree
NB. y: levels, children, values, range
randtree=: 3 : 0
'L C V R'=: y
if. +./0 = L,c=. ?C do. 1+(1+?V) ?@$ R return. end.
<@randtree"1 (L-1),.(1+C ?@$ L),"0 1]V,.R
)
NB. tree v nested levels
NB. x: x,y,w,h y: world unit boxed list
tree=: 4 : 0
if. 0=L. y do. x level y return. end.
(<"1 x level ;([: +/@; < S: 0) &.> y) tree&.> y
)
COLORS=: <:64+32*1+4 4 4#:i.4^3
cellrect=: COLORS ((#@] <"1@$ [) ,. ]) [: <S:0 tree
show=: 4 : 0
glbrush ''[ glrgb x
glrect"1 align y
)
NB. =========================================================
NB. nest v show nested treemap
NB. eg. 400 600 nest randtree 5 4 5 10
nest=: 600 400&$: : (4 : 0)
require 'gl2'
cocurrent conew >coname''
coinsert 'jgl2'
T=: y
f_close=: [: codestroy '' [ wd bind 'pclose'
p=. 'glpen 1,PS_SOLID [ glrgb 3#255 [ glclear i.0'
f_g_paint=: 3 : (p;'show&>/"1 (0 0,glqwh i.0) cellrect T')
wd 'pc f; pn *Nested Squarified Treemap'
wd 'xywh 0 0 ',(":x%2),';cc g isigraph rightmove bottommove;'
wd 'pas 0 0;pcenter;pshow;'
)
-- Oleg Kobchenko <<DateTime(2007-07-05T00:24:09Z)>>
I added a treemap verb that you can use to experiment with this. Note a slight difference in that the treemap verb displays larger rectangles at upper left, down to smaller rectangles at bottom right. -- Chris Burke <<DateTime(2007-07-04T02:45:24Z)>>
The direct verb is very nice: like plot and grid. Coordinate orientation is not an issue.
Current treemap does not handle nested trees, right? How best to represent them: nested boxes, two column relational or interface with methods (0 index is root):
interface Tree {
value(index) : numeric size;
children(index) : list of indices;
}
-- Oleg Kobchenko <<DateTime(2007-07-04T03:30:34Z)>>