用给定的一组矩形填充任意 2D 形状
我有一组矩形和二维空间中的任意形状。形状不一定是多边形（可以是圆形），并且矩形具有不同的宽度和高度。任务是用尽可能接近的矩形来近似形状。我无法更改矩形尺寸，但允许旋转。
这听起来与包装问题和覆盖问题非常相似，但覆盖区域不是矩形......
我猜这是 NP 问题，我很确定应该有一些论文显示出很好的启发式方法来解决它，但我不知道要谷歌什么？我应该从哪里开始？
更新：我刚刚想到了一个想法，但我不确定它是否值得研究。如果我们将边界形状视为一个充满水的物理模具会怎样？每个矩形都被视为具有大小的带正电粒子。现在将最小的矩形放到它上面。然后在随机点按大小放置下一个。如果矩形太靠近，它们就会相互排斥。继续添加矩形，直到全部用完。这个方法能行得通吗？
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...
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为您可以寻找打包和自动布局生成算法。自动 VLSI 布局生成算法可能需要类似的东西，就像纺织品布局问题一样......
本文 Hegedüs：用矩形覆盖多边形的算法似乎解决了类似的问题。由于本文是 1982 年发表的，因此查看 引用此文章的论文。此外，这次会议似乎正在讨论与此相关的研究问题，因此可能是对此想法进行研究的关键字或名称的起点。
我不知道计算几何研究是否有针对您的特定问题的算法，或者这些算法是否足够容易/实用来实现。如果我必须在无法查找以前的工作的情况下这样做，我将采用以下方法。这只是一个方向，到目前为止还不是解决方案......
将其表述为优化问题。您有选择矩形的离散变量（是或否）和连续变量（三角形的位置和方向）。现在您可以设置两个独立的优化：一个选择矩形的离散优化；一个选择矩形的优化。以及一旦给出矩形就优化位置和方向的连续。交错这两个优化。当然，困难在于优化的制定，以及设计误差能量，使其不会陷入一些奇怪的配置（局部最小值）。我尝试将连续作为 最小二乘 问题，以便我可以使用标准优化图书馆。
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...
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.
我认为这个问题适合用遗传算法和/或进化策略算法来解决。我在某种进化策略算法的帮助下完成了类似的装箱问题。请查看我的博客。
因此，如果您将使用这种方法 - 编码到染色体框中：
然后尝试最小化这种适应度函数 -
选择权重 w1,w2,w3 等来影响因素的重要性。当遗传算法找到部分解决方案时（删除仍然重叠在一起或变形的框），您将至少获得合法（但不一定是最佳）解决方案。
祝你在这个有趣的问题上好运！
I think this problem is suitable for solving with genetic algorithm and/or evolutionary strategy algorithm. I've done similar box packing problem with the help of evolutionary strategy algorithm of some kind. Check this out in my blog.
So if you will use such approach - encode into chromosomes box:
Then try to minimize such fitness function-
Choose weights w1,w2,w3 such as to affect importance of factors. When genetic algorithm will find partial solution - remove boxes which still overlaps together or are out of shape - and you will have at least legal (but not necessary optimal) solution.
good luck in this interesting problem !
这确实是NP难，而且由于它具有高科技应用，合理有效的近似策略甚至在专利中都没有，更不用说发表论文了。
在有限的预算下，你能做的最好的事情就是从限制问题开始。假设所有矩形都完全相同，假设所有作为标准矩形的二进制细分的矩形也是允许的，因为您可以有效地预先打包它们以适合您的核心划分。为了获得额外的分数，您还可以形成几个固定模式来粘合核心矩形，以覆盖一些比例截然不同的较大形状。假设您可以更改标准矩形/单元格的尺寸，只要其余部分（预包装和粘合模式）保持不变 - 这为您提供了根据给定的矩形确定核心矩形的大致尺寸的参数。
现在，您可以使用宽高比来近似这种有限系统可以保证的误差。对于第一次迭代，假设使用简单的细分模式可以有 50% 的错误，然后更改模式以减少错误，但不会增加预打包的渐近复杂性。在一天结束时，您总是只是将给定的矩形分配给预先计算的、现在固定的网格和二进制细分 - 这意味着您根本不尝试进行布局或回溯 - 您总是对第一个近似值感到满意适合网格。
致力于定义与您的模式很好地融合的矩形类 - 这又是为了使整个过程颠倒 - 您永远不会尝试真正适合您所给出的内容 - 您正在定义必须给出的内容，以便很好地适应它 -然后你将其余的视为错误，因为它是近似值。
然后你可以尝试多做一点，但不能多做——任何回溯或修正任意小错误的行为都会呈指数级增长。
如果您在研究机构并且可以获得一些超级计算机时间 - 在那里运行一组包含病态混合的详尽搜索，只是为了看看最佳包装可能是什么样子，并看看您是否可以得出更多的细分模式和/或矩形集的类别。
这对于头两年或研究来说应该足够了:-)
It is NP hard indeed and since it has hi-tech application, reasonably efficients approximate strategies are not even in patents, let alone published papers.
The best you can do with a limited budget is to start by limiting the problem. Assume that all rectangles are exactly the same, Assume that all rectangles which are binary sub-divisions of your standard rectangle are also allowed since you can efficiently pre-pack them to fit your core division. For extra points you can also form several fixed schemas for gluing core rectangles to cover a few larger shapes with substantially different proportions. Assume that you can change dimensions of your standard rectangle/cell as long as the rest (pre-packing and gluing schema) remains the same - this gives you parameters to decide approximate size of the core rectangle based on rectangles you are given.
Now you can play with aspect ratios to approximate the error such limited system could guarantee. For the first iterations assume that it can have 50% error with a simple sub-division schema and then change schema to reduce the error but without increasing asymptotic complexity of pre-packing. At the end of the day you are always just assigning given rectangles to your pre-calculated and now fixed grid and binary sub-divisions - meaning you are not trying to do a layout or backtrack at all - you are always happy with the first approximate fit into the grid.
Work on defining classes of rectangles that pack well with your schema - that's again to keep the whole process inverted - you are never trying to actually fit what you are given - you are defining what you have to be given in order to fir it well - then you punt the rest as error since it is approximation.
Then you can try to do a bit more, but not much more - any slip into backtracking or nailing arbitrary small error and it's exponential.
If you are at a research facility and can get some supercomputer time - run a set of exhaustive searches with pathological mixes there just to see how optimal packing may look like and to see if you can derive a few more sub-division schemas and/or classes of rectangle sets.
That should be enough for the first 2 yrs or research :-)