Add a square to a square polygon

Question

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

I want to do it in brute force when I start by adding two adjacent 1 * 1 squares to create a larger polygon using the join () function below and continuing in such a way as to grow the polygon. So the first argument of the union is the polygon, and the second argument is the adjacent 1 * 1 square that I want to add to the polygon. The return value is the boundary of the new polygon, current , associated with the new 1 * 1.

Here is what I have come 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 numbers representing the order in which its composite squares are added):

 234 1 5 6 

The printed output of the above code gives:

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

this is the minimum number of points needed to determine the boundary of a polygon.

But if I add another square to this form via a = join (a, area ((1,0))) and thereby create a hole, my algorithm breaks into pieces:

 234 1 5 76 

Here is another polygon that my algorithm cannot handle:

 123 64 5 

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

Thanks!

Answer 1

I think your algorithm is hard to fix. Note that, for example, adding one square to a polygon can create several holes:

  xxx xx xxx xxx xyx xxx xxx xx xxx 

Imagine, for example, that all x are the "current polygon" and you then id y ...

In the general case, a closed area is defined by a set of closed loops, and you can use only one list with only a much more complicated approach to creating bridges with zero area between the loops. A simple approach to what I think you're looking for is radically different:

• on each square and for each:
• if the square is inside and the square on the left is missing (or vice versa), then you know that you need a wall on the left.
• if the square is located and the square is higher (or vice versa), then you know that you need a wall above
• collect all the edges in the dictionary, where for each pair of coordinates you store a list of all walls starting or arriving at this edge.
• After the scan is completed, you can rebuild the loops that appear, starting from any wall and keeping the chain until you return to the starting point ... in the case when you reach the point, there are several options on which the walls to use to continue walking , then select any of them.

if you have correctly collected the data and assumed that you can add the border of one "outside" cell around your data, then it ensures that you get a list of zero or more closed loops as a result, because each point will list an even number of walls.

These loops (when considering the odd fill rule) will determine your starting area. Please note that you can get self-intersecting loops ... if you want to avoid that the algorithm is a bit more complicated.

This approach is also much faster than processing borders one at a time and performing all of these merge operations, and the result will be general (including unrelated regions and holes).

EDIT

The following image is the result of a complete implementation of this algorithm , including right-handed logic during loop collection, to avoid self-intersecting loops. Different colors were assigned to output the polygons, and the corners were cut to make the turns apparent.