Move the rectangles so that they do not overlap

Question

This is half the programming, half the math question.

I have several boxes that are presented as four corner points. They are true rectangles, the intersections of two sets of parallel lines, each line in each set at right angles to both lines in the other set (just so clear).

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

I work in javascript here. Here is 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 ay, 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 script shows drawers drawn on canvas translucent for clarity.

Answer 1

You can use the greedy algorithm. This 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 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 may create a new collision with the previous rectangle, which will not be resolved properly. Hectometer To avoid this, you may need to transfer some metadata about previous rectangles. Thinking...

Answer 2

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

Since the environment is a 2D plane, this should be fairly simple. There will be a joke with a library like jQuery, but even in simple js it's just a basic dependency and subtraction.

Answer 3

Assuming that the fields are aligned on the x and y axis, as in your comment, first I changed the presentation of each rectangle to 4 points: top, right, bottom, left and saved them as points on the rectangle. Secondly, simplify the task "Given n rectangles, where is the nearest point at which the rectangle r can move so that it does not overlap other rectangles"? This greatly simplifies the problem, but should also provide a decent solution. So we have our function:

 function deOverlapTheHonkOuttaTheRectangle(rectangle, otherRectangles){ .. } 

Now, each other rectangle will reject a specific range of motion for the original rectangle. Thus, you calculate all of these forbidden actions. From this you can calculate the form of prohibition, which overlaps the beginning and each other. For example, let's say rect1 disables -3px to 5px to the right and 4px to 10px up, and rect2 disables -4px to 1px to the right and -2px to 5px up. rect1 was not considered until rect2 appeared, since it overlaps the beginning and rect1. Starting with rect2, you will have [[-4, -2],[1,-2],[1,5],[-4,5]] . The drawing in rect1 gives [[-4, -2],[1,-2],[1,4],[5,4],[5,10],[-3,10],[-3,5],[-4,5]] (see the image below for an explanation). You continue to build them for each overlapping forbidden rectangle. After you have examined all the rectangles, you can use the distance formula from the origin to get the smallest distance that you can move your rectangle and move it.

Finally, you repeat this process for all remaining rectangles.