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

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

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



正确的覆盖应使用两个多边形：



如何计算哪些多边形最有效地覆盖了输入区域（最大限度地减少了选定多边形的数量）？

最佳答案

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

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

对于每个多边形相交部分，存储包含该相交部分的封面多边形的列表。在您的示例中，有〜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, ... ]

找到列表联合为c's的整个集合的ip's的最小数量为set covering problem。

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

问题在执行中:-)

首先是创建支持多边形索引的数据结构。为此，需要一些空间分区结构。在数据结构中插入新的多边形意味着使用结构中已经存在的相交部分创建新的相交。我认为最后的相交部分数量将是覆盖多边形数量的常数。如果您的四边形规则排列，则封面由n*m个部分组成，其中n和m可能很小。

其次是设置覆盖问题，它是NP完全的。我希望您不会涉及太多套。

关于polygon - 在固定位置覆盖最少数量的重叠多边形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31701570/