3

我正在尝试将不同大小的矩形长方体彼此相邻放置，以使它们之间的接触面积最大化。

以一种蛮力的方式，我正在寻找一个可能的位置，以便将每个长方体放置在不与任何其他长方体相交的空间中。我使用 Java 3D 的BoundingBox类实现了这一点，在该类中可以检查给定框是否与给定的其他框集合相交。现在我有许多可能的位置，我需要从中选择与其他盒子接触面积最大的位置。

我的问题是我不知道如何有效地计算这个区域。一个小例子...

方框1：左下点x=0,y=0,z=0；右上角 x=10,y=10,z=10

方框2：左下点x=10,y=0,z=0；右上角 x=15,y=5,z=5

框 3 的尺寸与框 1 相同，应放置在最大接触面积的位置

在此示例中，框 3 的一侧与除框 1 的右侧（框 2 所在的位置）之外的任何位置匹配的所有位置都是最佳解决方案。

如果有人有想法甚至解决方案，我会很高兴。如果免费图书馆不太大，我也很高兴。

谢谢！

4

1 回答 1

1

依次考虑每对潜在的接触面。

将框 2 放置在与框 1 接触的任何位置。然后递归搜索。对于每个位置，您识别所有相交的长方体，然后找到最小的向上、向下、向左和向右移动，以防止与其中一个相交的长方体相交。这建立了四个新的搜索位置。然后，您也可以从中解决问题。

澄清一下，如果你向左移动，你会找到相交长方体的最右边的面并移动以使该面不再相交。其他长方体可能仍会相交，但我们将递归地远离它们。

如果没有交叉路口，则您有一个停止位置，您记下该区域并继续搜索。

如果移动使您无法触摸原始盒子，则您不会沿着该路线进一步探索。

对于每个面，您会发现要么没有位置是可能的，要么至少有一个与该面的最大接触面积。

然后对其他 5 个面重复该过程。

于 2011-03-30T00:04:20.413 回答