algorithm - 给定 n 个重叠的多边形，如何获得以最少的多边形数量提供最多覆盖的集合

Question

我想获得提供最大覆盖范围的最小多边形集。例如，对于下图中的多边形，红色的那些不应该被切割，因为它们已经被一个或多个多边形覆盖（去掉其他多边形中的多边形是不够的）。孔是好的和预期的（如第二张图片）。

上面多边形的数据在这里：

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

我很乐意采用任何语言的算法，甚至是关于如何解决这个问题的数学描述。该图像是一个示例，但就我而言，我有数千个多边形（卫星图像边界）。

标签： algorithmgeospatialpostgispolygoncomputational-geometry

Answer 1

@btilly 提到了相关的近似硬度结果，但在实践中你应该能够得到一个好的结果：

1. 用离散元素制​​定加权覆盖问题。通过找到适当的平面细分，有一个聪明的方法可以做到这一点。还有一种不太聪明的方法可以做到这一点，通过重复寻找相交的一对多边形 P 和 Q 并用子多边形 P ∖ Q、P ∩ Q、Q ∖ P 替换它们，跟踪 sub 之间的对应关系-多边形和原始多边形。计算几何库将为您节省大量时间——也许是 CGAL？

2. 使用整数规划解决此覆盖问题。我偏爱OR-Tools，因为它是由我的同事开发的，但您有很多选择。