algorithm - 重叠圆的组合面积

Question

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

示例图片：

两个圈子很容易，

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

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

Answer 1

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

Answer 2

我确信有一个聪明的算法，但这里有一个愚蠢的算法，可以省去寻找它；

• 在圆圈周围放置一个边界框；
• 在边界框内生成随机点；
• 找出随机点是否在其中一个圆圈内；
• 通过一些简单的加法和除法计算面积（proportion_of_points_inside*area_of_bounding_box）。

当然这很愚蠢，但是：

• 您可以根据需要获得准确的答案，只需生成更多积分；
• 它适用于您可以计算内部/外部区别的任何形状；
• 它会很好地并行化，因此您可以使用所有内核。

Answer 3

Ants Aasma 的回答给出了基本的想法，但我想让它更具体一点。看看下面的五个圆圈以及它们被分解的方式。

• 蓝点是圆心。
• 红点是圆形边界交叉点。
• 白色内部的红点是不包含在任何其他圆圈中的圆圈边界交叉点。

识别这三种类型的点很容易。现在构建一个图形数据结构，其中节点是蓝点和内部为白色的红点。对于每个圆圈，在圆圈中间（蓝点）和它的每个交点（内部为白色的红点）之间放置一条边。

这将圆形联合分解为一组多边形（蓝色阴影）和圆形饼块（绿色阴影），它们成对不相交并覆盖原始联合（即分区）。由于这里的每一块都很容易计算面积，因此您可以通过对块的面积求和来计算并集的面积。

Answer 4

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

如果您可以判断正方形是在内部还是外部或与形状相交，这也适用于任何形状联合。

每个单元格都有以下状态之一：空、满、部分

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

• 在至少一个圆圈内，然后将单元格标记为已满，
• 在所有圈子之外，将单元格标记为空，
• 否则将单元格标记为部分。

完成后，您可以计算面积估计值：完整单元格给出下限，空单元格给出上限，部分单元格给出最大面积误差。

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

我认为这将比可能需要处理许多特殊情况的几何方法更容易实现。

Answer 5

我喜欢 2 个相交圆的情况的方法——这就是我如何对更复杂的例子使用相同方法的轻微变化。

它可能会更好地了解将算法推广到更多的半重叠圆。

这里的不同之处在于我首先连接中心（所以在圆的中心之间有一个顶点，而不是在圆相交的地方之间）我认为这可以让它更好地概括。

（在实践中，也许蒙特卡罗方法是值得的）

_{（来源：secretGeek.net）}

Answer 6

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

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

Answer 7

嗯，很有趣的问题。我的方法可能类似于以下内容：

• 找出一种方法来计算任意数量的圆圈之间的交点是什么，即如果我有 3 个圆圈，我需要能够计算出这些圆圈之间的交点是什么。“蒙特卡洛”方法将是一种近似此方法的好方法（http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/）。
• 消除完全包含在另一个更大圆圈中的任何圆圈（查看半径和两个圆圈中心之间距离的模数）我认为不是强制性的。
• 选择 2 个圆圈（称为 A 和 B）并使用以下公式计算总面积：

（这适用于任何形状，无论是圆形还是其他）

area(A∪B) = area(A) + area(B) - area(A∩B)

WhereA ∪ B表示 A union B 并且A ∩ B表示 A intersect B （您可以从第一步开始计算。

• 现在继续添加圆圈并继续计算添加的面积，作为圆圈面积和圆圈之间相交面积的总和/减法。例如对于 3 个圆（称为额外的圆 C），我们使用以下公式计算面积：

A（这与上面替换为的相同A∪B）

area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)

我们area(A∪B)刚刚解决的地方，area((A∪B)∩C)可以找到：

area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)

你又可以在哪里找到上面的区域（A∩B∩C）。

棘手的一点是最后一步 - 添加的圆圈越多，它变得越复杂。我相信有一个扩展来计算一个有限联合的交叉区域，或者你可以递归地计算它。

另外关于使用蒙特卡罗来近似迭代的面积，我相信可以将任意数量的圆的交点减少到这些圆的4个的交点，这可以精确计算（不知道如何做到这一点然而）。

顺便说一句，可能有更好的方法 - 对于每个添加的额外圆圈，复杂性显着增加（可能成倍增加，但我不确定）。

Answer 8

我一直在研究模拟重叠星场的问题，试图从密集场中的实际圆盘区域估计真实的恒星数量，其中较大的明亮恒星可以掩盖较暗的恒星。我也曾希望能够通过严格的形式分析来做到这一点，但无法找到该任务的算法。我通过将蓝色背景上的星场生成为绿色圆盘来解决它，其直径由概率算法确定。一个简单的例程可以将它们配对以查看是否存在重叠（将星对变为黄色）；然后颜色的像素计数生成观察区域以与理论区域进行比较。然后，这会生成真实计数的概率曲线。也许是蛮力，但它似乎工作正常。_{（来源：2from.com）}

Answer 9

这是一个在实践中应该很容易实现的算法，并且可以调整以产生任意小的错误：

1. 用一个以同一点为中心的正多边形来近似每个圆
2. 计算作为近似圆的并集的多边形
3. 计算合并多边形的面积

步骤 2 和 3 可以使用标准的、易于从计算几何中找到的算法来执行。

显然，您为每个近似多边形使用的边越多，您的答案就越接近准确。您可以使用内接和外接多边形进行近似，以获得确切答案的界限。

Answer 10

使用所谓的功率图可以有效地解决这个问题。不过，这确实是一项繁重的数学运算，而不是我想临时解决的问题。对于“简单”的解决方案，请查找线扫描算法。这里的基本原则是将图形分成条带，计算每个条带的面积相对容易。

因此，在包含所有没有被擦掉的圆圈的图形上，在每个位置画一条水平线，即圆的顶部、圆的底部或两个圆的交点。请注意，在这些条带内，您需要计算的所有区域看起来都一样：一个“梯形”，两侧被圆形线段取代。因此，如果您可以计算出如何计算这样的形状，您只需对所有单独的形状进行计算并将它们加在一起即可。这种朴素方法的复杂度是 O(N^3)，其中 N 是图中的圆圈数。通过一些巧妙的数据结构使用，您可以将此行扫描方法改进为 O(N^2 * log(N))，但除非您真的需要，否则可能不值得麻烦。

Answer 11

我发现这个链接可能有用。不过好像还没有一个确定的答案。 谷歌答案。三个圆的另一个参考是Haruki 定理。那里也有一张纸。

Answer 12

根据您要解决的问题，它可能足以获得上限和下限。上限很简单，只是所有圆圈的总和。对于下限，您可以选择一个半径，使所有圆都不重叠。为了更好地找到每个圆的最大半径（直到实际半径），使其不重叠。删除任何完全重叠的圆也应该很简单（所有这些圆都满足|P_a - P_b| <= r_a），其中P_a是圆A的中心，P_b是圆B的中心，r_a是A的半径) 并且这改善了上限和下限。如果您在任意对上使用您的配对公式，而​​不仅仅是所有圆圈的总和，您还可以获得更好的上限。可能有一种选择“最佳”的好方法

给定一个上限和下限，您可能能够更好地调整蒙特卡罗方法，但没有什么特别的想法。另一种选择（同样取决于您的应用程序）是对圆进行光栅化并计算像素。它基本上是具有固定分布的蒙特卡罗方法。

Answer 13

像素绘画方法（如@Loadmaster 所建议的）在很多方面都优于数学解决方案：

1. 实现要简单得多。上述问题可以用不到 100 行代码解决，正如这个 JSFiddle 解决方案所展示的那样（主要是因为它在概念上要简单得多，并且没有需要处理的边缘情况或异常）。
2. 它很容易适应更普遍的问题。它适用于任何形状，无论形态如何，只要它可以用 2D 绘图库（即“所有这些！”）渲染——圆形、椭圆、样条线、多边形，应有尽有。哎呀，甚至位图图像。
3. 像素绘画解决方案的复杂度为~O[n]，而数学解决方案的复杂度为~O[n*n]。这意味着随着形状数量的增加，它将表现得更好。
4. 说到性能，您通常会免费获得硬件加速，因为大多数现代 2D 库（如 HTML5 的画布，我相信）会将渲染工作卸载到图形加速器。

像素绘画的一个缺点是解决方案的有限精度。但这可以通过根据情况需要简单地渲染到更大或更小的画布来进行调整。还要注意， 2D 渲染代码中的抗锯齿（通常默认打开）将产生优于像素级的精度。因此，例如，将 100x100 的图形渲染到相同尺寸的画布上，我认为应该会产生大约 1 / (100 x 100 x 255) = .000039% 的精度……这可能“足够好”除了最苛刻的问题之外的所有问题。

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>

// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);

Answer 14

这可以使用格林定理来解决，复杂度为 n^2log(n)。如果您不熟悉格林定理并想了解更多信息，这里是可汗学院的视频和笔记。但是为了我们的问题，我想我的描述就足够了。

如果我把L和M这样

那么 RHS 就是区域R的面积，可以通过求解闭积分或 LHS 获得，这正是我们要做的。

因此，沿逆时针方向积分给我们区域的面积，而沿顺时针方向积分给我们面积的负值。所以

AreaOfUnion =（沿逆时针方向沿红色弧的积分+沿顺时针方向沿蓝色弧的积分）

但是很酷的技巧是，如果对于每个圆，如果我们整合不在任何其他圆内的弧，我们就会得到所需的区域，即我们沿着所有红色弧在逆时针方向上整合，沿着顺时针方向沿着所有蓝色弧整合。任务完成！！！

即使是圆不与其他圆相交的情况也会得到处理。

这是我的C++ 代码的 GitHub 链接

Answer 15

如果你知道你所有的圆圈都将在一个特定的区域内，我有办法得到一个近似的答案，即圆圈中的每个点都在一个你知道其尺寸的盒子内。例如，如果所有圆圈都在已知大小的图像中，则该假设将是有效的。如果您可以做出此假设，请将包含您的图像的区域划分为“像素”。对于每个像素，计算它是否在至少一个圆圈内。如果是，则将运行总计加一。完成后，您知道至少一个圆圈内有多少像素，并且您还知道每个像素的面积，因此您可以计算所有重叠圆圈的总面积。

通过增加您所在区域的“分辨率”（像素数），您可以改进近似值。

此外，如果包含您的圆圈的区域的大小是有界的，并且您保持分辨率（像素数）不变，则算法在 O(n) 时间内运行（n 是圆圈数）。这是因为对于每个像素，您必须检查它是否在您的 n 个圆圈中的每个圆圈内，并且像素的总数是有界的。