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?
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
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.