将许多矩形合并成更少的矩形

Question

当相邻时，我想将许多不重叠的矩形压缩为较大的矩形。

我当前算法的伪代码：

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

这是清扫和修剪的链接。

这工作得很好，但是我想知道是否有方法导致更少的矩形输出。我认为这比我现在做的还要复杂。

Answer 1

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

R树维基

这是塞利斯等人的一篇相关论文。等 描述R +树：

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

这是R-Tree的C＃实现

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

[编辑-评论1之后]

因此，让我看看是否可以解决当前的问题。

• 矩形通过水平/垂直邻接测试通过。
• 仅当矩形和矩形的相邻边界相等时，才连接矩形。
• 任何连接的中间结果还必须形成一个有效的矩形。
• 由于加入的顺序，结果不是最佳的。

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

您可以查看David Eppstein的计算几何问题的图论解

或调查算法寻找矩形最少覆盖一组矩形不重叠的加雷思·雷斯