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?
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.
Simply test if the rectangles are touching and then run convex hull on the union of their points.
Or you could also manually test to see which side of the rectangles are touching and add the point in the correct order to a polygon object.
These assume closed polygons will suffice (can't have holes in it).
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.
Convex hull won't work. Consider the three rectangles:
+---------------+
| |
| |
+-------+-------+
| |
| |
| |
+-------+-------+
| |
| |
+---------------+
The convex hull would be one big rectangle, not a U shape.
if your bounds are reasonable use a 2D array of edge counts, otherwise you'd have to use nested dictionaries.
because all widths and heights are the same you can uniquely identify an edge by a combination of x, y, and orientation(vertical or horizontal)
sample pseudocode: list_of_edges = new list arr_count = new int[][][]
fill_with_zeroes(arr_count )
foreach rect
foreach edge
arr_count [edge.x][edge.y][edge.orientation] += 1
foreach edge in arr_count
if count[edge] = 1
list_of_edges.add(edge]
of course, if you want to order the edges, then you'd have to pass through the array another time
foreach edge in arr_count
if count[edge] = 1
add_recursive(edge)
add_recursive(x,y):
for both horizontal and vertical orientations of edge starting at x, y:
count[edge] = 0
if (edge.orientation is horizontal)
return add_recursive( x+1, y)
else
return add_recursive( x, y+1 )
sorry, this pseudocode is pretty sloppy, but you should get the general idea
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
How about trying the following. I think this will work if designed properly.
Find the smallest emclosing rectangle, basically max-x, min-x and max-y and min-y. This will be our canvas for drawing. Initialise a 2D array of bits dx X dy where dx, dy are width of this outer rectangle, to all 0s.
Our objective is to find the contour, basically some corners of the rectangles so we can scale down this problem to a level where we can handle it computationally, once we have the points we can scale up to get the actual coordinates.
Scan through the above 2D array and mark a point 1 if it is contained in one of the given rectangle.
Now scan the 2D array and look for points whose neighbourhood has a 3:1 split, that means on 3 sides it has 1s and on one side 0s or vice versa. These points are those that will define the contour.
I think the complexity will be managiable if we can scale down the problem wisely.
