问题:

I want to partition a US state into 20 parts of approximately equal population. I can do this using, say, tracts, ZIP codes or another smaller geography. I'm looking for an algorithm to do the partitioning. It can be in any language or software (ArcGIS, QGIS, python, PostGIS, R, node).

For grouping or clustering algorithms I've looked at like k-means, ArcGIS Grouping Analysis, etc. These do not seem to do what's needed, since they group based on the similarity of a variable don't partition into equal size based on a variable. My quick look at ESRI's districting tool suggests that this might be a possibility.

Any other suggestions?

回答1:

You should consider the Shortest splitline algorithm, recommended for creating optimally compact voting districts. Here is a description of its results in solving gerrymandering.

回答2:

You can try centroidal weighted voronoi diagrams. i.e. Loyds algorithm. Pick the voronoi diagram and the center of gravity of each voronoi cell and rinse and repeat:http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/