我在2D空间中有一组矩形和任意形状.形状不是多边形(可以是圆形),矩形具有不同的宽度和高度.任务是使用尽可能接近的矩形近似形状.我无法更改矩形尺寸,但允许旋转.
这听起来非常类似于包装问题和覆盖问题,但覆盖区域不是矩形...
我想这是NP的问题,而且我很确定应该有一些论文显示出很好的启发式来解决它,但我不知道该怎么去谷歌？我应该从哪里开始？
更新:我想到了一个想法,但我不确定它是否值得调查.如果我们将形状限定为充满水的物理模具,该怎么办？每个矩形被认为是带有尺寸的带正电粒子.现在删除最小的矩形.然后在随机点放下下一个大小.如果矩形太近,它们会相互排斥.继续添加矩形直到全部使用.这种方法有用吗？