3

我正在寻找一种方法来计算多个重叠多边形所覆盖的公共区域。多边形都是直角的，如果这有助于使事情变得更容易。

例如：

   BBBB
   BBBB
AAA---BB
AAA---BB
AAAAAA
AA--AA
AA--AA
  二
  二
  LLLL
  LLLL

我想找到 A、B 和 L 所覆盖的公共区域，这将等于：B = 5x4 = 20 + A = 6x5 = 30 + L = 4x2 + 6x2 = 20 = 70 减去重叠区域：- 10 = 60 (所有多边形覆盖的公共区域）

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

4

3 回答 3

2

计算此类区域的经典方法是使用扫描算法。您可以查看问题区域重叠矩形以获得在矩形更简单情况下的算法描述。

然后，您可以将多边形分解为矩形，或调整扫描算法，以便在扫描期间隐式完成此分解。

于 2009-09-08T23:18:58.713 回答
0

另一种方法是使用轮廓积分计算面积。绕着该区域的周长走一圈，使用格林定理和数值求积计算面积。十分简单。

于 2009-09-07T19:25:06.613 回答
0

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

算法是这样的：

// 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 的每个槽。空间的最坏情况是当所有多边形的交集为空时（并且可能它们间隔稀疏）。可能值得先检查空交叉口的情况......然后如果交叉口是空的，那么“公共”区域只是各个区域的总和。

于 2009-09-07T19:43:00.587 回答