StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I don't know off the top of my head if there is already an algorithm for this, so I made one up:</p> <p>Find (xmin,ymin) (xmax,ymax) i.e. the minimum and maximum of the x and y coordinates of the existing squares. This defines a single bounding rectangle enclosing all of your squares.</p> <p>Find and connect with straight lines concave corners within the bounding rectangle.</p> <p>Answer to comments: ok, so if we connect all the concave perimeter corners along the grid lines, gradually removing (labeling) the peripheral rectangles, we get the following on the above difficult example:</p> <pre><code> A XBB CCCX XDD X EFFFG I J I J </code></pre> <p>which, as has rightly been pointed out, is sub-optimal. There are some decisions to be made in which order to pairwise connect the concavities when more than one way is possible. Choose the one resulting in the least number of new rectangles. (See F under the lowest X).</p> <p>When the splits are finished, we now add another stage of extending (merging) the existing rectangles. Crucially only such merging is to be allowed that does not reduce any of the existing rectangles. Changing the uppermost X to a B would be such a disallowed change because the Xs rectangle has been reduced. This condition guarantees that changes are only in the direction towards the minimum number of rectangles. Continuing with this procedure on the above example, we get:</p> <pre><code> X XBB CCCX XDD X FFFFF I J I J </code></pre> <p>Which happens to be optimal on this example but in general you may have to do a state-space search using these operations in order to find the global minimum.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload