移动矩形，使它们不重叠 [英] Move rectangles so they don't overlap

问题描述

我有一些框，它们被表示为四个角点。它们是真正的矩形，两组平行线的交集，每组中的每一行都与另一组中的两条直线成直角（只是这样我们就清楚了。）

对于任何一组n个框，我怎样才能有效地计算它们移动的位置（最小距离），以便它们不会相互重叠？

我在这里工作的JavaScript。这里是数据：

  //一个无限长盒子数组
 //盒子表示为四点数组
 //点表示为两个元素的数组，一个x和ay，以
 //像素为单位，从左上角开始测量
 
 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,4 28.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 0.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]]] 
  

这个小提琴显示半透明画布上的框以清楚起见。

解决方案

您可以使用贪婪算法。这将远非最佳，但可能足够好。这里是一个草图：

  1用x轴排序矩形，最上面的第一个。 （n log n）
 2为每个矩形r1，从上到下
 //检查与它下面矩形的交点。 
 //你只需要检查它们排序的前几个b / c 
 3对于可能与其相交的每个其他矩形r2 
 4如果r1和r2相交//这部分是很容易，请参阅@ Jose的答案
 5 left =通过移动r2离开解决冲突所需的金额左边
 6 right =通过右移r2来解决冲突所需的金额
 7 down =通过移动r2减少
 
来解决碰撞所需的金额8根据（左，右下）
 //的最小值移动r2（这可能会产生新的碰撞，它们将被解析在后面的步骤中）
 9结束如果
 
 10结束
 11结束
  

注意第8步可能会与之前的矩形创建一个新的碰撞，这将不会被正确解析。嗯。您可能需要携带一些关于先前矩形的元数据以避免这种情况。思考......

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

这篇关于移动矩形，使它们不重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！