算法要求确定矩形是否完全被一组多边形覆盖

Question

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

由于多边形数量和复杂性以及总面积A都非常大，因此基于多边形并集的方法可能无法在时间上得到解决。为了简化问题，我定义了A'作为A内部最小区域的大小，其覆盖范围我关心。我考虑构建类似于2D段树的结构，重复地将区域分成2D （每个区域正方形分成4个子正方形，直到子正方形大小为A'），但由于我们在处理多边形，所以我不确定这种方法是否足够高效。

- user1089464

---

什么是限制？多边形数量，最小最大坐标（目标多边形和所有其他多边形）。 - Толя

我认为这可能会有所帮助：https://dev59.com/SnE95IYBdhLWcg3wi-Uc - Tony Morris

[1] 我有超过50K个多边形，而A的大小相当大。为了增加更多上下文，我不得不将A分成14次才能达到A'的大小（即）A = 4 ^ 14 * A'。@TonyMorris，我处理的多边形非常复杂，拥有内部空洞等。我使用了第三方库来找到联合体（如帖子中所述），但是它没有用处。另一方面，查找矩形是否落在这些多边形内速度更快，这就是我尝试2D线段树方法的原因。 - user1089464

Answer 1

你可以使用多边形相交或差集代替并集：

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

- Ehsan Shoja

---

顺便问一下，我们如何实现一个二维线段树？与一维树相比，我在这里看到的问题是，在一维树中，我们知道查询范围只会在遍历深度并返回结果时分裂两次。但在二维中，情况似乎并非如此。 - user1089464

我认为对于2D线段树，你应该首先考虑线段的x投影，从而得到一个1D线段树，然后每个节点也是一个1D线段树，覆盖节点x范围内的线段的y投影。 - Ehsan Shoja

另外，我之前的回答需要计算A-P'，如果多边形P'包含孔，这似乎会很棘手。 - Ehsan Shoja

是的，我也正要说同样的话。我匆忙采用了那个解决方案，但使用 A-P' 解决方案运行时创建复杂多边形联合的问题又出现了。 - user1089464