algorithm - 确定一个矩形是否被一组多边形完全覆盖所需的算法

Question

给定一组多边形 P 和一个矩形区域 A，我需要验证 A 是否完全被 P 覆盖。

多边形的数量和复杂性以及总面积 A 非常大，因此基于多边形联合的方法可能无法及时工作。为了让事情更简单一点，我将 A' 定义为 A 内我关心的最小区域的大小。我想建立一个 2D 分段树状结构，重复划分 2D 区域（每个区域正方形分成 4 个子正方形，直到子正方形大小为 A'）但由于我们在这里处理多边形，我不确定是否这将足够有效。

Answer 1

您可以使用多边形交集或差异而不是联合：

将 A 本身视为一个多边形，每次选择一个多边形 P' 并将 A 细化为 A - P'，并检查 A 是否为空。检查所有多边形后，您可以确定 A 是否被 P 覆盖。