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:
- Circular Partitions with Applications to Visualization and Embeddings
- pebbles – using Circular Treemaps to visualize disk usage
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
squarified layout by Arpit
strip layout
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:
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!
FlashDevelop
HAXE
makc
on Apr 17th, 2011
@ 12:09 am:
on my very crap netbook “pretty heavy” thing runs for 3 or 4 seconds
(which is to say it’s not heavy at all)
Arpit
on Apr 17th, 2011
@ 12:56 am:
Very cool. I am glad you could use the Treemap classes, the examples look fantastic.
I haven’t looked at my post on Treemaps in a while and I realize I never updated it. After that post I was exactly where you were, thinking how it wasn’t a good idea to use nested sprites. I did update the algorithm to use Rectangles rather than nested DisplayObjects. I also released to code on GitHub (https://github.com/arpit/treemaps/) so people could fork the code easier or add features they would like. I am updating the post now to link to the latest library.
Amazing work with the examples!
Squarified Treemaps with source !! | code zen
on Apr 17th, 2011
@ 1:02 am:
[...] Sprites and gives you a lot more control on elements you'd like to lay out. Also check out some fantastic examples using the library by [...]
nicoptere
on Apr 17th, 2011
@ 2:45 am:
@makc good :) next steps : 60 fps ^^
@arpit, thanks for passing by, for your kind words but mostly for having released the original code (even if not perfect ;) ) !
without your help, I would still wonder how to handle this thing ^^
li
on Apr 17th, 2011
@ 6:04 am:
Very nice!
Thanks for sharing the source also =)
blog.lhli.net
on Apr 17th, 2011
@ 5:06 pm:
[...] http://en.nicoptere.net/?p=1568 Apr 17, 2011 16:11 by lhli. ffffound Inga [...]
Steeve Cayla
on Apr 19th, 2011
@ 3:54 pm:
Nice, thanks for mentioning our Kap Lab!
One little thing though: Our TreeMap component is part of a reporting package, Kolbert, that bundles 4 components: TreeMap of course, but also Radar Chart, Ring Chart and Elastic Search. The price of this package is not 4000euro but 1000euro, which makes it more affordable.
The component that costs 4000euro is Kalileo, a Diagramming and graphs explorer, but that’s an other story and it doesn’t belong to this post :)
nicoptere
on Apr 19th, 2011
@ 4:32 pm:
hi, thanks for the kinds words ( @li too ) :)
@steve no offense! I can’t even imagine how much work it is to create, release and maintain a complete set of reliable tools.
in the case of KapLab, it’s a colossal work ; a complete suite that might help structure or just make possible large scale projects.
this doesn’t have to be free of charge :)
Steeve Cayla
on Apr 19th, 2011
@ 4:44 pm:
Thanks Nico for the kind words too :).
If I might add, all these components are also free with the community license that allows to develop internal applications for personal or internal use in companies. Of course there is a watermark, no source code, no support (still, we have a community forum available), but eh, it’s free ;)
Cheers!
Tarwin
on Apr 20th, 2011
@ 10:31 pm:
Man, you’ve got such a great way of explaining / showing things! Love your work!
Alan Shaw
on Sep 8th, 2011
@ 4:48 am:
Ah, very nice! I have thought about implementing Voronoi Treemaps — as described in the literature they have curved boundaries, if I remember right. So obviously they did something different — maybe involving weighted Voronoi, which is so easy to do with the bitmap region-growing technique.
But I get the idea that treemaps in general are like the Hilbert curve: easy to describe but quite confusing to implement. Wish I had time to look at your code but that will have to wait, I’m up to my goolies in evolutionary art!
BTW did you experience any “fuzzies” along the region boundaries with my code and if so did you solve it? I always thought it was an artifact of the imprecision of doing arithmetic on a BitmapData. Nowadays I would use a ByteArray in haxe.Memory for the computation…
So sorry I’m not making it to Brighton. L’austerité est en vigueur!
Nicole
on Mar 8th, 2012
@ 3:54 pm:
Great work !! In the treemap can using the untyped data ( data:* ) object to store anything you want to use later can you use this to group the nodes by color.
nicoptere
on Mar 8th, 2012
@ 4:01 pm:
thanks :)
don’t know if I get you right but, yes. you can store anything in the objects you sort.
just extend TreemapItem and create a field containing whatever you want :)
if you want to sort items by color, I’d start creating a first pass with the colors, which would give me rects representing the colors then subdivides those zones with a given amount of objects.
hoipe it helped
kochumvk
on Jun 28th, 2012
@ 10:50 am:
Great Work .
However I am facing an issue with this one.
When I Visualize complex structures, It ends up with a lot of thin long rectangles (thin strips). This limits scope of visualization inside that rectangle.
Is there a way to avoid such thin long strips. reduction in accuracy is not a problem to some extent.
example: a 32 x 32 px rectangle is much desirable than a 100 x 10 px one :)
nicoptere
on Jun 28th, 2012
@ 11:01 am:
hey, thanks :)
as far as I can remember, it’s the Ratio issue ; first make sure you use the squarified layout.
then algo will try to make the rect as close as possible to a Ratio of 1 ( 32 * 32 rather than 10 * 100 ).
but still it’s not perfect, sorry about that.
may be you can also cheat : create a custom TreemapItem and give them the same value.
this will create a layout with rectangles that have the same ratio and you can store the actual value as a parameter of your custom TreemapItem.
kochumvk
on Jun 28th, 2012
@ 11:12 am:
Thanks for your quick reply:)
I am using Squarified layout. I think I am demanding too much from the algorithm.
I am trying to avoid very small relative weights now.
Since I am visualizing a code structure, approximate sizing of rectangles are required, so making multiple treeMap Items with same weight will not work. Just my thought.
nicoptere
on Jun 28th, 2012
@ 11:31 am:
or maybe there’s a better implementation somewhere ;)
it really depends on what your set is ; with a small amount of very different data – say a 3 items’ set with 10, .2 & 0.005 values – there’s not much you can do : you’ll end up with thin stripes.
perhaps nesting the data within rectangles of ratio ~1 could help… will make it more complex and won’t necessarily solve the problem.
I can’t really figure out what you’re intending to do but I’d like to see that :)
kochumvk
on Jun 28th, 2012
@ 11:45 am:
What I am doing is a 3D visualization of a software system( you can think of a file folder structure even). I am using your stuff + away 3D 4. an added dimension is giving me kicks and pain at same time.
some folder may have 500 big files another may have 2 tiny ones… what not , even a 1000 average files in a folder will be another candidate.
kochumvk
on Jun 29th, 2012
@ 8:38 am:
Hey , Is there a way to calculate the minimum area required for packing?
nicoptere
on Jun 29th, 2012
@ 9:48 am:
( interesting project :) )
well no, actually it works the other way round : you give it the area to fill (so you have it already ), values to pack, then it normalizes the values and tries to find a layout with the best ratios to fill the area.
kochumvk
on Jul 9th, 2012
@ 9:39 am:
I did it the other way. I am now not using tremap. Instead plot the inner nodes and wrapped outer ones around it. used MaxRect Bin packing. Slow but works!
Thanks for your valuable time.
nicoptere
on Jul 9th, 2012
@ 7:06 pm:
ok,
no problem, glad I could “help”.
this MaxRect bin packer looks very interesting too :)
kochumvk
on Jul 10th, 2012
@ 8:10 am:
I am sad that I am not able to show u what I have made!.
Now that I will be back on your site again and again even if i don’t have a trouble:)
just to see what new you have done!