问重叠圆的组合面积

EN

找到外周上的所有圆交点(例如，下图中的B、D、F、H)。将它们与相应圆的中心连接在一起，形成一个多边形。圆并集的面积是多边形的面积+由连续交点和它们之间的圆中心定义的圆切片的面积。您还需要考虑任何漏洞。

​

​

如果你想要一个离散的(而不是连续的)答案，你可以做一些类似于像素绘制算法的事情。

在网格上绘制圆圈，如果网格的每个单元格主要包含在一个圆圈内(即至少50%的面积在其中一个圆圈内)，则给每个单元格上色。对整个网格执行此操作(其中网格跨越圆覆盖的所有区域)，然后计算网格中彩色单元格的数量。

使用所谓的电源图可以有效地解决这个问题。这真的是很繁重的数学运算，我不想马上解决。要获得一个“简单”的解决方案，请查看行扫描算法。这里的基本原则是，您将图形划分为条带，其中计算每个条带中的面积相对容易。

因此，在包含所有没有擦掉的圆的图形上，在每个位置绘制一条水平线，该位置要么是圆的顶部，要么是圆的底部，要么是两个圆的交点。请注意，在这些条带中，您需要计算的所有面积看起来都是一样的:一个两边被圆形线段替换的“梯形”。因此，如果你能计算出这样的形状，你只需对所有单独的形状进行计算，并将它们相加。这种简单方法的复杂度是O(N^3)，其中N是图中的圆圈数。通过一些巧妙的数据结构使用，您可以将这种行扫描方法改进为O(N^2 * log(N))，但是除非确实需要，否则可能不值得这么麻烦。