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.
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...