polygon - 在固定位置用最少数量的重叠多边形覆盖多边形

Question

如何从一组固定位置的多边形中选择最少数量的多边形，其并集覆盖输入多边形？

例如，让我们考虑以下输入，其中绿色多边形是查询集，蓝色多边形是查询:

正确的覆盖应该是两个多边形:

如何计算哪些多边形最有效地覆盖输入区域(最小化所选多边形的数量)？

Answer 1

我认为多边形是四边形，并且您希望以最少数量的照片最大化返回区域，因为这样您将以相同的成本获得更多区域，以便将来使用。

这只是一个关于解决方案的想法。

对于每个多边形交叉部分，存储包含该交叉部分的覆盖多边形列表。在您的示例中，有大约 30 个交叉部分。有些是四边形，有些是 L 形。

对于查询多边形，查找多边形包含或相交的所有相交部分。这样我们就有了一组交叉部分以及每个部分的覆盖多边形列表。喜欢:

ip_1 - [c1, c3]
ip_2 - [c1, c2, c3, c6]
...

反转这个“矩阵”:

c1 - [ip_1, ip_2, ...]
c2 - [ip_2, ... ]
c3 - [ip_1, ip_2, ... ]

找到列表并集是整个 ip 集合的最小数量的 c 是 set covering problem .

该方法找到最优解。它适用于一般多边形。在最简单的版本中，它不能解决面积最大化问题。

问题出在实现中:-)

首先是创建支持多边形索引的数据结构。为此，需要一些空间分区结构。将新多边形插入数据结构意味着与结构中已有的相交部分创建新的相交。我认为末端相交部分的数量将是覆盖多边形数量的常数因子。如果您的四边形间隔规则，则覆盖物由 n*m 部分组成，其中 n 和 m 可能很小。

第二个是集合覆盖问题，它是NP完全的。我希望您不会有太多的内容需要涵盖。