<p>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.</p>

<p><a href="http://en.wikipedia.org/wiki/R-tree" rel="nofollow noreferrer">R-Tree Wiki</a></p>

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

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50ECCC47148D9121A4B39EC1220D9FB2?doi=10.1.1.45.3272&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50ECCC47148D9121A4B39EC1220D9FB2?doi=10.1.1.45.3272&amp;rep=rep1&amp;type=pdf</a></p>

<p>here is a C# implementation of an R-Tree</p>

<p><a href="http://sourceforge.net/projects/cspatialindexrt/" rel="nofollow noreferrer">http://sourceforge.net/projects/cspatialindexrt/</a></p>

<p>[Edit - After Comment 1]</p>

<p>So let me see if I can capture the current problem.</p>

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

<p>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.  </p>

<p><img src="https://i.stack.imgur.com/Ndi1I.png" alt="Minimum Dissection into Rectangles of a Rectilinear Polygon"></p>

<p>You can check out <a href="http://arxiv.org/pdf/0908.3916v1.pdf" rel="nofollow noreferrer">Graph-Theoretic Solutions
to Computational Geometry Problems</a> by <a href="http://www.ics.uci.edu/~eppstein/" rel="nofollow noreferrer">David Eppstein</a></p>

<p>Or investigate <a href="https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles">Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping</a> by <a href="https://stackoverflow.com/users/68063/gareth-rees">Gareth Rees</a></p>
Combining many rectangles into fewer rectangles
<p>I want to compress many non-overlapping rectangles into larger rectangles When they are adjacent.</p>

<p>Pseudo-code for my current algorithm:</p>

<pre><code>do
   compress horizontally using sweep and prune
   compress horizontal output vertically using sweep and prune
while (this output is small than previous output)
</code></pre>

<p>Here's a <a href="http://en.wikipedia.org/wiki/Sweep_and_prune" rel="nofollow">link to sweep and prune</a>.</p>

<p>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.</p>