Algorithm to merge adjacent rectangles into polygon

Question

I guess that my problem is related to "convex hull", but no the same. All shapes in the drawing are rectangles with same width and height. Many are adjacent to each other. I want to combine those adjacent rectangles into polygons. Unlike "convex hull", the resuled polygons could be "hollow" inside.

Is there any open source algorithm available?

Solution 1

I had to write an algorithm for merging adjacent polygons as part of an experiment project with HTML5 canvas (nothing glorious, a jigsaw puzzle :-) Holes in the resulting polygon are naturally supported. The Javascript routine is found in the function named Polygon.prototype.merge() in www dot raymondhill dot net / puzzle-rhill / jigsawpuzzle-rhill-3 dot js

The key is to remove segments which are duplicate, but of opposite direction. Rough explanation: A Point is {x:?,y:?}, a Segment is {ptA:?,ptB:?}, a Contour is {pts:[]} (a collection of connected Point objects), a Polygon is {contours:[]} (a collection of Contour objects.)

The merge algorithm collect all segments in a big fat pool of Segment objects, where duplicates are eliminated. First, all the segments of all the contours defining Polygon A are added to the pool. Then, all the segments of all contours defining Polygon B are added to the pool, but we test and remove for duplicate (easily done using a Point object as a hashkey).

Then we take a segment from the pool (randomly is fine), and we "walk" it until we reach a "dead end", that is, no more segment can be connected. This form one Contour object. We repeat until the whole collection of segments has been used. As segments are used, they are removed from the pool. "Walk" a segment means we take its end point, and we look up a segment which start point matches it.

As said, as a result we have a collection of Contour objects which define the Polygon. Some contours will be filled, some might be hollow. To determine whether a Contour is filled or hollow is just a matter of testing whether the Contour is clockwise or counterclockwise, or whether its area is positive or negative. It's a convention, in my case clockwise contours are filled, counterclockwise are hollow.

Here is my implementation, minus the specifics and minus error handling. Hopefully I copied/pasted enough for you to make it work right away, else refer to my JS file above for context:

// Point object
function Point(a,b) {
    // a=x,b=y
    if (b) {
        this.x=a;
        this.y=b;
        }
    // a=Point or {x:?,y:?}
    else if (a) {
        this.x=a.x;
        this.y=a.y;
        }
    // empty
    else {
        this.x=this.y=0;
        }
    }
Point.prototype.toHashkey = function() {
    return this.x+"_"+this.y;
    };
Point.prototype.clone = function() {
    return new Point(this);
    };
// Segment object
function Segment(a,b) {
    this.ptA = new Point(a);
    this.ptB = new Point(b);
    }
// Contour object
function Contour(a) {
    this.pts = []; // no points
    if (a) {
        if (a instanceof Array) { // assume array of Point objects
            var nPts = a.length;
            for (var iPt=0; iPt<nPts; iPt++) {
                this.pts.push(a[iPt].clone());
                }
            }
        }
    }
Contour.prototype.clone = function() {
    return new Contour(this);
    };
Contour.prototype.addPoint = function(p) {
    this.pts.push(p);
    };
// Polygon object
function Polygon(a) {
    this.contours = []; // no contour
    if (a) {
        if (a instanceof Polygon) {
            var contours = a.contours;
            var nContours = contours.length;
            for ( var iContour=0; iContour<nContours; iContour++ ) {
                this.contours.push(new Contour(contours[iContour]));
                }
             }
        else if ( a instanceof Array ) {
            this.contours.push(new Contour(a));
            }
        }
    }
Polygon.prototype.merge = function(other) {
    // A Javascript object can be used as an associative array, but
    // they are not real associative array, as there is no way
    // to query the number of entries in the object. For this
    // reason, we maintain an element counter ourself.
    var segments={};
    var contours=this.contours;
    var nContours=contours.length;
    var pts; var nPts;
    var iPtA; var iPtB;
    var idA; var idB;
    for (var iContour=0; iContour<nContours; iContour++) {
        pts = contours[iContour].pts;
        nPts = pts.length;
        iPtA = nPts-1;
        for ( iPtB=0; iPtB<nPts; iPtA=iPtB++ ) {
            idA = pts[iPtA].toHashkey();
            idB = pts[iPtB].toHashkey();
            if (!segments[idA]) {
                segments[idA]={n:0,pts:{}};
                }
            segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
            segments[idA].n++;
            }
        }
    // enumerate segments in other's contours, eliminate duplicate
    contours = other.contours;
    nContours = contours.length;
    for ( iContour=0; iContour<nContours; iContour++ ) {
        pts = contours[iContour].pts;
        nPts = pts.length;
        iPtA=nPts-1;
        for (iPtB=0; iPtB<nPts; iPtA=iPtB++) {
            idA = pts[iPtA].toHashkey();
            idB = pts[iPtB].toHashkey();
            // duplicate (we eliminate same segment in reverse direction)
            if (segments[idB] && segments[idB].pts[idA]) {
                delete segments[idB].pts[idA];
                if (!--segments[idB].n) {
                    delete segments[idB];
                    }
                }
            // not a duplicate
            else {
                if (!segments[idA]) {
                    segments[idA]={n:0,pts:{}};
                    }
                segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
                segments[idA].n++;
                }
            }
        }
    // recreate and store new contours by jumping from one point to the next,
    // using the second point of the segment as hash key for next segment
    this.contours=[]; // regenerate new contours
    var contour;
    for (idA in segments) { // we need this to get a starting point for a new contour
        contour = new Contour();
        this.contours.push(contour);
        for (idB in segments[idA].pts) {break;}
        segment = segments[idA].pts[idB];
        while (segment) {
            contour.addPoint(new Point(segment.ptA));
            // remove from collection since it has now been used
            delete segments[idA].pts[idB];
            if (!--segments[idA].n) {
                delete segments[idA];
                }
            idA = segment.ptB.toHashkey();
            if (segments[idA]) {
                for (idB in segments[idA].pts) {break;} // any end point will do
                segment = segments[idA].pts[idB];
                }
            else {
                segment = null;
                }
            }
        }
    };

When we "walk" the segment to create a contour, there is a case where a segment can connect to more than one segment:

+------+-------+
|   Poly A     | two segments sharing same start point Z
|              | 
+      +---<---Z---->---+
|      |       | Poly B |
|      |       |        |
+      +-------+--------+
|                       |
|                       |
+------+-------+--------+

Which can lead to two valid results (the algorithm above will lead randomly to one or the other):

Result 1, one filled contour:

+------+--->---+
|   Poly A     |
|              | 
+      +---<---+---->---+
|      |       |        |
|      |       |        |
+      +--->---+        +
|                       |
|                       |
+------+---<---+--------+

Result 2, one filled contour, one hollow contour:

+------+--->---+
|   Poly A     |
|              | 
+      +---<---+---->---+
|      | Hole A|        |
|      |       |        |
+      +--->---+        +
|                       |
|                       |
+------+---<---+--------+

This shouldn't be a problem though, as your code should already be ready to handle holes.

Other important detail: The algorithm above doesn't get rid of intermediate points ('+'), in fact they are expected or else the algorithm won't work, as in the following case:

+------>-------+
|   Poly A     |
|              | 
|              | +---->---+
|              | | Poly B |
|              | |        |
|              | +----<---+
|              |
|              |
+------<-------+

My understanding is that this is what you have. I imagine the algorithm could be extended to support such case by finding and adding the intersecting points beforehand (it was unnecessary in my case):

+------>-------+
|   Poly A     |
|              | 
|              + +---->---+
|              | | Poly B |
|              | |        |
|              + +----<---+
|              |
|              |
+------<-------+

Hope this help.

P.S.: You can 'test' the algorithm with the jigsaw puzzle, by snapping pieces together to generate holes, etc.: http://www.raymondhill.net/puzzle-rhill/puzzle-rhill.php?puzzlePieces=16&puzzleComplexity=1&puzzleURL=http://www.public-domain-photos.com/free-stock-photos-4/travel/los-angeles/los-angeles-skyline.jpg&puzzleRotate=0&puzzleVersion=3

Solution 2

I would look into something like General Polygon Clipper. You're basically doing union (OR) polygon operations. The fact that they're all rectangles just makes the math a bit easier, but it could easily be done with something like GPC.

There are language wrappers for lots of languages there, too.

Solution 3

If you're using a spatial processing library (like JTS [java], NTS [.net] or GEOS [c++], which are all open source and usable for commercial apps, unlike GPC) you can just Union the rectangles.

The general purpose way to do this is to build a graph of the edges of the inputs (rectangles), perform intersections, label the edges as on the inside or outside of the result, and just keep the outer edges. I don't know of a specific algorithm to treat rectangles, but it would likely be simiar, except, as noted, the math would be simpler.

Comments

[mbeckish]

The perimeter of any blob of adjacent rectangles makes a polygon. Is your question "How do I list the line segments that define the perimeter of a set of connected rectangles?" or something else?

[David Grayson]

When you say "many are adjacent to eachother", what does that mean? Do they just touch at the edges, or can rectangles overlap? Are the rectangles on a grid of some sort, or can their vertices be anywhere?

[Reed Copsey]

That won't work if he want to preserve holes. Imagine having a 3x3 block of rectangles, but the center rectangle missing - convex hull will fill it in.

[Laurent Jégou]

Thanks for this answer, i was able to use the algo in a cartographic contexte with the OpenLayers lib.