如何计算多个重叠直角多边形的面积？

Question

我正在寻找一种计算多个重叠多边形共同覆盖面积的方法。如果这些多边形都是直角的，那么将更容易计算。

例如：

我想找到A、B和L的公共区域，它们的面积分别为： B = 5x4 = 20 + A = 6x5 = 30 + L = 4x2 + 6x2 = 20 = 70 减去重叠的部分： - 10 = 60（所有多边形共同覆盖的区域）

我需要能够处理三个或更多多边形占据同一区域的情况。是否有适合此需求的算法，可以将x/y坐标的数组作为输入？（欢迎提供Java示例源代码）。

- Martin

---

我应该补充一下，这些多边形可能并不全部重叠，有些可能是“独立的”。是否有一种算法也可以处理这种情况？ - Martin

Answer 1

一种计算这样一个区域的经典方法是使用扫描线算法。您可以查看问题重叠矩形的面积，以获得在更简单的矩形情况下算法的描述。

然后，您可以将多边形分解为矩形，或者调整扫描算法，使得在扫描过程中隐式地进行此分解。

- Camille

Answer 2

如果您可以将多边形表示为2D int或bool数组（如果第ij个插槽包含在多边形中，则A [i] [j] == 1，否则为0），那么您可以在更大的2D“Bounding”数组上创建多边形的并集。

算法大致如下：

// get your polygons, each represented by a 2D array as described above

// create a "bounding" array B that can contain all polygons (watch out for
// sparsely spaced polygons in which case B could be large)

// populate B s.t. B[i][j] == 1 if ijth slot is contained in 
// the union of all polygons

// count all slots in B where B[i][j] == 1 (this will be the "common" area)

考虑运行时间和空间需求: 需要遍历每个多边形的每个插槽。需要遍历边界数组B的每个插槽。当所有多边形的交集为空(且它们可能是稀疏分布)时，最坏的空间情况就产生了。首先检查空交集情况可能是值得的...然后如果交集为空，“公共”区域就是各个区域的面积之和。

- MrDatabase

Answer 3

另一种方法是使用轮廓积分来计算面积。沿着区域的周长走一圈，使用格林公式和数值积分来计算面积。非常简单。

- duffymo

---

这种方法的问题在于，找到周长并不比找到面积容易。 - Camille

如果所有的多边形都是四边形，那么内部节点将被四个多边形共享。周边节点则由一个、两个或三个多边形共享。您可以识别周边节点并从任意点开始行走，转移到下一个周边节点。沿着该边缘进行积分，然后找到下一个边缘。 - duffymo

我不明白为什么四个多边形要共享内部节点。例如，考虑两个重叠的矩形（每个矩形覆盖另一个矩形的一个角）。您还必须识别不是原始多边形节点的周边节点。当然，您可以确定联合体的边界，但无论如何都必须使用某种扫描算法来完成该任务，因此我的评论。 - Camille