Alex Rivera | Logout

An algorithm to space out overlapping rectangles?

Asked 2010-07-16T14:40:29.400
100

This problem actually deals with roll-overs, I'll just generalized below as such:

I have a 2D view, and I have a number of rectangles within an area on the screen. How do I spread out those boxes such that they don't overlap each other, but only adjust them with minimal moving?

The rectangles' positions are dynamic and dependent on user's input, so their positions could be anywhere.

Attachedalt text images show the problem and desired solution

The real life problem deals with rollovers, actually.

Answers to the questions in the comments

  1. Size of rectangles is not fixed, and is dependent on the length of the text in the rollover

  2. About screen size, right now I think it's better to assume that the size of the screen is enough for the rectangles. If there is too many rectangles and the algo produces no solution, then I just have to tweak the content.

  3. The requirement to 'move minimally' is more for asethetics than an absolute engineering requirement. One could space out two rectangles by adding a vast distance between them, but it won't look good as part of the GUI. The idea is to get the rollover/rectangle as close as to its source (which I will then connect to the source with a black line). So either 'moving just one for x' or 'moving both for half x' is fine.

algorithm user-interface language-agnostic graphics
Edit
Report

1 Answer

12

Here's a guess.

Find the center C of the bounding box of your rectangles.

For each rectangle R that overlaps another.

  1. Define a movement vector v.
  2. Find all the rectangles R' that overlap R.
  3. Add a vector to v proportional to the vector between the center of R and R'.
  4. Add a vector to v proportional to the vector between C and the center of R.
  5. Move R by v.
  6. Repeat until nothing overlaps.

This incrementally moves the rectangles away from each other and the center of all the rectangles. This will terminate because the component of v from step 4 will eventually spread them out enough all by itself.

answered 2010-07-16T14:58:39.430

Your Answer