Group divided polygon into N contiguous shapes

user_10855478 0
Viewed 329

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.

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.

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:

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

polygon geometry algorithm
2 Answers

I think it's more complicated to be solved in a single run. Despite the criteria used for selecting next polygon, it may stock somewhere in the middle. So, you need an algorithm that goes back and changes previous decision in such cases. The classic algorithm that does so is BackTracking.

But before starting, let's change the representation of the problem. These polygons form a graph like this:

enter image description here

This is the pseudocode of the algorithm:

function [ selected, stop ] = BackTrack(G, G2, selected, lastGroupLen, groupSize)
    if (length(selected) == length(G.Node))
        stop = true;
        return;
    end
    stop = false;
    if (lastGroupLen==groupSize)
        // start a new group
        lastGroupLen=0;
    end;
    // check continuity of remaining part of graph
    if (discomp(G2) > length(selected))
        return;
    end

    if (lastGroupLen==0)
        available = G.Nodes-selected;
    else
        available = []
        // find all nodes connected to current group
        for each node in last lastGroupLen selected nodes
            available = union(available, neighbors(G, node));
        end
        available = available-selected;
    end
    if (length(available)==0)
        return;
    end
    lastSelected = selected;
    for each node in available
        [selected, stop] =  BackTrack(G, removeEdgesTo(G2, node), 
            Union(lastSelected, node), lastGroupLen+1, groupSize);
        if (stop)
            break;
        end
    end
end

where:
selected: an ordered set of nodes that can be divided to n consecutive groups
stop: becomes true when the solution was found
G: the initial graph
G2: what remains of the graph after removing all edges to last selected node
lastGroupLen: number of nodes selected for last group
groupSize: maximum allowable size of each group
discomp(): returns number of discontinuous components of the graph
removeEdgesTo(): removes all edges connected to a node

That should be called like:

[ selected, stop ] = BackTrack( G, G, [], 0, groupSize);

I hope that is clear enough. It goes like this:

enter image description here

Just keep in mind the performance of this algorithm can be severely affected by order of nodes. One solution to speed it up is to order polygons by their centroids:

enter image description here

But there is another solution, if you are not satisfied with this outcome like myself. You can order the available set of nodes by their degrees in G2, so in each step, nodes that have less chance to make the graph disconnected will be visited first:

enter image description here

And as a more complicated problem, i tested map of Iran that has 262 counties. I set the groupSize to 20:

enter image description here

user_20930770

I think you can just follow the procedure:

  1. Take some contiguous group of sub-polygons lying on the perimeter of the current polygon (if the number of polygons on the perimeter is less than the target size of the group, just take all of them and take whatever more you need from the next perimeter, and repeat until you reach your target group size).
  2. Remove this group and consider the new polygon that consists of the remaining sub-polygons.
  3. Repeat until remaining polygon is empty.

Implementation is up to you but this method should ensure that all formed groups are contiguous and that the remaining polygon formed at step 2 is contiguous.

EDIT:

Never mind, user58697 raises a good point, a counterexample to the algorithm above would be a polygon in the shape of an 8, where one sub-polygon bridges two other polygons.

user_131053680
Related