0

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

eflorico
  • 3,589
  • 2
  • 30
  • 41
  • There are a few questions about rectangle positioning in SO. For example this one http://stackoverflow.com/questions/1799662/object-positioning-algorithm/1799752#1799752, or this one http://stackoverflow.com/questions/716558/place-random-non-overlapping-rectangles-on-a-panel – Anna Nov 28 '09 at 08:58

1 Answers1

1

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
  • 105
  • 10