Group polygons by count and spatially

[Emilbrundage]

I have a polygon feature class that represents work areas in a given region. My task is to divide the work up evenly between n number of agents. The groups of polygon features should be grouped close together, and there should be similar counts per group.

So, for example, if i have a feature class with 80 polygons, and I have 4 agents, I'd need an end result of 4 groups of 20 polygons, with each group spatially close together.

I've developed a script that uses near analysis among other techniques to test various combinations of polygons. I first find all possible OID combs with itertools.combinations, and from there start testing each combo. It's fairly random at this point and takes a very long time. I have incorporated only using combos with the min and max X and Y features, and developed a bit of a way to 'hunt' in areas that are close to right, but still things are slow. Currently it's just easier to do it by hand, but I'd like it to be automated and work in a manageable amount of time. Any ideas?

Thanks!

[DouglasSands]

The only approach I can think of is to start by getting the bounding box for your polygon layer. From that, you could create 4 polygons, one for each quadrant of the bounding box. Then you would do a spatial selection and count (using arcpy.GetCount_management) the number of polygons inside each quadrant.

Then you could would start with the upper-right quadrant. If the number of polygons is to high, then you 'assign' the polygons closest to the left edge to the upper left quadrant (regardless of how many are in that quadrant) and increase the sum you got for the upper left quadrant. If there are too few (or 20), you do nothing.

Now you move to the upper left quadrant. If it contains more than 1/4 of the polygons, you find the n closest polygons to its lower edge where n is however many to great the polygon count is to the lower-left polygon and increase the lower left quadrant's count.

For the lower-left polygon, you again assess the count and if it is to great, you move extra polygons from the top edge into the top-right polygon.

You may have to loop through this a few times, but I don't think you could possibly have to loop more than twice. Also, you would check between each step and if the count for each quadrant is what you want, then you stop immediately. I can draw it out on paper and I think this would work and get a result something like what you want, but I don't have any code to share with you. I think it should be a lot faster than looping through every possible mix of polygons to identify the ideal distribution

Hope this helps,

- Doug

[Emilbrundage]

Thanks for the reply. This is perhaps a start, but your method of using quadrants I think assumes there are four agents each time. In fact, there may be 2, or 3, or 10, etc.

[DanPatterson_Retired]

As your criteria changes, I would also agree with your doing it faster by hand method, alternatively, do the agents have any preference as to their desired working area?

[XanderBakker]

Maybe the recently introduced Grouping Analysis (Spatial Statistics)  might be what you are looking for...