问用给定的矩形集填充任意二维形状

EN

我认为你可以寻找包装和自动布局生成算法。自动VLSI版图生成算法可能需要类似的东西，就像纺织品版图问题.

本文Hegedüs:矩形覆盖多边形的算法似乎解决了一个类似的问题。由于这篇论文是1982年的，所以研究引用这篇文章的报纸可能会很有趣。此外，这次会议似乎正在讨论与此相关的研究问题，因此可能是对此进行研究的关键字或名称的起点。

我不知道计算几何学研究中是否有针对具体问题的算法，或者这些算法是否容易/实用到足以实现。这里是我如何处理它，如果我不得不这样做，而不能查找以前的工作。这只是一个方向，远远不是一个解决办法.

将其表述为一个优化问题。您有离散变量，您选择的矩形(是或否)和连续变量(三角形的位置和方向)。现在，您可以设置两个独立的优化:一个选择矩形的离散优化；以及一个连续优化，在给定矩形后对位置和方向进行优化。将这两个优化交织在一起。当然，困难在于优化的制定，以及错误能量的设计，这样它就不会陷入一些奇怪的配置(局部极小)。我会尝试将连续性作为一个最小二乘问题，这样我就可以使用标准的优化库。

我认为该问题适用于遗传算法和/或进化策略算法的求解。我用某种进化策略算法做过类似的装箱问题。看看这个在我的博客里。

因此，如果你使用这样的方法-编码到染色体框中：

• X坐标
• Y坐标
• 夹角

那就尽量减少这种健身功能-

Y= w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space

选择权重w1、w2、w3等影响因素的重要性。当遗传算法找到部分解时--移除仍然重叠或变形的框--你将至少有合法的(但不是必要的)最优解。

祝你在这个有趣的问题上好运！

它确实很难，而且由于它有高科技的应用，合理的效率近似策略甚至不在专利中，更不用说发表的论文了。

在有限的预算下，你能做的最好的事情就是从限制问题开始。假设所有矩形都是完全相同的，假设所有矩形都是标准矩形的二进制细分，因为您可以有效地对它们进行预打包，以适应您的核心划分。对于额外的点，您还可以形成几个固定的模式来粘合核心矩形，以覆盖几个大的形状，其比例有很大的不同。假设您可以更改标准矩形/单元格的尺寸，只要其余的(预打包和粘合模式)保持不变--这将为您提供参数，以便根据给定的矩形确定核心矩形的近似大小。

现在，您可以使用高宽比来近似这种有限的系统所能保证的错误。对于第一次迭代，假设一个简单的细分模式可以有50%的误差，然后改变模式以减少误差，但不增加预包装的渐近复杂性。在一天结束时，你总是把给定的矩形分配给你预先计算好的、现在固定的网格和二进制细分--这意味着你根本不想做布局或回溯--你总是对第一次近似地融入网格感到满意。

致力于定义与模式紧密结合的矩形类--这也是为了保持整个过程的倒置--你从来没有试图真正符合所给出的内容--您正在定义必须给出的内容，以便更好地处理它--然后您将其余部分作为错误，因为它是近似的。

然后，您可以尝试做更多，但不多-任何滑进回溯或钉任意小错误，它是指数。

如果你在一个研究机构，并能得到一些超级计算机的时间-运行一组详尽的搜索与病理混合，只是为了看看最优的包装可能是什么样子，并看看你是否可以得到更多细分模式和/或类矩形集。

对于头两年的研究来说，这应该足够了:-)