views:

80

answers:

1

Hi!

Does anyone know a way to locate rectangles to best fit a certain area? The rectangles can be scaled up to a certain limit, but they should keep their proportions. I basically want to rebuild Mac OS' Exposé: Picture

Thanks, eWolf

A: 

The problem is NP Hard, but that is only for the optimal solution. What I guess you really want is a solution that just looks good.

So I suggest looking for algorithms that make data look good. Once I wanted to layout pictures for the DeepZoom Composer and I tried to recycle a graph drawing force-interaction based algorithm. http://en.wikipedia.org/wiki/Force-based_algorithms

It worked really well even for 600 hundred rectangles, you just have to play with the details of the simulation.

  • How the distance is calculated?
  • What functions do you use for the attraction and repulsion forces?
  • How much overlap are you going to accept?

The only problem I could not solve entirely, was that the rectangles formed a circle shape, rather then a big rectangle shape, which is natural when you are simulating physics. But you can work around that with carefully placed auxiliary force sources.

supo