2
$\begingroup$

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

Initial Problem enter image description here

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work.

Final Structure

Possible steps Possible steps

Example of a Real World problem Real Word problem

$\endgroup$
  • $\begingroup$ The dual graph representation doesn't seem to encode enough information. Consider your optimal solution for the first example, and think about it being some sub-part of a larger figure. In that case, none of the edges of the graph actually encode allowable contractions because the rectangles aren't connected along entire edges. $\endgroup$ – John Dec 13 '18 at 21:13
  • $\begingroup$ Branch and bound might be the easiest way to go here. It's exam week, so I'm not completely thinking straight, but I don't see either an obvious dynamic programming solution, nor an obvious NP-completeness proof here. $\endgroup$ – John Dec 13 '18 at 21:23
1
$\begingroup$

Here's a naive attempt at a greedy solution.

I'm assuming the initial input is a polyomino (polygon made up of grid aligned squares) on a grid as in your "real world example".

Let $b = (i, j, w, h)$ be the rectangle with lower left corner containing grid location $(i, j)$ with width $w$ and height $h$. A rectangle is valid if and only if all of its internal grid cells are part of the polyomino.

For a valid rectangel $r$, the boundary edges of $r$ will either also be boundary edges of the polyomino itself, or internal edges. Denote by $B_r$ the number of boundary edges of the rectangle that are internal to the polyomino and $I_r$ the number of grid edges that are internal to both the boundary and the rectangle. In the teal rectangle in my example below, $I_r = 17$ and $B_r = 6$ (the red sketchy edges). Now define the quality of the rectangle $r$ to be $Q_r = I_r - B_r$.

The thought here is that the quality of a rectangle measures how good it is at eliminating internal edges.

Now, the greedy solution I have in mind is:

Generate all of the $O(n^4)$ possible rectangles $r$. For each rectangle $r$, check if $r$ is valid. * If $r$ is valid, compute its quality score and maintain the rectangle with the maximum quality. End for loop. Add the rectangle that maximized the quality to the output set, and color the squares it covers white. Repeat until all squares are white.

Unfortunately this is $O(n^5)$ where $n$ is the width and height of the grid. But if your problem size really is like the image, then that may not be an issue.

Also, I don't have a proof that it's optimal, but I'll think about it.

enter image description here

Ok, I wrote some code for this. It's quick and dirty, but it returns exactly your optimal result on your original small example. It is quick and dirty, so don't judge ;).

from functools import reduce

# Generates all valid rectangles that have a lower left hand corner in i and j
def validRectanglesFrom(grid, i, j):
    result = []
    w = 1
    while i + w <= len(grid) and grid[i + w - 1][j] == 1:
        h = 1
        row_is_valid = True
        while j + h <= len(grid[i + w - 1]) and row_is_valid:
            for k in range(i, i + w):
                if grid[k][j + h - 1] == 0: 
                    row_is_valid = False
                    break
            if row_is_valid: 
                result.append((i, j, w, h))
            h = h + 1
        w = w + 1
    return result

def left_edge_is_internal(grid, i, j):
    return i > 0 and grid[i - 1][j] == 1 and grid[i][j] == 1

def right_edge_is_internal(grid, i, j):
    return i < len(grid) - 1 and grid[i][j] == 1 and grid[i + 1][j] == 1

def bottom_edge_is_internal(grid, i, j):
    return j > 0 and grid[i][j - 1] == 1 and grid[i][j] == 1

def top_edge_is_internal(grid, i, j):
    return j < len(grid[i]) - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1

def bottom_boundary_penalty(grid, rect): 
    return len(
        list(
            filter(
                lambda isInt: isInt, 
                map(
                    lambda i: bottom_edge_is_internal(grid, i, rect[1]), 
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def top_boundary_penalty(grid, rect): 
    return len(
        list(
            filter(
                lambda isInt: isInt, 
                map(
                    lambda i: top_edge_is_internal(grid, i, rect[1] + rect[3] - 1), 
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def left_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt, 
                map(
                    lambda j: left_edge_is_internal(grid, rect[0], j), 
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def right_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt, 
                map(
                    lambda j: right_edge_is_internal(grid, rect[0] + rect[2] - 1, j), 
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def boundary_penalty(grid, rect):
    return (
        bottom_boundary_penalty(grid, rect) + 
        top_boundary_penalty(grid, rect) +
        left_boundary_penalty(grid, rect) + 
        right_boundary_penalty(grid, rect)
    )

def internal_grid_edges(rect):
    return ((rect[2] - 1) * rect[3]) + (rect[2] * (rect[3] - 1))

def quality(grid, rect):
    return internal_grid_edges(rect) - boundary_penalty(grid, rect)


def get_rectangles(grid):
    result = []
    grid_locations = [(i, j) for i in range(0, len(grid)) for j in range(0, len(grid[i]))]
    unfilled = {cell for cell in grid_locations if grid[cell[0]][cell[1]] == 1}
    while len(unfilled) > 0:
        rects = [rect for cell in unfilled for rect in validRectanglesFrom(grid, cell[0], cell[1])]
        qualityScores = list(map(lambda rect: quality(grid, rect), rects))
        bestRectIdx = reduce(lambda i, j: i if qualityScores[i] > qualityScores[j] else j, range(len(qualityScores)))
        bestRect = rects[bestRectIdx]
        result.append(bestRect)
        for i in range(bestRect[0], bestRect[0] + bestRect[2]):
            for j in range(bestRect[1], bestRect[1] + bestRect[3]):
                unfilled.remove((i,j))
                grid[i][j] = 0
    return result

# Your initial example
grid = [[1, 1, 1], [0, 1, 0], [0, 1, 1], [0, 1, 0]] 
get_rectangles(grid)

# Your "real world" example
grid2 = [[0,0,0,0,0,0,0,0,1,1,1,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,1,1,1,0,0],
        [0,0,0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,0,0,0,0,0,0,0,1,0,1,1,0,0],
        [1,1,0,0,0,0,0,0,0,0,0,1,1,1,0],
        [1,1,1,1,0,0,0,0,1,0,0,1,0,1,0],
        [0,0,0,1,1,0,0,1,1,1,1,1,0,1,0],
        [1,1,1,1,1,0,1,1,1,1,1,1,0,0,0],
        [1,1,1,0,1,0,1,1,1,1,1,0,0,0,0],
        [0,0,1,1,1,1,1,0,0,1,1,1,0,0,0],
        [0,0,0,1,0,0,0,0,0,0,1,0,0,0,0],
        [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,1,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,0,0,0,0,0,0,0,0,0],
        [0,1,0,1,1,1,1,1,0,0,0,0,0,0,0]]
get_rectangles(grid2)

Here's the result my code returns for your "real world" example.

enter image description here

$\endgroup$
  • $\begingroup$ From where do the n^4 comes, Basically I need to start from each rectangle and see the largest valid rectangle that can be created? $\endgroup$ – jozamm Dec 14 '18 at 5:57
  • $\begingroup$ I think you almost certainly need to check all possible rectangles, not just the largest (in fact, what does "largest" mean here? By area? By Dimensions? I'm not sure either are completely relevant since what we care about is how many border edges are internal to the polyomino, not the size). For example, in my figure above, you'd also need to check the rectangle that has the same lower left-hand corner but is only two cells wide and 5 cells high. $\endgroup$ – John Dec 14 '18 at 13:58
  • $\begingroup$ My analysis is pretty coarse-grained. Intsead of naively generating all n^4 rectangles, you could imagine growing rectangles from a lower left-hand corner and generating all valid rectangles without generating any invalid ones. Then if $w$ and $h$ are the maximum width and height of any given rectangle and $m$ is the number cells in your polyomino, your only looking at $O(mwh)$ iterations, which sounds a lot better. And there's almost certainly some more clever algorithm you could use to find the largest rectangle that can be grown from each square. $\endgroup$ – John Dec 14 '18 at 14:03
  • $\begingroup$ I now have a counter example to the largest area triangle being the best first choice, by the way: make a column 1 cell wide and 100 units high. Then, to the bottom two cells of the column add a 1 x 2 column off the side (making a sort of L shape) so that the bottom has a 2x2 square. The optimal is to cut that 2x2 square off as one rectangle and the remaining 1x98 column as a second rectangle leading to a score of 1. However, initially, the largest area rectangle I can make is the 1x100 initial column, but cutting this way gives me a sub-optimal score of 2. $\endgroup$ – John Dec 14 '18 at 16:41
  • $\begingroup$ By the way, this is definitely not optimal. $\endgroup$ – John Dec 15 '18 at 19:05
1
$\begingroup$

I coded a possible solution to the problem.

Given that the structure is quite large e.g. a grid of 25x25 and around the periphery of the structure other rectangles are added, it is very difficult to determine the optimal solutions. The structure may also contain holes which makes it NP complete.

Initially I used to the internal borders metric i.e. maximize the number of internal borders removed but the results I got were not very satisfactory. The next greedy technique I tried was to maximize the area removed at each step and this is giving good results as far as I can see. Good results re the improvement in computational efficiency for the next steps. The only I can see the overall effect of the metric is to do a statistical test. I will generate a couple of 1000 structure, apply both the internal perimeter and area matrics and see the improvement in the results.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.