Given the following polygon, which is divided into sub-polygons as depicted below [left], I would like to create `n` number of contiguous, equally sized groups of sub-polygons [right, where `n=6`]. There is no regular pattern to the sub-polygons, though they are guaranteed to be contiguous and without holes.

[![](https://i.stack.imgur.com/24X4e.png)](https://i.stack.imgur.com/24X4e.png)

This is *not* splitting a polygon into equal shapes, it is grouping its sub-polygons into equal, contiguous groups. The initial polygon may not have a number of sub-polygons divisible by `n`, and in these cases non-equally sized groups are ok. The only data I have is `n`, the number of groups to create, and the coordinates of the sub-polygons and their outer shell (generated through a clipping library).

My current algorithm is as follows:

```
list sub_polygons[] # list of polygon objects

for i in range(n - 1):
    # start a new grouping
    pick random sub_polygon from list as a starting point
    remove this sub_polygon from the list
    add this sub_polygon to the current group

    while (number of shapes in group < number needed to be added):
        add a sub_polygon that the group borders to the group
        remove this sub-polygon from the sub-polygons list

add all remaining sub-shapes to the final group

```

This runs into problems with contiguity, however. The below illustrates the problem - if the red polygon is added to the blue group, it cuts off the green polygon such that it cannot be added to anything else to create a contiguous group. 

[![](https://i.stack.imgur.com/uuhlH.png)](https://i.stack.imgur.com/uuhlH.png)

It's simple to add a check for this when adding a sub-polygon to a group, such as 

```
if removing sub-polygon from list will create non-contiguous union
   pass;

```

but this runs into edge conditions where every possible shape that can be added creates a non-contiguous union of the available sub-polygons. In the below, my current algorithm is trying to add a sub-polygon to the red group, and with the check for contiguity is unable to add any:

[![](https://i.stack.imgur.com/kl49x.png)](https://i.stack.imgur.com/kl49x.png)

Is there a better algorithm for grouping the sub-polygons?