Add square to polygon composed of squares

Question

I have a collection of 1*1 polygons, each of which is defined by its boundary (a set of four points) and I use the function area() below in my code example to create these. I wish to combine such adjacent squares into a single polygon, with this polygon also defined in terms of its boundary points.

I wish to do this in a brute force fashion where I begin by adding two adjacent 1*1 squares to create a larger polygon using the function join() below and continue in this fashion in order to grow the polygon. So the first argument of join is the polygon so far and the second argument is an adjecent 1*1 square which I wish to add to the polygon. The return value is the boundary of the new polygon, current joined with the new 1*1.

Here's what I've come with so far:

def join(current, new):
    """ current is the polygon, new the 1*1 square being added to it"""
    return get_non_touching_part_of_boundary(current, new)  + get_non_touching_part_of_boundary(new, current)

def get_non_touching_part_of_boundary(this, other):
    for i,point in enumerate(this):
        if point not in other and this[i-1] in other:
            break # start of non touching boundary from a clockwise perspective
    non_touching_part_of_boundary = []
    for point in this[i:] + this[:i]:
        if not point in other:
            non_touching_part_of_boundary.append(point)
    return non_touching_part_of_boundary    

def area(point):
    """ boundary defined in a clockwise fashion """
    return [point,(point[0],point[1]+1),(point[0]+1,point[1]+1),(point[0]+1,point[1])]

a = area((0,1))            # a assigned a 1*1 polygon
a = join(a, area((0,2)))   # a assigned a 2*1 polygon
a = join(a, area((1,2)))    
a = join(a, area((2,2)))    
a = join(a, area((2,1)))    
a = join(a, area((2,0)))    

print(a)

This gives me the following polygon shape (with the numbers representing the order in which which its composing squares are added):

234
1 5
  6

The printed output of the code above gives:

[(2, 2), (1, 2), (1, 1), (0, 1), (0, 3), (3, 3), (3, 0), (2, 0)]

this is the minimum number of points required to defined the boundary of the polygon.

But if I add one more square to this shape via a = join(a, area((1,0))) and thereby creating a hole, my algorithm falls to pieces:

234
1 5
 76

Here's another polygon that my algorithm can't handle:

123
 64
  5

Can anyone help me? I'd like the holes in the polygon to be listed in a separate list.

Thank!

It is hard to understand from your description what is the input and what is the desired output. Please, clarify. — Roman Susi

6502 6502 · Accepted Answer · 2012-01-20T20:58:25

I think that your algorithm is hard to fix. Consider that for example adding a single square to a polygon could create several holes:

  xxx
  x x
xxx xxx
x  y  x
xxx xxx
  x x
  xxx

imagine for example that all the x are the "current polygon" and you then andd y...

In general a closed area is defined by a collection of closed loops and you can use just a single list only with a much more complex approach of creating zero-area bridges between the loops. A simple approach to what seems to me you are looking for is radically different:

loop on every square and for each one:
if the square is in and the square to the left is out (or vice versa) then you know you need a wall on the left
if the square is in and the square above is out (or vice versa) then you know that you need a wall above
collect all the edges in a dictionary where for every coordinate pair you keep a list of all walls starting or arriving at that edge
once the scan is finished you can rebuild the resulting loops by starting with any wall and keeping following the chain until you get back to the initial point... in case that when you arrive at a point there are multiple choiches about which wall to use for continue the walk then pick any of them.

if you collected the data properly and assuming you can add a border of one "out" cell around your data then it's guaranteed that you will get as result a list of zero or more closed loops because each point will list an even number of walls.

Those loops (when considering an odd-even filling rule) will be defining your initial area. Note that you may get self-intersecting loops... if you want to avoid that the algorithm is slightly more complex.

This approach is also much faster than processing boundaries one at a time and doing all those merge operations and the result will be general (including non-connected areas and holes).

EDIT

The following image is the result of a complete implementation of this algorithm including a right-turn logic during cycle collection to avoid self-intersecting cycles. Different colors have been assigned to output polygons and corners have been cut to make the turns evident.

output of the cycle collection algorithm

Add square to polygon composed of squares

1 Answers

EDIT