Cur*_*usG 26 algorithm geometry computational-geometry
我在2D空间中有一组矩形和任意形状.形状不是多边形(可以是圆形),矩形具有不同的宽度和高度.任务是使用尽可能接近的矩形近似形状.我无法更改矩形尺寸,但允许旋转.
这听起来非常类似于包装问题和覆盖问题,但覆盖区域不是矩形...
我想这是NP的问题,而且我很确定应该有一些论文显示出很好的启发式来解决它,但我不知道该怎么去谷歌？我应该从哪里开始？
更新:我想到了一个想法,但我不确定它是否值得调查.如果我们将形状限定为充满水的物理模具,该怎么办？每个矩形被认为是带有尺寸的带正电粒子.现在删除最小的矩形.然后在随机点放下下一个大小.如果矩形太近,它们会相互排斥.继续添加矩形直到全部使用.这种方法有用吗？
bal*_*los 16
我认为你可以寻找包装和自动布局生成算法.自动VLSI布局生成算法可能需要类似的东西,就像纺织布局问题一样......
本文Hegedüs:用矩形覆盖多边形的算法似乎解决了类似的问题.由于这篇论文是从1982年开始的,所以看看引用这篇文章的论文可能会很有趣.此外,这次会议似乎正在讨论与此相关的研究问题,因此可能是研究这一想法的关键词或名字的起点.
我不知道计算几何研究是否具有针对您的特定问题的算法,或者这些算法是否容易/实用足以实现.如果我必须这样做而不能查找以前的工作,我将如何处理它.这只是一个方向,到目前为止还不是解决方案......
将其公式化为优化问题.您有离散变量,您选择哪个矩形(是或否)和连续变量(三角形的位置和方向).现在,您可以设置两个独立的优化:一个选择矩形的离散优化; 和一个连续的,一旦给出矩形就优化了位置和方向.交错这两个优化.当然,困难在于优化的制定,以及设计你的误差能量,使其不会陷入某些奇怪的配置(局部最小值).我试图将连续性作为最小二乘问题,以便我可以使用标准优化库.
我认为这个问题适合用遗传算法和/或进化策略算法求解.在某种进化策略算法的帮助下,我做了类似的盒子包装问题.在我的博客中查看.
所以,如果你将使用这种方法 - 编码到染色体框中:
然后尽量减少这种健身功能 -
y = w1*box_intersection_area + w2*box_area_out_of_shape + w3*average_circle_radius_in_free_space
选择权重w1,w2,w3以影响因素的重要性.当遗传算法找到部分解决方案时 - 删除仍然重叠或变形的盒子 - 你将至少拥有合法(但不是必要的最佳)解决方案.
祝这个有趣的问题好运!
| 归档时间： |
|
| 查看次数： |
9488 次 |
| 最近记录： |