用给定的一组矩形填充任意二维形状 [英] Fill arbitrary 2D shape with given set of rectangles

问题描述

我在二维空间中有一组矩形和任意形状.形状不一定是多边形(可能是圆形)，矩形有不同的宽度和高度.任务是用尽可能接近的矩形来近似形状.我无法更改矩形尺寸，但允许旋转.

I have a set of rectangles and arbitrary shape in 2D space. The shape is not necessary a polygon (it may be a circle), and rectangles have different widths and heights. The task is to approximate the shape with rectangles as close as possible. I can't change rectangles dimensions, but rotation is permitted.

这听起来与包装问题和覆盖问题非常相似，但覆盖区域不是矩形...

It sounds very similar to packing problem and covering problem but covering area is not rectangular...

我猜这是 NP 问题，我很确定应该有一些论文展示了很好的启发式方法来解决它，但我不知道要谷歌什么?我应该从哪里开始?

I guess it's NP problem, and I'm pretty sure there should be some papers that show good heuristics to solve it, but I don't know what to google? Where should I start?

更新:我刚想到一个想法，但我不确定它是否值得研究.如果我们将边界形状视为充满水的物理模具会怎样.每个矩形被认为是一个带正电的粒子，具有大小.现在将最小的矩形放到它上面.然后在随机点按大小删除下一个.如果矩形太靠近，它们会相互排斥.继续添加矩形，直到全部用完.这种方法行得通吗?

Update: One idea just came into my mind but I'm not sure if it's worth investigating. What if we consider bounding shape as a physical mold filled with water. Each rectangle is considered as a positively charged particle with size. Now drop the smallest rectangle to it. Then drop the next by size at random point. If rectangles too close they repel each other. Keep adding rectangles until all are used. Could this method work?

推荐答案

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

I think you could look for packing and automatic layout generation algorithms. Automatic VLSI layout generation algorithms might need similar things, just like textile layout questions...

这篇论文Hegedüs: Algorithms for Covering polygons by rectangles 似乎来解决类似的问题.由于这篇论文是 1982 年的，所以看看 引用这个的论文.此外，本次会议似乎正在讨论与此相关的研究问题，因此可能是研究此想法的关键字或名称的起点.

This paper Hegedüs: Algorithms for covering polygons by rectangles seems to address a similar problem. And since this paper is from 1982, it might be interesting to look at the papers which cite this one. Additionally, this meeting seems to be discussing research problems related to this, so might be a starting point for keywords or names who do research in this idea.

我不知道计算几何研究是否有针对您的特定问题的算法，或者这些算法是否足够容易/实用以实施.如果我不得不这样做而无法查找以前的工作，这就是我将如何处理它.这只是一个方向，目前还不是解决方案……

I don't know if the computational geometry research has algorithms for your specific problem, or if these algorithms are easy/practical enough to implement. Here is how I would approach it if I had to do it without being able to look up previous work. This is just a direction, by far not a solution...

将其表述为优化问题.您有选择哪些矩形的离散变量(是或否)和连续变量(三角形的位置和方向).现在您可以设置两个独立的优化:选择矩形的离散优化；和一个连续的，一旦给出矩形，就可以优化位置和方向.交错这两个优化.当然，困难在于优化的制定，以及设计你的误差能量，使其不会陷入一些奇怪的配置(局部最小值).我会尝试将连续作为 最小二乘 问题，以便我可以使用标准优化图书馆.

Formulate it as an optimization problem. You have discrete variables of which rectangles you choose (yes or no) and continuous variables (location and orientation of the triangles). Now you can set up two independent optimizations: a discrete optimization which picks the rectangles; and a continuous that optimizes for the location and orientation once rectangles are given. Interleave these two optimizations. Of course the difficulty lies in the formulation of optimizations, and designing your error energy such that it does not get stuck in some strange configurations (local minima). I'd try to get the continuous as a least squares problem such that I can use standard optimizations libraries.

这篇关于用给定的一组矩形填充任意二维形状的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！