2

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

我当前算法的伪代码：

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

这是一个扫描和修剪的链接。

这运作良好，但我想知道是否有方法可以减少矩形输出。我认为这比我现在所做的更复杂。

4

1 回答 1

5

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

R-树维基

这是 Sellis 等人的相关论文。人。描述 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的Graph-Theoretic Solutions to Computational Geometry Problems

或者通过Gareth Rees研究用于找到覆盖一组矩形而不重叠的最少矩形的算法

于 2013-07-21T15:12:08.027 回答