Lay out rectangles avoiding collisions (algorithm help)

Question

I have a (large) horizontally scrolling view, and a bunch of rectangles I'd like to position on it. Each rectangle has a desired horizontal position, but it can vary from that position by up to a certain amount (a constant, K) if needed. The rectangles must not overlap. The vertical position of the rectangles is arbitrary (constrained to the height of the view, of course).

Ideally I'd like to have the size of the rectangles being variable… I guess if that's not possible I can make the size vary in only one dimension.

Now, there will be impossibilities in this layout: since there is only a certain amount of vertical space, and they can only move K pixels away from their ideal horizontally, probably not all rectangles will be able to be drawn. To deal with this, each rectangle has a priority (P), and the lower priority ones should be omitted first. (You can assume that that is non-ambiguous, and that you can always tell which of any two rectangles has the higher priority.)

I'm after conceptual algorithm stuff, but if you need specifics, this will be run on an iPad, and there will be a few thousand (>1000 but <10,000) rectangles to consider. Ideally I'd like something quick enough to re-run every time the user changes the zoom level, but if that's not easy then I can cache the positions. The objects are photos on a timeline, and I want to get them approximately near when the event happened — I'm going for approximate so as to get more of them on there.

I've seen algorithms like this, that do the non-intersecting trick, but don't have the same idea about each item being only allowed to move by up to a certain amount. Obviously without the latter constraint, you can display all items, so I'll also need some way of knowing at what point no more rectangles can be displayed.

If solving the problem as described is too difficult, I'd welcome a suggestion of a more pragmatic idea. If all else fails, I could always do something where it goes through in priority order, renders each item in its desired place if it can, if not then tries shifting it vertically, if still not then shift it horizontally up to the allowable limit, before moving on to the next one. The priority ordering would mean that probably a sub-optimal solution would be found, but it would be weighted towards the most important items.

Answer 1

This is one way that I think this could be done.

Step 1 is to figure out all of the locations where the new yellow rectangle can be placed. Without loss of generality, we can store this as a list of all the possible X-Y positions of the upper left corner of the rectangle. Naturally, for such a huge starting area that list will contain millions of entries, so to save space let's store this list in the form of a set of rectangular areas.

For example, if our screen has pixels from X=0 to X=2999 inclusive, and from Y=0 to Y=999 inclusive, and our new rectangle has width 300 pixels and height 150 pixels, the upper left corner of our new rectangle can appear at any position from (X,Y) = (0, 0) to (2699, 849) inclusive. Let's store that as a quadruplet, [0, 0, 2699, 849].

Now when we put each existing (red) rectangle onto the screen, some of these possibilities become ruled out, since they would result in the new (yellow) rectangle overlapping them. For example, if there is a red rectangle [1100, 200, 1199, 299], then our yellow rectangle cannot have its upper left corner at any position from (X,Y) = (801, 51) to (1199, 299) inclusive.

So, replace [0, 0, 2699, 849] with four rectangular zones which cover the same area but leave the gap. There are many ways to do this but here is one: [0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849].

Keep adding more red rectangles to the screen. Each time one is added, subtract more possibilities from the list (this will usually result in the list containing more, smaller "safe zones"). (This could be very time-consuming for your full screen with 1000+ rectangles on it; if, instead, you start with just the [X-K, 0, X+K, H] space that you mentioned, then relatively few of the 1000+ will overlap this and the calculation will go much faster.) This code should be written with great care and a pile of unit tests, because fencepost errors will abound.

The end result is a complete list of possible locations on the screen where the upper left corner of your new yellow rectangle could be placed, expressed in the form of a list of rectangular zones.

Step 2: look through this list and select the most desirable location. Any rectangular zone which actually intersects your ideal vertical line will take priority. But it's possible that there will be none. In this case it is up to you to pick the most preferable option from the zones falling on the left and the zones falling on the right of the ideal line. As a hint: only one corner of each zone needs to be considered in each case (the top left corner of the zones on the right, the top right corner of the zones on the left).