重叠圆圈的组合区域

我最近遇到了一个问题，我有四个圆圈（中点和半径），并且必须计算这些圆圈的面积。

示例图像：

对于两个圈子来说很简单，

我可以计算不在三角形内的每个圆圈区域的分数，然后计算三角形的面积。

但是当有两个以上的圆圈时，我可以使用一个聪明的算法吗？

---

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

---

我确信有一个聪明的算法，但是这是一个愚蠢的算法，不必去寻找它;

在圈子周围放一个边框;

在边界框内生成随机点;

确定随机点是否在一个圆圈内;

通过一些简单的加法和除法来计算面积（proportion_of_points_inside * area_of_bounding_box）。

确定它是愚蠢的，但是：

你可以得到准确的答案，只要你想要的，只是产生更多的点;

它可以用于你可以计算内部/外部区别的任何形状;

它将会很好地并行，所以你可以使用你所有的内核。

---

对于与前一个不同的解决方案，您可以使用四叉树以任意精度生成估计。

如果您可以确定方形是内部还是外部还是与形状相交，这也适用于任何形状联合。

每个单元格都有一个状态：空，全，部分

该算法包括以低分辨率（例如标记为空的4个单元）开始“绘制”四叉树中的圆圈。 每个单元格是：

在至少一个圆圈内，然后将单元格标记为已满，

在所有圈子之外，将单元格标记为空，

否则将该单元格标记为部分。

完成后，可以计算区域的估计值：全部单元格给出下限，空单元格给出更高边界，部分单元格给出最大面积误差。

如果错误对您来说太大，您可以细化部分单元格，直到获得正确的精度。

我认为这比处理大量特殊情况需要的几何方法更容易实现。

链接地址: http://www.djcxy.com/p/84975.html

上一篇: Combined area of overlapping circles

下一篇: Locate point using trilateration method