I want to write software that merges groups of (mainly) adjacent polygons. For example, merge the US counties into sales regions. Then, display either the boundary of these sales regions or fill them with some color indicating, let's say, sales numbers.

Preprocessing and merging the given shapes in a GIS editor is not an option, the sales groups are not given in advance.

The GIS component I use has a function for merging polygons, but it is awfully slow. Reducing the number of vertices didn't help much. Neither having the common segments of the polygons use the exact same vertices. But given the fact that the line segments of the polygons are duplicated in a shapefile (which I use at the moment as data source), I can imagine that the algorithm might have a lot of work to do.

Are there algorithms and/or data structures that can handle this problem more efficiently?

I thought of maybe using Geo Markup Language or TopoJSON, which both have the ability to define segments which can be referenced to make up polygons.

Using that, is there software which optimizes existing polygons in such way that common boundaries are factored out into one representation and references to it?


Based on the answer to an earlier related question Dissolve ploygons in QGIS or Grass to new polygons of defined population sizes I think you need AZTool which was designed to do the same job for the GB Census output areas.

Not the answer you're looking for? Browse other questions tagged or ask your own question.