HIDIHO!

giving something back to the Flash community

treemaps

Tags: , , , , ,


this one’s about treemaps aka space constrained visualization of hierarchical data.
treemap is shorter :)

what is it ?
well the long name says it all: we have a set of hierarchical data, a given space and we want the data to fit in the space.
this link by the inventor of the algorithm might be more explicit.
if you follow this blog, chances are that you like visualization so you might enjoy those 2 links:

this algorithm ( described here ) is used in many feed aggregators (Flipboard for instance), some online newspapers and – at an experimental state – for data visualization. partly because the results are not 100% reliable when dealing with lots of items, mostly because it is a pain to code.

still it’s a fascinating way to organize a layout given a weighted pool of things.

initially, I had to find an original layout for a shitload of items.
the items ( pictures, videos and texts ) would have to cover the biggest possible area of the screen. that’s where I heard about treemaps and all.

there are already 2 AS libs, one in Flex, the other in AS3.

both the above ( and probably some other ) are open source and there’s also a couple of paying versions (4000€ :/… 1000€, see commentslooks nice though :) ).

the treemap 2.0 by Josh is doubtlessly a good solution if you need large datavis. I read the comments, there is this guy having issues with XML format. I’m not a Flexer and when it comes to things like:

You’ll want to implement the interface mx.controls.treeClasses.ITreeDataDescriptor (and possibly ITreeDataDescriptor2). See mx.controls.treeClasses.DefaultDataDescriptor to see how Adobe implemented the default version.

the only thing I can think of is “no I don’t”.

so I chose the pure AS3 Squarified Layout by Arpit.
if you look at the source, you ‘ll see it’s more like it. or it looked more like it, Arpit did a great job and I am very thankful to him – that’s not the point – the point is that he used some properties of the DisplayObjects along with some properties of the rects.
in his version, the calculations are tightly coupled to the displayList.
this is bad because in the end you don’t get a clean, flat list of rectangles but rather a bunch of nested Sprites which is much less flexible for a later use and the items themselves are very coupled to the rendering process.
lastly, it would only perform a ‘squarified layout’, I thought it would be nice to have the other layouts :)

I’m not saying I have the best solution (far from it) but at least things are separated.
it implied so much refactoring that few of the original classes remain ; I left Arpit’s Copyright in these classes, if someone wants to improve something, just go for it :)

- “cut the crap, show something!” -

these are the 3 layouts I’ve implemented, they all work with a vertical/horizontal parameter.
slice/dice layout
slice dice

squarified layout by Arpit
squarified

strip layout
strip

for some reason, the strip layout sometimes just processes the first row and skips the rest, making it look almost like a slice dice layout. I really turn the thing upside down and couldn’t fix it… sorry for that.

a basic example goes like:

//create a map, passes the rectangle where we want to draw
var map:TreeMap = new TreeMap( new Rectangle( 10, 10, 480, 480 ) );

//create values
var values:Vector. < TreemapItem > = new Vector. < TreemapItem >;

//populate the values with basics items
for  (var i:int = 0; i < 150; i++ ) 
{
	var item:TreeMapItem = new TreeMapItem( Math.random() );//random weight
	values.push( item );
}

//compute the map
values = map.compute( values );

//render
for each( item in values )
{
	graphics.beginFill( 0x808080 + Math.random() * 0x808080 );
	graphics.drawRect( item.rect.x, item.rect.y, item.rect.width, item.rect.height );
}

after calling compute() on the treemap instance, we obtain a list of items containing the rectangle (item.rect) at the right location and size, we can then draw them wherever we need or use the rect itself to place objects.

a good thing when we have a clean list of rectangles is that we can use the result of a computation to create nested treemaps to represent depth. click to compute in a loop and again to stop.

( I love it ^^ )

next you may want to create basic interactivity and again, as the rects are clean and flat, we can perfom a simple Rectangle.contains( x, y ) on our items list instead of having to deal with nested DisplayObjects.

for each( var item:TreeMapItem in values )
{
	//simple Rectangle.contains( X, Y ) to check if the mouse is inside an item
	if ( item.rect.contains( mouseX, mouseY ) )
	{
		//do something amazing
	}
}

which gives us :

the TreeMapItem class also has an untyped data ( data:* ) object so that you can store anything you want to use later. in the swf above, I’m storing the item’s color to redraw it on Rollover.
this is handy but not really the way to go as untyped objects are the cerberus of coding hell.

instead, it’s nicer to use a custom object that extends the base TreeMapItem.
for instance in this case I’m using a customItem that extends TreeMapItem, the computation is not affected as the TreeMapItem complies with the ITreeMapItem’s requirements and the rendering is handled by the class.
click on an item to turn it white.

this is another example: the items are computed, then they copy the region of a given image. rollover the right side to retrieve the items data.

variations are numerous ; we can obtain either clear layouts or unreadable ones in both case, this algorithm is fascinating. finally as talking Voronoi is trendy, I’ll put a last example of render. I’ve used a nested treemap to distribute some points and then Alan’s Toy ( that’s not what you think… ) to render it.
it’s pretty heavy a process so here’s what it looks like in the end:
squarified
and if you’re fearless, just click below.

so here you go for the source code of the treemaps in actionscript
it contains a treemap package along with the above demos’ swf & source.

that was it!

Tags: , , , , ,

© 2009 HIDIHO!. All Rights Reserved.

This blog is powered by Wordpress and Magatheme by Bryan Helmig.