5

Given a standard nested circular treemap, how do you calculate the where to place the circles?

Montgomery 'monty' Jones
  • 1,061
  • 2
  • 14
  • 27
  • 2
    Have you looked [here](http://en.wikipedia.org/wiki/Treemapping#The_tiling_algorithm)? and [here](http://www.jsoftware.com/jwiki/Treemap/Algorithms)? Also, is this possibly related to this [question](http://stackoverflow.com/questions/5371869/venn-diagram-generation-software-from-rcc8-specification-or-similar)? – MarcoS Mar 31 '11 at 09:43
  • 1
    +1 @MarcoS. Also, [here](http://www.randelshofer.ch/treeviz/) is an implementation in Java (with source code) – CMR Apr 06 '11 at 12:56

1 Answers1

1

Your main problem can be described as this: "Given a set of circles of varying radius, how does one place them within a larger circle, so that none of them overlap".

It's a hard problem, but here's a brute force solution to get you started:

  1. Sort the circles by size
  2. Place the largest circle on the inner rim of the bounding circle
  3. For the rest of the circles (r1), do the following:
    1. Iterate over all pairs of already placed circles (r2,r3) (including the outer one)
    2. Find the (one or two) points that have distance r1+r2 to the first circle and r1+r3 to the second circle.
    3. Try to place the new circle here.

The above uses the observation that in a perfect packing, every circle must border to at least two other circles. You can use the algorithm to provide a full search, or you can just iterate randomly and greedily choose the first available spot.

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114