将许多矩形组合成更少的矩形 [英] Combining many rectangles into fewer rectangles

问题描述

我当前算法的伪代码：

  do 
使用扫描和剪切水平压缩
使用扫描和剪切垂直压缩水平输出
 while比以前的输出）
  

这是一个 by David Eppstein

或调查通过 Gareth Rees 查找最少矩形以覆盖一组矩形的算法

I want to compress many non-overlapping rectangles into larger rectangles When they are adjacent.

Pseudo-code for my current algorithm:

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

Here's a link to sweep and prune.

This is working well, but I want to know if there are approaches which result in fewer rectangles output. I figure there's more sophisticated than what I'm doing now.

解决方案

So it sounds like your problem is that you have small gaps between the rectangles preventing them from being collected together into a single piece. If you have access to the source code for the sweep and prune method, you can add a buffer to the "overlap" test, but I think it would be more optimal to consider using an R-Tree. This will index the rectangular spaces without messing with limits on gaps etc.

R-Tree Wiki

Here is a relevant paper by Sellis et. al. describing the R+ tree:

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

here is a C# implementation of an R-Tree

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

[Edit - After Comment 1]

So let me see if I can capture the current problem.

• Rectangles are joined in passes of horizontal/vertical adjacency tests.
• Rectangles are only joined if the adjacent boundary for both is equal.
• The intermediate result of any join must also form a valid rectangle.
• The result is non-optimal because the sequence of joining.

I think you're actually looking for the minimum dissection into rectangles of a rectilinear polygon. The first step would be to join ALL the touching rectangles together, regardless of whether they form a rectangle or not. I think you are getting caught up in problems with the intermediate stages of each step in the process also needing to be complete rectangle deconstructions, leading to a sub-optimal result. If you merge them together into a single rectilinear polygon, you can use graph theory mechanisms.

You can check out Graph-Theoretic Solutions to Computational Geometry Problems by David Eppstein

Or investigate Algorithm for finding the fewest rectangles to cover a set of rectangles by Gareth Rees

这篇关于将许多矩形组合成更少的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！