logo标签列表

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

algorithmgeometrycomputational-geometry
26

我有一组在二维空间中的矩形和任意形状。该形状不一定是一个多边形（可能是一个圆），而且矩形具有不同的宽度和高度。任务是尽可能接近用矩形来逼近该形状。 我不能改变矩形的大小，但允许旋转。

听起来非常类似于装箱问题和覆盖问题，但覆盖区域不是矩形...

我想这是NP问题，我很确定应该有一些论文展示了好的启发式算法来解决它，但我不知道该怎么搜索？我应该从哪里开始？

更新：我突然想到一个主意，但我不确定是否值得研究。如果我们将边界形状视为充满水的物理模具。每个矩形都被认为是一个具有大小的正电荷粒子。现在将最小的矩形放在里面。然后在随机点上按大小放置下一个矩形。如果矩形太靠近，则彼此排斥。继续添加矩形直到所有矩形都被使用。这种方法能行吗？

你是想尽可能地紧密打包吗？还是尽可能地近似形状？你是在优化数学函数，还是更注重美观？ - brainjam
关于这个充电矩形方法，它可能不一定会给出最优的配置，因为我们首先使用随机化来放置它们。 - Lazer
优先级是什么 - 追踪边界还是填充形状？我的意思是，如果矩形完美地追踪边界但在中间留下一个洞，这样可以吗？ - Lazer
1
@CuriousG 你最终采用了哪个解决方案？ - tommy.carstensen
3个回答
16

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

这篇论文Hegedüs: Algorithms for covering polygons by rectangles似乎解决了类似的问题。由于这篇论文是1982年的，因此查看引用此论文的论文可能会很有趣。此外，这个会议似乎正在讨论与此相关的研究问题，因此可能是关键词或进行此方面研究的人员的起点。

我不知道计算几何研究是否具有您特定问题的算法，或者这些算法是否足够容易/实用来实现。 如果我必须在无法查找以前的工作的情况下处理它，那么我会如何处理。 这只是一个方向，远远不是解决方案...

将其制定为优化问题。 您有离散变量，即您选择的矩形（是或否）和连续变量（三角形的位置和方向）。 现在，您可以设置两个独立的优化：挑选矩形的离散优化；以及一种连续的优化，一旦给出矩形，就会优化位置和方向。 交替这两个优化。 当然，困难在于优化的制定，并设计您的误差能量，使其不会陷入某些奇怪的配置中（局部最小值）。 我会尝试将连续优化作为最小二乘问题，以便我可以使用标准优化库。

5
我认为这个问题适合使用遗传算法和/或进化策略算法来解决。我曾经用某种进化策略算法解决过类似的装箱问题。请查看我的博客。
因此，如果您采用这种方法-将盒子编码成染色体：
  • x坐标
  • y坐标
  • 角度
然后尝试最小化以下适应函数-

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

选择权重w1，w2，w3以影响因素的重要性。当遗传算法找到部分解决方案时-移除仍然相互重叠或不符合形状的盒子-您将至少拥有合法（但不一定是最优）的解决方案。
祝您在这个有趣的问题中好运！
2
这确实是NP难问题，由于它具有高科技应用，因此合理的有效近似策略甚至都没有在专利上出现，更别说发表论文了。
您可以从限制问题开始，以适应您的预算。假设所有矩形都完全相同，假设所有二进制子分割的矩形也允许，因为您可以有效地预先包装它们以适应您的核心分割。为了得到额外的分数，您还可以形成几个固定的模式，将核心矩形粘合在一起，以涵盖几个比例差异显著的较大形状。假设您可以更改标准矩形/单元格的尺寸，只要其余部分（预包装和粘合模式）保持不变-这使您可以根据所给矩形来决定核心矩形的近似大小。
现在，您可以通过纵横比来逼近该有限系统可以保证的误差。对于前几次迭代，请假设它可以具有50％的误差，并采用简单的子分割模式，然后更改模式以减少误差，但不增加预包装的渐近复杂度。最终，您始终只是将给定的矩形分配给预先计算并现在固定的网格和二进制子分割-这意味着您根本不尝试进行布局或回溯-您始终对其第一个近似拟合到网格中感到满意。
努力定义与您的模式相匹配的矩形类别-这再次保持了整个过程的反转-您从未真正尝试适应您所给出的内容-您正在定义必须给出以使其很好地适应-然后将其余部分作为误差，因为它是近似值。
然后，您可以尝试做更多，但不能做太多-任何一点后退或钉住任意小的错误都会导致指数级增长。
如果您在研究机构工作，并且可以获得一些超级计算机时间-在那里运行一组详尽的搜索，以查看最佳包装可能的外观，并查看是否可以推导出更多的子分割模式和/或矩形集类别。
这应该足够进行前两年的研究 :-)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接