如何计算多个重叠直角多边形的面积？
我正在寻找一种方法来计算多个重叠多边形覆盖的公共区域。多边形都是直角的，如果这能让事情变得更容易的话。
例如：
BBBBB BBBBB AAA---BB AAA---BB AAAAAA AA--AA AA--AA LL LL LLLLLL LLLLLL
我想找到 A、B 和 L 覆盖的公共区域，这等于： B = 5x4 = 20 + A = 6x5 = 30 + L = 4x2 + 6x2 = 20 = 70 减去重叠区域： - 10 = 60（所有多边形覆盖的公共区域）
我需要能够满足 3 个或更多多边形占据同一区域的情况。 是否有合适的算法，可以将 x/y 坐标数组的数组作为输入？ （示例 Java 源代码将非常受欢迎）。
I am looking for a way to calculate the common areas covered by multiple overlapping polygons. The polygons are all right-angled, if that helps makes things easier.
So for example:
BBBBB BBBBB AAA---BB AAA---BB AAAAAA AA--AA AA--AA LL LL LLLLLL LLLLLL
I would like to find the common area covered by A, B and L, which would equal:
B = 5x4 = 20 +
A = 6x5 = 30 +
L = 4x2 + 6x2 = 20
= 70
minus overlapping areas:
- 10 = 60 (common area covered by all polygons)
I need to be able to cater for situations where 3 or more polygons occupy the same area.
Is there a suitable algorithm for this, which could take arrays of arrays of x/y co-ordinates as inputs? (sample Java source code would be very welcome).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
计算此类面积的经典方法是使用扫描算法。您可以查看问题重叠矩形的面积以获取更简单的矩形情况下的算法描述。
然后，您可以将多边形分解为矩形，或者调整扫描算法，以便在扫描期间隐式完成此分解。
A classical way of computing such an area is to use a sweep algorithm. You can have a look at question Area of overlapping rectangles to get a description of the algorithm in the simpler case of rectangles.
Then you can either decompose your polygons into rectangles, or adapt the sweep algorithm so that this decomposition is done implicitly during the sweep.
另一种方法是使用轮廓积分计算面积。绕该区域的周长走动并使用格林定理和数值求积计算面积。简单易行。
Another way to do it would be to calculate area using a contour integral. Walk around the perimeter of the area and calculate area using Green's theorem and numerical quadrature. Easy peasy.
如果您可以将多边形表示为 2D int 或 bool 数组（如果第 ij 个槽包含在多边形中，则 A[i][j] == 1，否则为 0），那么您可以在更大的 2D 上创建多边形的并集“边界”数组。
该算法是这样的：
考虑运行时间和空间要求：需要遍历每个多边形的每个槽。需要遍历边界数组 B 的每个槽。空间的最坏情况是所有多边形的交集为空（并且可能它们间隔稀疏）。可能值得首先检查空的交叉路口情况......然后，如果交叉路口是空的，“公共”区域只是各个区域的总和。
If you can represent the polygons as 2D int or bool arrays (A[i][j] == 1 if the ijth slot is contained in the polygon, 0 otherwise) then you can create the union of the polygons on a larger 2D "bounding" array.
The algorithm is something like this:
Thinking about the run time and space requirements: need to traverse every slot of every polygon. Need to traverse every slot of the bounding array B. Worst case for space is when the intersection of all polygons is empty (and perhaps they are sparsely spaced). Might be worthwhile to check the empty intersection case first... then if the intersection is empty the "common" area is just the sum of the individual areas.