logo标签列表

移动矩形以避免重叠

javascriptperformancegeometrycollision-detection
8
这是一个半编程、半数学的问题。
我有一些盒子，它们由四个角点表示。它们是真正的矩形，是两组平行线的交集，每组线中的每条线都与另一组线成直角（这样我们就清楚了）。
对于任何一组n个盒子，如何高效地计算它们移动的位置（最小距离），以使它们不重叠？
我在这里使用javascript进行工作。以下是数据：
//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]]]

这个 fiddle 展示了半透明绘制在画布上的方框以增强清晰度。

1
为简单起见，假设所有的盒子都与x和y轴平行（原点在左上角）。这个小工具是样本数据，完全可用于测试解决方案。不，这不是作业，只是出于好奇。 - Mario
我有点兴奋，这个答案可能并不真正有帮助，但你是否尝试过研究基于力的图形绘制算法：http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing) - Vanson Samuel
1
使用它。这是一组数据。我本可以不提供数据，你更喜欢那样吗？变量上方的注释解释了变量的确切内容。 - Mario
1
@Mario - 关于这个小提琴无用的地方在于你本可以把那些数据包含在你的问题中。 - Wayne
2
我怀疑这个问题的精确解法是NP难问题。 - Gabe Moothart
显示剩余6条评论
3个回答
4
您可以使用贪心算法。虽然它离最优解还有一段距离，但可能已经足够好了。以下是一个简要的概述：
 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

注意：第8步可能会与之前的矩形发生新的碰撞，这将无法得到正确解决。嗯，您可能需要携带一些关于先前矩形的元数据以避免这种情况。思考中...

是的，那就是我所说的。我曾经通过仅在虚拟上更新位置来避免这个问题，这样你可以分享每个相交矩形之间所需的触摸移动（取决于它们的速度），当你检查完它们时，它们总是在移动，否则你可能只会发现一个在移动。 - Jose Faeti
你也参与游戏编程吗？:) 就我个人而言，我从不喜欢后期解决碰撞问题，我更喜欢从一开始就做好碰撞检测（代码速度允许的情况下）。 - Jose Faeti
@Jose 不，我不从事游戏编程。 - Gabe Moothart
0

假设盒子与您的评论中的x和y轴对齐，首先我会将每个矩形的表示更改为4个点：顶部、右侧、底部、左侧，并将它们存储为矩形上的点。其次，让我们将问题简化为“给定n个矩形，矩形r可以移动到哪个最近的点，以便它不重叠任何其他矩形”？这大大简化了问题，但也应该提供一个不错的解决方案。因此，我们有以下函数：

function deOverlapTheHonkOuttaTheRectangle(rectangle, otherRectangles){
    ..
}

现在，每个其他的矩形都会限制原始矩形的一定范围运动。因此，您需要计算所有这些被禁止的移动。从这些中，您可以计算出与原点和其他矩形重叠的禁止形状。例如，假设rect1禁止向右移动-3px到5px，向上移动4px到10px，而rect2禁止向右移动-4px到1px，向上移动-2px到5px。直到rect2出现，rect1才被考虑，因为它与原点和rect1重叠。从rect2开始，您将得到[[-4,-2],[1,-2],[1,5],[-4,5]]。加入rect1后，您将得到[[-4,-2],[1,-2],[1,4],[5,4],[5,10],[-3,10],[-3,5],[-4,5]]（请参见下面的图像以获得澄清）。您需要为每个重叠的禁止矩形构建这些内容。一旦您考虑了所有矩形，那么您就可以使用距离公式从原点获取最小距离，并将其移动。

Disallowed Moves

最后，您需要为所有剩余的矩形重复此过程。

0

记住盒模型，给定任意两个矩形，您必须计算两个框的宽度和高度，加上它们各自的边距、填充和边框（将它们的左/右相加以检测 x 轴上的碰撞，将它们的上/下相加以检测 y 轴上的碰撞），然后您可以计算元素 1 和 2 之间的距离，将结果添加到它们各自的坐标位置中，例如 ((positionX2+totalWidth2) - (positionX1+totalWidth1)) 来计算沿 X 轴的碰撞。如果是负数，则它们重叠。一旦您知道了这一点，如果它们不会通过移动而重叠，您可以正常地移动它们，否则您必须从您想要移动它们的值中减去它们重叠的空间量。

由于环境是一个二维平面，这应该很简单。使用 jQuery 等库就像开玩笑一样，但即使在普通的 js 中也只是基本的加减法。

1
计算交点很容易，但是最优地决定如何移动矩形却不是那么简单。 - Gabe Moothart
“Optimally” 是什么意思？用户询问如何计算最小移动距离，我通常是这样做的。一旦你有了元素的坐标和大小，在了解它们之间的距离（沿 X 和 Y 轴）后，你就可以自动知道可以将它们移动多少。 - Jose Faeti
1
对于两个盒子，当然可以。但是现在有 n 个盒子。你怎么知道在解决一个碰撞的同时不会产生另一个呢？ - Gabe Moothart
因为用户问道：“对于任意两个盒子，我如何高效地计算它们应该移动到哪里（距离最短），以便它们不会重叠？”无论如何，在视频游戏编程中，例如基本的方法是同时考虑每个盒子，并且对于每个盒子，您都要检查与其他盒子的碰撞。然后还有更有效和复杂的方法，尤其是针对3D环境，但我怀疑这不是用户所寻找的。 - Jose Faeti
固定的。我是指一组 n，我的意思是逐个迭代每个框，并在继续移动之前解决与所有前面的框的碰撞。 - Mario
好的，我没有理解它是一次性对n个框执行操作。虽然如此，我的答案仍然不变，我将检查每个矩形与其他矩形的位置，更新位置，然后转到下一个矩形，以此类推。如果您一次移动多个框（您没有指定这一点），那么如果要避免意外重叠，可能希望在每次可能的检查结束时仅更新位置。还有许多跳过检查的方法，例如，如果一个矩形向左移动，则可以只考虑其左侧的其他矩形，只是举个例子。 - Jose Faeti
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接