给定 n 个重叠的多边形，如何以最少的多边形数量获得覆盖范围最大的集合
Given n overlapping polygons, how could one get the set that provides the most coverage with the minimum number of polygons
我想要获得提供最大覆盖范围的最小多边形集。例如，对于下图中的多边形，红色部分不应进行切割，因为它们已经被一个或多个多边形覆盖（去除其他多边形中的多边形是不够的）。孔是正常的并且在意料之中（如第二张图片所示）。
上面多边形的数据在这里：
http://geojson.io/#id=gist:rumicuna/b36cab7d0019511b92120db130a73d44&map=8/38.311/-81.403
我很乐意采用任何语言的算法甚至数学描述来解决这个问题。该图像是一个示例，但就我而言，我有数千个多边形（卫星图像边界）。
@btilly 提到了相关的近似硬度结果，但在实践中你应该可以得到一个不错的结果：
用离散元素构造一个weighted coverage problem。有一种聪明的方法可以通过找到合适的平面细分来做到这一点。还有一个不太聪明的方法，通过重复寻找一对相交的多边形 P 和 Q 并将它们替换为子多边形 P ∖ Q，P ∩ Q，Q ∖ P，跟踪子多边形之间的对应关系-多边形和原始多边形。计算几何库将为您节省大量时间 -- 也许是 CGAL？
使用整数规划解决这个覆盖问题。我偏爱 OR-Tools，因为它是由我的同事开发的，但您有很多选择。
我想要获得提供最大覆盖范围的最小多边形集。例如，对于下图中的多边形，红色部分不应进行切割，因为它们已经被一个或多个多边形覆盖（去除其他多边形中的多边形是不够的）。孔是正常的并且在意料之中（如第二张图片所示）。
上面多边形的数据在这里：
http://geojson.io/#id=gist:rumicuna/b36cab7d0019511b92120db130a73d44&map=8/38.311/-81.403
我很乐意采用任何语言的算法甚至数学描述来解决这个问题。该图像是一个示例，但就我而言，我有数千个多边形（卫星图像边界）。
@btilly 提到了相关的近似硬度结果，但在实践中你应该可以得到一个不错的结果：
用离散元素构造一个weighted coverage problem。有一种聪明的方法可以通过找到合适的平面细分来做到这一点。还有一个不太聪明的方法，通过重复寻找一对相交的多边形 P 和 Q 并将它们替换为子多边形 P ∖ Q，P ∩ Q，Q ∖ P，跟踪子多边形之间的对应关系-多边形和原始多边形。计算几何库将为您节省大量时间 -- 也许是 CGAL？
使用整数规划解决这个覆盖问题。我偏爱 OR-Tools，因为它是由我的同事开发的，但您有很多选择。