Given n overlapping polygons, how could one get the set that provides the most coverage with the minimum number of polygons

user_15231140 0
Viewed 106

I want to get the minimum set of polygons that provide the maximum coverage. For example, for the polygons in the image below, the ones in red should not make the cut as they are already covered by one or more polygons (getting rid of the polygons within other polygons is not enough). Holes are ok and expected (as in the second image).

Example 1 Example 2

The data for the polygons above is here:

http://geojson.io/#id=gist:rumicuna/b36cab7d0019511b92120db130a73d44&map=8/38.311/-81.403

I would happily take an algorithm in any language or even a mathematical description on how to approach this problem. The image is an example, but in my case, I have thousands of polygons (satellite image bounds).

postgis polygon computational-geometry geospatial algorithm
1 Answers

@btilly mentioned the relevant approximation hardness result, but in practice you should be able to get a good result:

  1. Formulate a weighted coverage problem with discrete elements. There's a clever way to do this, by finding the appropriate planar subdivision. There's also a less clever way to do this, by repeating looking for a pair of polygons P and Q that intersect and replacing them with the sub-polygons P ∖ Q, P ∩ Q, Q ∖ P, keeping track of the correspondence between sub-polygons and original polygons. A computational geometry library will save you a lot of time -- maybe CGAL?

  2. Solve this coverage problem using integer programming. I'm partial to OR-Tools since it's developed by colleagues of mine, but you have a lot of options.

user_21446690
Related