给定n个重叠的多边形，如何获取提供最大覆盖面积且多边形数量最少的集合

Question

3

我希望获得提供最大覆盖范围的最小多边形集。例如，在下面的图像中，红色的多边形不应该被包括在内，因为它们已经被一个或多个多边形覆盖（仅仅消除其他多边形内部的多边形是不够的）。孔洞是可以的，并且也是预期的（如第二张图片所示）。

上述多边形的数据在此处：

我很乐意接受任何语言的算法，甚至是如何解决这个问题的数学描述。这张图片只是一个例子，但在我的情况下，我有成千上万个多边形（卫星图像边界）。

- M P

1

https://en.wikipedia.org/wiki/Polygon_covering#Covering_a_polygon_with_convex_polygons 表示你的问题是NP完全问题，但有近似算法。 - btilly

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

@btilly提到了相关的近似难度结果，但实际上您应该能够获得良好的结果：

用离散元素制定加权覆盖问题。有一种聪明的方法可以做到这一点，即找到适当的平面划分。还有一种不那么聪明的方法，就是重复查找一对相交的多边形P和Q，并用子多边形P∖Q、P∩Q、Q∖P替换它们，跟踪子多边形与原始多边形之间的对应关系。计算几何库将为您节省大量时间--也许是CGAL？
使用整数规划解决此覆盖问题。我倾向于OR-Tools，因为它是由我的同事开发的，但您有很多选择。