在固定位置以最少数量的重叠多边形覆盖多边形
Cover polygon with minimal number of overlapping polygons at fixed positions
如何select从一组具有固定位置且并集覆盖输入多边形的多边形中提取最少数量的多边形？
例如，让我们考虑以下输入，其中绿色多边形是查询集，蓝色多边形是查询：
正确的覆盖应该是两个多边形：
如何计算哪些多边形最有效地覆盖输入区域（最小化 selected 多边形的数量）？
我假设多边形是四边形，并且您想以最少的照片数量最大化返回的面积，因为这样您将以相同的成本获得更多的面积，可以在将来使用。
这只是一个解决方案的想法。
对于每个多边形交集部分，存储包含该交集部分的覆盖多边形列表。在您的示例中，有大约 30 个交叉部分。有的是四边形的，有的是L型的。
对于查询多边形，查找多边形包含或相交的所有相交部分。这样我们就有了一组交叉部分和每个部分的覆盖多边形列表。喜欢：
ip_1 - [c1, c3]
ip_2 - [c1, c2, c3, c6]
...
反转这个'matrix'：
c1 - [ip_1, ip_2, ...]
c2 - [ip_2, ... ]
c3 - [ip_1, ip_2, ... ]
找到列表并集是整组 ip's 的最小 c's 数是 set covering problem。
此方法找到最优解。它适用于一般多边形。在最简单的版本中，它没有解决区域最大化问题。
问题在实施中:-)
首先是创建支持多边形索引的数据结构。为此，需要一些 space 分区结构。将新的多边形插入数据结构意味着创建新的交叉点，交叉部分已经在结构中。我认为最后的交叉部分数量将是覆盖多边形数量的常数。如果你经常有四边形 spaced，那么封面由 n*m 部分组成，其中 n 和 m 可能很小。
其次是集合覆盖问题，是NP完全问题。我希望你不会有太多的套路要讲。
似乎给出正确结果的解决方案如下：
将所有多边形裁剪到查询区域
将每个裁剪多边形与与其相交的任何其他多边形分开，消除所有重复项 - 让我们称此操作为 "chopping"。例如，这样的操作将产生以下非重叠多边形：
来自以下多边形（按范围裁剪）：
所有切碎的多边形代表集合覆盖项中的宇宙；被单个裁剪覆盖多边形覆盖的裁剪多边形代表一个子集
Pre-select所有未被其他多边形并集完全覆盖的多边形对应的子集。
使用近似算法求最小集合覆盖（如所述here）
我已经使用 GeoTools. Here's the code: https://github.com/w-k/MinimalCoverage and the archive with the jar and the dependencies can be downloaded from here: https://github.com/w-k/MinimalCoverage/releases 实现了这个。
我是根据 Ante 的回答得出的，这个回答很有价值，但没有提供正确的解决方案。这是不正确的，因为满足覆盖所有交叉部分的要求会导致查询多边形覆盖过多。例如，由范围多边形裁剪的覆盖多边形（如上图）产生以下公共部分：
为了覆盖所有公共部分，我们必须 select 覆盖所有三个多边形（中间的公共部分没有被最左边或最右边的多边形完全覆盖）。
如何select从一组具有固定位置且并集覆盖输入多边形的多边形中提取最少数量的多边形？
例如，让我们考虑以下输入，其中绿色多边形是查询集，蓝色多边形是查询：
正确的覆盖应该是两个多边形：
如何计算哪些多边形最有效地覆盖输入区域（最小化 selected 多边形的数量）？
我假设多边形是四边形，并且您想以最少的照片数量最大化返回的面积，因为这样您将以相同的成本获得更多的面积，可以在将来使用。
这只是一个解决方案的想法。
对于每个多边形交集部分，存储包含该交集部分的覆盖多边形列表。在您的示例中，有大约 30 个交叉部分。有的是四边形的，有的是L型的。
对于查询多边形，查找多边形包含或相交的所有相交部分。这样我们就有了一组交叉部分和每个部分的覆盖多边形列表。喜欢：
ip_1 - [c1, c3]
ip_2 - [c1, c2, c3, c6]
...
反转这个'matrix'：
c1 - [ip_1, ip_2, ...]
c2 - [ip_2, ... ]
c3 - [ip_1, ip_2, ... ]
找到列表并集是整组 ip's 的最小 c's 数是 set covering problem。
此方法找到最优解。它适用于一般多边形。在最简单的版本中，它没有解决区域最大化问题。
问题在实施中:-)
首先是创建支持多边形索引的数据结构。为此，需要一些 space 分区结构。将新的多边形插入数据结构意味着创建新的交叉点，交叉部分已经在结构中。我认为最后的交叉部分数量将是覆盖多边形数量的常数。如果你经常有四边形 spaced，那么封面由 n*m 部分组成，其中 n 和 m 可能很小。
其次是集合覆盖问题，是NP完全问题。我希望你不会有太多的套路要讲。
似乎给出正确结果的解决方案如下：
将所有多边形裁剪到查询区域
将每个裁剪多边形与与其相交的任何其他多边形分开，消除所有重复项 - 让我们称此操作为 "chopping"。例如，这样的操作将产生以下非重叠多边形：
来自以下多边形（按范围裁剪）：
所有切碎的多边形代表集合覆盖项中的宇宙；被单个裁剪覆盖多边形覆盖的裁剪多边形代表一个子集
Pre-select所有未被其他多边形并集完全覆盖的多边形对应的子集。
使用近似算法求最小集合覆盖（如所述here）
我已经使用 GeoTools. Here's the code: https://github.com/w-k/MinimalCoverage and the archive with the jar and the dependencies can be downloaded from here: https://github.com/w-k/MinimalCoverage/releases 实现了这个。
我是根据 Ante 的回答得出的，这个回答很有价值，但没有提供正确的解决方案。这是不正确的，因为满足覆盖所有交叉部分的要求会导致查询多边形覆盖过多。例如，由范围多边形裁剪的覆盖多边形（如上图）产生以下公共部分：
为了覆盖所有公共部分，我们必须 select 覆盖所有三个多边形（中间的公共部分没有被最左边或最右边的多边形完全覆盖）。