填写任意2D图形与给定的矩形 [英] 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问题，我pretty的肯定应该有一些论文，表现出良好的启发式方法来解决这个问题，但我不知道谷歌是什么？我应该从哪里开始？

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...

此文章<一个href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYR-481MNY5-TY&_user=10&_coverDate=09/30/1982&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1436124964&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=293df491c9871c775cb04a0de025d7f1">Hegedüs:算法覆盖面由矩形似乎来解决类似的问题。而且，由于本文主要是从1982年，这可能是有趣的，看看<一href="http://scholar.google.com/scholar?start=10&hl=en&as_sdt=2000&sciodt=2000&cites=11093890509873644341">papers其中举这一个。此外，本次会议似乎讨论与此相关的研究问题，所以可能是一个起点点谁做研究，这个想法的关键字或名称。

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.

我不知道，如果计算几何的研究具有算法为您的特定问题，或者如果这些算法很容易/实际落实不够。下面是我会怎么对待它，如果我不得不这样做，而不能仰视previous工作。这仅仅是一个方向，但至今没有一个解决方案...

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.

这篇关于填写任意2D图形与给定的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！