java - merge adiacent rectangles into a polygon

Question

I have a set of rectangles that have the same width and height and are always adiacent. I know the position of all the vertices, each one having only 4. (because is a square).

This image can explain this:

If there are any gaps, is ok if the algorithm will 'fill' the gap.

I searched a lot, and could not find anything good.. I need an simple algorithm, it doesn't have to be that efficient.. Let's say that we got 7 rectangles like in the second polygon example from the image. Is ok if I first merge 1 with 2, then merge our new polygon with 3, and so on, it doesn't have to be that fast, because there will be maximum 50 rectangles.

Answer 1

Because your shape consists of rectangles only and they are always adjacent, the algorithm of merging is much simpler than it would be without those assumptions.

• Create a list of ALL edges from your rectangles. One rectangle has 4 edges.
• Let the Edge be a class with properly defined compareTo() and equals().
• Sort the edges list (uses compareTo).
• Iterate through the list. If the same edge is present in the list TWICE, remove them both from the list.
• The remaining edges are the edges of your polygon.

Answer 2

I really l like the efficiency of Dariusz's answer. And it might be that it meets all your requirements, in which case go with it.

However, there are a few problems that come to mind.

What if there are multiple shapes after merging? How can you detect if these shapes are separate, or nested? For that matter, if you are simply given a set of edges, it is not easy to tell if it constitutes a shape, or the void left inside a shape.

For example, consider the following diagram after merging adjacent squares:

##################
##################
##################
###            ###
###  ########  ###
###  ########  ###
###  ########  ###
###  ########  ###
###            ###
##################
##################
##################

Here there are really 2 shapes - 1 inside another. However, there are 3 sets of connected edges. In order to see if the inner rectangle is a shape or a void within a shape, you must start at the outer rectangle and work inwards. Doing so will result in knowing that the shape is basically an outline of a rectangle surrounding another rectangle. If you were to remove the outer edges, however, the resulting shape would simply be a hollow rectangle - one shape.

Assuming this is relevant to your problem (it might not be), then the following algorithm may be more suitable:

Instead of throwing the set of all the edges of all the rectangles together at the beginning, keep each rectangle separate in a list of Polygons. Each Polygon has its own set of edges.

Merge Polygons in this list that share an edge until you are left with a set of distinct Polygons (i.e. no more merges can take place).

List<Polygon> plist;

// Populate the list with the polygons...

for (int i = 0; i < plist.size(); i++) {
  Polygon p1 = plist.get(i);
  boolean distinct = false;
  while (!distinct) {
    distinct = true;
    for (int j = plist.size() - 1; j > i; j--) {
        Polygon p2 = plist.get(j);
        if (p1.sharesEdge(p2)) {
          // Merge the two polygons
          p1.merge(p2);
          // One less shape
          plist.remove(j);
          distinct = false;
        } // if (p1.sharesEdge(p2))
      } // for (int j=plist.size()-1 ; j>i; j--) 
    } // while (!distinct)
} // for (int i=0; i<plist.size(); i++)

At the end, you will have a list of separate Polygons in plist.

sharesEdge simply loops over the edges of each Polygon and sees if they have any in common.

merge does exactly as Dariusz's answer - remove pairs of edges.

Some assumptions - all initial polygons have edges of unit length. If this is not true, then you may need to split edges up when merging and have a more complicated method of checking for shared edges.

If nested shapes need to be handled by absorbing them into the larger shape (i.e. filling the gaps), then it gets a little tricky. You'd start by creating a path of the edges. If the edges are all connected, then this is a simple shape where its edges define the perimeter. If not, then there should be one outer perimeter, and one or more inner perimeters. Ignore the inner perimeters and resolve the shape to to simple - i.e. only the edges in the outer perimeter are kept. Then, loop over the shapes and see if any of the shapes is inside the other. If so, remove it.