合并和分割重叠的矩形以生成不重叠的矩形
我正在寻找如下算法：
给定一组可能重叠的矩形（所有这些矩形都“不旋转”，可以统一表示为（左，上，右，下）连音符等...），它返回占据相同区域的最小（非旋转）非重叠矩形集。
乍一看似乎很简单，但事实证明很棘手（至少要高效地完成）。
this/ideas/pointers 有一些已知的方法吗？
不一定是最小的，但启发式的小集合的方法也很有趣，产生任何有效输出集的方法也很有趣。
I am looking for an algorithm as follows:
Given a set of possibly overlapping rectangles (All of which are "not rotated", can be uniformly represented as (left,top,right,bottom) tuplets, etc...), it returns a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.
It seems simple enough at first glance, but prooves to be tricky (at least to be done efficiently).
Are there some known methods for this/ideas/pointers?
Methods for not necessarily minimal, but heuristicly small, sets, are interesting as well, so are methods that produce any valid output set at all.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为基于线扫描算法的东西会起作用：
y坐标就足够了）y坐标向输出集中添加一个新矩形设置为新矩形中尚未覆盖的部分。我不完全确定这涵盖了所有内容，但我认为通过一些调整它应该可以完成工作。或者至少给你一些想法......:)
Something based on a line-sweep algorithm would work, I think:
xcoordinates into an array, as "start-rectangle" and "end-rectangle" eventsy-coordinates will suffice)y-coordinates set to the part of the new rectangle that isn't already covered.I'm not completely sure this covers everything, but I think with some tweaking it should get the job done. Or at least give you some ideas... :)
因此，如果我尝试这样做，我要做的第一件事就是提出一个统一的网格空间。查找所有唯一的 x 和 y 坐标，并创建到索引空间的映射。因此，如果您有 x 值 { -1, 1.5, 3.1 }，则将它们映射到 { 0, 1, 2 }，对于 y 也是如此。然后每个矩形都可以用这些打包的整数坐标来精确表示。
然后我会分配一个位向量或覆盖整个网格的东西，并光栅化网格中的矩形。网格的好处是它非常易于使用，并且通过将其限制为唯一的 x 和 y 坐标，它既最小又精确。
提出相当快速的解决方案的一种方法是转储网格的每个“像素”。通过映射运行它们，然后就完成了。如果您正在寻找更优化数量的矩形，那么您就会遇到某种搜索问题。
让我们看一下 4 个相邻像素，一个 2x2 的小正方形。当我编写这样的算法时，我通常会考虑顶点、边和面。所以，这些是垂直周围的面。如果其中 3 个打开且 1 个关闭，则您将得到一个凹角。这是唯一的无效案例。例如，如果我没有任何凹角，我只需抓住范围并将整个东西转储为单个矩形。对于每个凹角，您需要决定是水平分割、垂直分割还是同时分割。我认为分割是在查找范围时标记边缘不要交叉。您也可以将其作为套装着色来进行，只要对您来说更容易即可。
凹角及其分割方向是您的搜索空间。您可以使用您想要的任何优化算法。分支/界限可能效果很好。我打赌您可以找到一种表现良好的简单启发式（例如，如果您正在考虑的凹角正对面有另一个凹角，则始终沿该方向分割。否则，沿较短的方向分割）。你可以贪婪一点。或者，您可以在两个方向上分割每个凹顶点，这通常会给您提供比将每个“像素”输出为矩形更少的矩形，并且非常简单。
读完这篇文章，我意识到可能有些地方不清楚。如果您想让我澄清任何事情，请告诉我。
So, if I were trying to do this, the first thing I'd do is come up with a unified grid space. Find all unique x and y coordinates, and create a mapping to an index space. So if you have x values { -1, 1.5, 3.1 } then map those to { 0, 1, 2 }, and likewise for y. Then every rectangle can be exactly represented with these packed integer coordinates.
Then I'd allocate a bitvector or something that covers the entire grid, and rasterize your rectangles in the grid. The nice thing about having a grid is that it's really easy to work with, and by limiting it to unique x and y coordinates it's minimal and exact.
One way to come up with a pretty quick solution is just dump every 'pixel' of your grid.. run them back through your mapping, and you're done. If you're looking for a more optimal number of rectangles, then you've got some sort of search problem on your hands.
Let's look at 4 neighboring pixels, a little 2x2 square. When I write algorithms like these, typically I think in terms of verts, edges, and faces. So, these are the faces around a vert. If 3 of them are on and 1 is off, then you've got a concave corner. This is the only invalid case. For example, if I don't have any concave corners, I just grab the extents and dump the whole thing as a single rectangle. For each concave corner, you need to decide whether to split horizontally, vertically, or both. I think of the splitting as marking edges not to cross when finding extents. You could also do it as coloring into sets, whatever is easier for you.
The concave corners and their split directions are your search space.. you can use whatever optimization algorithm you'd like. Branch/bound might work well. I bet you could find a simple heuristic that performs well (for example, if there's another concave corner directly across from the one you're considering, always split in that direction. Otherwise, split in the shorter direction). You could just go greedy. Or you could just split every concave vert in both directions, which would generally give you fewer rectangles than outputting every 'pixel' as a rect, and would be pretty simple.
Reading over this I realize that there may be areas that are unclear. Let me know if you want me to clarify anything.