Move rectangles so they don't overlap

Question

This is a half programming, half math question.

I've got some boxes, which are represented as four corner points. They are true rectangles, the intersections of two sets of parallel lines, with every line in each set at a right angle to both lines in the other set (just so we're clear.)

For any set of n boxes, how can I efficiently calculate where to move them (the least distance) so that they do not overlap each other?

I'm working in javascript here. Here's the data:

//an array of indefinite length of boxes
//boxes represented as arrays of four points
//points represented as arrays of two things, an x and a y, measured in
//pixels from the upper left corner

var boxes = [[[504.36100124308336,110.58685958804978],[916.3610012430834,110.58685958804978],[916.3610012430834,149.58685958804978],[504.36100124308336,149.58685958804978]],[[504.4114378910622,312.3334473005064],[554.4114378910622,312.3334473005064],[554.4114378910622,396.3334473005064],[504.4114378910622,396.3334473005064]],[[479.4272869132357,343.82042608058134],[516.4272869132358,343.82042608058134],[516.4272869132358,427.82042608058134],[479.4272869132357,427.82042608058134]],[[345.0558946408693,400.12499171846],[632.0558946408694,400.12499171846],[632.0558946408694,439.12499171846],[345.0558946408693,439.12499171846]],[[164.54073131913765,374.02074227992966],[264.54073131913765,374.02074227992966],[264.54073131913765,428.02074227992966],[164.54073131913765,428.02074227992966]],[[89.76601656567325,257.7956256799442],[176.76601656567325,257.7956256799442],[176.76601656567325,311.7956256799442],[89.76601656567325,311.7956256799442]],[[60.711850703535845,103.10558195262593],[185.71185070353584,103.10558195262593],[185.71185070353584,157.10558195262593],[60.711850703535845,157.10558195262593]],[[169.5240557746245,23.743626531766495],[231.5240557746245,23.743626531766495],[231.5240557746245,92.7436265317665],[169.5240557746245,92.7436265317665]],[[241.6776988694169,24.30106373152889],[278.6776988694169,24.30106373152889],[278.6776988694169,63.30106373152889],[241.6776988694169,63.30106373152889]],[[272.7734457459479,15.53275710947554],[305.7734457459479,15.53275710947554],[305.7734457459479,54.53275710947554],[272.7734457459479,54.53275710947554]],[[304.2905062327675,-3.9599943474960035],[341.2905062327675,-3.9599943474960035],[341.2905062327675,50.04000565250399],[304.2905062327675,50.04000565250399]],[[334.86335590542114,12.526345270766143],[367.86335590542114,12.526345270766143],[367.86335590542114,51.52634527076614],[334.86335590542114,51.52634527076614]],[[504.36100124308336,110.58685958804978],[916.3610012430834,110.58685958804978],[916.3610012430834,149.58685958804978],[504.36100124308336,149.58685958804978]],[[504.4114378910622,312.3334473005064],[554.4114378910622,312.3334473005064],[554.4114378910622,396.3334473005064],[504.4114378910622,396.3334473005064]],[[479.4272869132357,343.82042608058134],[516.4272869132358,343.82042608058134],[516.4272869132358,427.82042608058134],[479.4272869132357,427.82042608058134]],[[345.0558946408693,400.12499171846],[632.0558946408694,400.12499171846],[632.0558946408694,439.12499171846],[345.0558946408693,439.12499171846]],[[164.54073131913765,374.02074227992966],[264.54073131913765,374.02074227992966],[264.54073131913765,428.02074227992966],[164.54073131913765,428.02074227992966]],[[89.76601656567325,257.7956256799442],[176.76601656567325,257.7956256799442],[176.76601656567325,311.7956256799442],[89.76601656567325,311.7956256799442]],[[60.711850703535845,103.10558195262593],[185.71185070353584,103.10558195262593],[185.71185070353584,157.10558195262593],[60.711850703535845,157.10558195262593]],[[169.5240557746245,23.743626531766495],[231.5240557746245,23.743626531766495],[231.5240557746245,92.7436265317665],[169.5240557746245,92.7436265317665]],[[241.6776988694169,24.30106373152889],[278.6776988694169,24.30106373152889],[278.6776988694169,63.30106373152889],[241.6776988694169,63.30106373152889]],[[272.7734457459479,15.53275710947554],[305.7734457459479,15.53275710947554],[305.7734457459479,54.53275710947554],[272.7734457459479,54.53275710947554]],[[304.2905062327675,-3.9599943474960035],[341.2905062327675,-3.9599943474960035],[341.2905062327675,50.04000565250399],[304.2905062327675,50.04000565250399]],[[334.86335590542114,12.526345270766143],[367.86335590542114,12.526345270766143],[367.86335590542114,51.52634527076614],[334.86335590542114,51.52634527076614]]]

This fiddle shows the boxes drawn on a canvas semi-transparently for clarity.

For simplicity, say the boxes are all aligned parallel to the x and y axes (with origin in the upper left). The fiddle is sample data, entirely usable, for testing solutions. No, it's not homework. It's curiosity. — Mario, Jul 19 '11 at 16:13
There's no need to close this question, it is a definite question with a certain solution. Given a set of boxes, which are arrays of four points, how to produce a corresponding array of non-overlapping boxes. Simply because it's a brain-puzzler doesn't make it not interesting or useful to anyone. — Mario, Jul 19 '11 at 16:15
I am a little high to this answer might not really help, but have you tried looking into graph drawing force based algorithms: http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing) — Vanson Samuel, Jul 19 '11 at 16:16
well the fiddle is useless. it's just a variable, what we suppposed to do with a variable? — Ibu, Jul 19 '11 at 16:16
Use it. It's a set of data. I could have provided no data, would you have preferred that? The comment above the variable explains the exact content of the variable. — Mario, Jul 19 '11 at 16:18
@Mario - The thing that's useless about the fiddle is that you could have just included that data in your question. — Wayne, Jul 19 '11 at 16:21
Isn't this what you're looking for: [http://stackoverflow.com/questions/2998638/fitting-rectangles-together-in-optimal-fashion][1] [1]: http://stackoverflow.com/questions/2998638/fitting-rectangles-together-in-optimal-fashion — Pedery, Jul 19 '11 at 16:24
I've updated the fiddle with an example drawing the rectangles onto a canvas. — Mario, Jul 19 '11 at 16:25
This is a bit different from that question, because I am not limiting the size of the containing rectangle, but I wish to minimize the distance the rectangles move from their initial positions. — Mario, Jul 19 '11 at 16:28

Gabe Moothart · Accepted Answer · 2011-07-19T17:44:09.570

You could use a greedy algorithm. It will be far from optimal, but may be "good enough". Here is a sketch:

 1 Sort the rectangles by the x-axis, topmost first. (n log n)
 2 for each rectangle r1, top to bottom
       //check for intersections with the rectangles below it.
       // you only have to check the first few b/c they are sorted 
 3     for every other rectangle r2 that might intersect with it 
 4         if r1 and r2 intersect //this part is easy, see @Jose's answer
 5             left = the amount needed to resolve the collision by moving r2 left
 6             right = the amount needed to resolve the collision by moving r2 right
 7             down = the amount needed to resolve the collision by moving r2 down

 8             move r2 according to the minimum value of (left, right down)
               // (this may create new collisions, they will be resolved in later steps)
 9         end if

10     end
11 end

Note step 8 could create a new collision with a prior rectangle, which wouldn't be resolved properly. Hm. You may need to carry around some metadata about previous rectangles to avoid this. Thinking...

Yes that is what I was talking about. I used to avoid that problem by updating the positions only virtually, this way you can share the movement needed to touch between each intersecting rectangle (depending on their speed) when you checked them all, so that they are always moving, otherwise you may find only one moving. — Jose Faeti, Jul 19 '11 at 18:25
are you also involved in game programming? :) personally, I never liked to resolve the collision problems later, I prefer to do a better collision checking from the start (code speed permitting). — Jose Faeti, Jul 19 '11 at 18:27

score 0 · Answer 2 · answered Jul 19 '11 at 16:47

0

Keep in mind the box model, given any two rectangles you have to calculate the two boxes width and height, adding their respective margins, paddings, and borders (add the left/right of them to detect collision on the x axis, and top/bottom to detect collision on the y axis), then you can calculate the distance between element 1 and 2 adding the result to their respective coordinate position, for example ((positionX2+totalWidth2) - (positionX1+totalWidth1)) to calculate collision along the X axis. If it is negative, they are overlapping. Once you know this, if they won't overlap by moving them, you can move them normally, otherwise you have to subtract the amount of space they are overlapping from the value you want to move them.

Since the environment is a 2D plane, this should be pretty straightforward. With a library such as jQuery would be a joke, but even in plain js is just basic addiction and subtraction.

answered Jul 19 '11 at 16:47

Jose Faeti

12,126
5
38
52

1

Calculating intersections is easy, but optimally deciding how to move the rectangles is not. – Gabe Moothart Jul 19 '11 at 17:02
What do you mean by optimally? The user asked for how to calculate the least distance to move them, I always did it like this. Once you have elements coordinates and their size, by knowing the distance between them (both along the X and Y axis) you automatically know by how much you can move them. – Jose Faeti Jul 19 '11 at 17:13
1

For 2 boxes, sure. But there are `n` boxes. How do you know that in fixing one collision you are not creating another? – Gabe Moothart Jul 19 '11 at 17:22
Because the user asked "For any two boxes, how can I efficiently calculate where to move them (the least distance) so that they do not overlap each other?". Anyway, in video games programming for example the basic way to do it is to take into consideration every single box at once, and for every one of them you check the collision with the others. Then there are more efficient and complex way, expecially for 3D environments, but I doubt this is what the user is looking for. – Jose Faeti Jul 19 '11 at 17:26
fixed. Set of n, I meant to say. I was thinking of doing it by iterating through each box and resolving collisions with all previous boxes before moving on. – Mario Jul 19 '11 at 17:28
Ok, I didn't understand it was for n boxes at once. My answer remains the same though, I would check every rectangle with each other, update positions, then go to the next rectangle and so on. This is ok if you are moving one box at a time (you didn't specify this), if more than one is moving at the same time, you may want to update the positions only at the end of every possible check to avoid unwanted overlapping. There also many ways to skip checks, for example if a rectangle is moving left, you can consider only the other rectangles to its left just to say one. – Jose Faeti Jul 19 '11 at 17:36

score 0 · Answer 3 · answered Jul 19 '11 at 18:34

Assuming the boxes are aligned to the x and y axis as in your comment, first I'd change the representation of each rectangle to 4 points: top, right, bottom, left and store them as points on the rectangle. Second, let's simplify the problem to "Given n rectangles, where is the nearest point where rectangle r can move to so that it doesn't overlap any other rectangles"? That simplifies the problem a great deal, but also should provide a decent solution. Thus, we have our function:

function deOverlapTheHonkOuttaTheRectangle(rectangle, otherRectangles){
    ..
}

Now, each other rectangle will disallow a certain range of motion for the original rectangle. Thus, you calculate all of these disallowed moves. From these, you can calculate the disallow shape that overlaps the origin and each other. For example, lets say rect1 disallows a shift of -3px to 5px right and 4px to 10px up, and rect2 disallows -4px to 1px right and -2px to 5px up. rect1 was not considered until rect2 came along, since that one overlaps the origin and rect1. Starting with rect2, you'd have [[-4, -2],[1,-2],[1,5],[-4,5]]. Figuring in rect1 gives [[-4, -2],[1,-2],[1,4],[5,4],[5,10],[-3,10],[-3,5],[-4,5]] (see image below for clarification). You keep building these up for each overlapping disallowed rectangle. Once you have considered all the rectangles, then you can use a distance formula from the origin to get the smallest distance you can move your rectangle and move it.

Disallowed Moves

Finally, you repeat this process for all remaining rectangles.

Move rectangles so they don't overlap

3 Answers3

Linked