c# - 将许多矩形组合成更少的矩形

Question

我想将许多不重叠的矩形压缩成更大的矩形，当它们相邻时。

我当前算法的伪代码:

do
   compress horizontally using sweep and prune
   compress horizontal output vertically using sweep and prune
while (this output is small than previous output)

这是一个 link to sweep and prune .

这很好用，但我想知道是否有方法可以减少矩形输出。我想这比我现在做的更复杂。

Answer 1

所以听起来您的问题是矩形之间的间隙很小，无法将它们收集在一起成为一个整体。如果您可以访问扫描和修剪方法的源代码，则可以为“重叠”测试添加一个缓冲区，但我认为考虑使用 R-Tree 会更好。这将索引矩形空间而不会弄乱间隙限制等。

R-Tree Wiki

这是 Sellis 等人的一篇相关论文。阿尔。描述 R+ 树:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50ECCC47148D9121A4B39EC1220D9FB2?doi=10.1.1.45.3272&rep=rep1&type=pdf

这是 R 树的 C# 实现

http://sourceforge.net/projects/cspatialindexrt/

[编辑 - 在评论 1 之后]

那么让我看看我是否能捕捉到当前的问题。

• 在水平/垂直邻接测试的过程中连接矩形。
• 只有当两个矩形的相邻边界相等时才连接矩形。
• 任何连接的中间结果也必须形成一个有效的矩形。
• 结果不是最优的，因为加入的顺序。

我认为您实际上是在寻找对直线多边形矩形的最小剖分。第一步是将所有接触的矩形连接在一起，无论它们是否形成矩形。我认为您陷入了过程中每个步骤的中间阶段的问题，也需要进行完整的矩形解构，从而导致次优结果。如果将它们合并成一个直线多边形，则可以使用图论机制。

可以查看Graph-Theoretic Solutionsto Computational Geometry Problems通过 David Eppstein

或调查Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping通过 Gareth Rees