What's the algorithm for laying out a circular TreeMap?

开发者_开发知识库

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

---

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.