Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm working on visualizing a hierarchy. There will be clusters of objects, each cluster containing rectangles of fixed width but variable height. I'd like to arrange these within a rectangular space so as to have equal visual spacing between them, something like this:

mockup

download bmml source – Wireframes created with Balsamiq Mockups

Before I spend a day inventing the wheel, are there standard algorithms for this kind of distribution and space-filling? If the objects were all the same size, I'd just use a grid.

I'll be using this algorithm at two levels: once to lay out the clusters, and again to lay out the objects within each cluster. The latter would look best if they were arranged within a roughly circular space, but if that complicates things excessively I'm OK with rectangular.

I won't be showing relationships between these objects, so distance minimization is not necessary.

There's a similar question (What would be the best way to fill "space" in an User Interface for irregular image sizes gallery?) about laying out rectangular images while eliminating or minimizing white space. In my case, I want to equalize white space, clusters will be circular, and some clusters will be much larger than others.

share|improve this question
3  
This is definitely a complex problem. I think you may find some interesting things when you start looking into topics like force-directed graph layout or perhaps some of the other types of layout engines used for GraphViz. They're not a one-for-one match to your problem, but they're in the neighborhood. –  J Trana Jan 11 at 6:28
    
There certainly can be an algorithm made to answer this, it actually seems to [me / be] a semi-simple problem. I would say it's akin to adding nodes to a balanced tree; but to make it visually appealing is probably a different problem. –  TruthOf42 Jan 27 at 15:45
    
K-means clustering can be used to identify clusters –  Dave Hillier Jan 31 at 11:15
    
This is a difficult enough problem when you know the size of your container. It's far more difficult when your container size can stretch if needed. I feel your pain. –  Neil Jan 31 at 11:19
    
@JTrana: so far, your comment is the best answer. –  kevin cline Jan 31 at 11:51
add comment

migrated from ux.stackexchange.com Nov 28 '13 at 8:56

This question came from our site for user experience researchers and experts.

2 Answers

This is called in mathematics the bin packing problem. There is some example code of the application of the first fit algorithm. Tackling the distribution of white space as required in the second half of your post might be implemented by introducing the concept of elastic "glue" as it is used in the famous typesetting program TeX written by Donald E. Knuth.

share|improve this answer
add comment

I've tackled a similar problem by randomising the positions of each object, then measuring the distance and angle (or normalised gradient) to each other object and nudging them a small amount towards or away from each other based on their relationship to the other object (related=close, unrelated=far), then repeating until the distances start to fall within an acceptable range of what you want. Depending on the size of the data set it can take a while but gives good final results and can look cool in the process! :)

share|improve this answer
    
The "random" approach is an acceptable tactic for tackling certain kinds of combinatorial problems. If you are interested, look into complexity theory, including the traveling salesman problem or the bin packing problem. –  Jay Elston Feb 12 at 3:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.