重叠圆的组合面积

Question

最近我遇到了一个问题，需要计算四个圆的并集面积（包括圆心和半径）。

例如下面的这张图片:

对于两个圆来说，计算起来很容易:

我可以计算每个圆中不在三角形内的部分所占的比例，然后计算三角形的面积。

但是当有两个以上的圆时，是否存在一种聪明的算法可以使用呢？

- Anton Hansson

---

这是一个非常有趣的问题，我记得在高中几何课上看到过，但从未找到解决方法。如果你在这里找不到答案，请尝试在http://mathoverflow.net/发帖，让数学家来试试吧:P - Charles Ma

有时候真正的程序员需要真正的数学。 - fa.

对于解决这个问题，你有什么想法呢？“我们在这四个地点有销售代表，每个代表负责一个以这四个半径为范围的区域。我们覆盖了国家的多大面积？”如果你拥有一个不断变化的销售代表数据库，这就成为了一个编程问题！ - Chris Roberts

实际上，这是真正的程序员喜欢思考的问题类型。 - MAK

@zvolkov：电路板用一种语言描述，它会放置方块和圆形，并可选择拖动它们。 "计算铜面积"。（这可能需要计算蚀刻时间，知道是否要添加清除艺术品等各种事情。） - DigitalRoss

Answer 1

在外围找到所有圆的交点（例如下图中的B、D、F、H）。将它们与相应圆的中心连接起来形成一个多边形。圆的联合区域的面积等于多边形的面积加上由连续交点和它们之间的圆心定义的圆片的面积。您还需要考虑任何孔。

- Ants Aasma

---

当中心出现一个孔时会发生什么？ - John Gietzen

你需要从总数中减去孔的中心连接多边形，并将该多边形的圆形切片添加到总数中。 - Ants Aasma

不错，但我想这需要大量的实现细节来处理所有特殊情况（一个圆在另一个圆内部，没有相交点，孔洞，一个点的接触等）。 - fa.

特殊情况非常容易处理。不与周长相交的圆形被丢弃。单点接触实际上是距离为零的两个交点。可以通过在图形上运行连接组件算法来查找断开的形状，其中如果中心距小于半径总和，则两个圆形将被连接。孔是除最大面积多边形外的所有多边形。周长交点是所有不严格位于任何圆内的交点。 - Ants Aasma

是的，但孔的边界也是（小）弧线。我仍然认为这需要很多代码才能正常工作。 - fa.

Answer 2

我相信有一个聪明的算法，但是这里有一个简单的算法可以避免寻找它：

• 在圆周围放一个边界框；
• 在边界框内产生随机点；
• 判断随机点是否在其中一个圆内；
• 通过一些简单的加法和除法（比例_在范围内的点数*边界框面积）计算出面积。

当然这个算法比较愚蠢，但是：

• 你可以生成更多的点来获得尽可能准确的答案；
• 它适用于任何你可以计算出内外区别的形状；
• 它可以并行计算，因此你可以使用所有核心。

- High Performance Mark

---

这会奏效，但像这样基于均匀采样的蒙特卡罗方法通常收敛速度不是很好。 - ShreevatsaR

抱歉，尽管我欣赏您的努力并认为您的解决方案“实用”，但我认为您的方法非常错误。这是一个可以且应该通过数学手段而不是蛮力解决的问题。在这样的问题上浪费能源和核心是浪费和奢侈的。 - mafu

你说得对，我感到惭愧，但是我有一台拥有12,000个核心的集群，我可以大手大脚地使用。可我无法想出如何让那个优雅的数学解决方案适应这么多处理器。 - High Performance Mark

只要蒙特卡罗（或任何随机化）方法在合理的时间内提供所需的准确度，它本身并没有什么问题。 - MAK

@mafutrct，你说得没错。然而，在数学上犯小错误是很容易的。这个解决方案提供了一种简单的方法来测试正确性。 - Richard

Answer 3

Ants Aasma的答案给出了基本思路，但我想让它更具体化。请看下面的五个圆和它们的分解方式。

• 蓝色点是圆心。
• 红色点是圆边交点。
• 带有白色内部的红色点是圆边交点，且没有包含在任何其他圆内。

识别这三种类型的点很容易。现在构造一个图形数据结构，其中节点是蓝色点和带有白色内部的红色点。对于每个圆，将其边界上的每个交点（带有白色内部的红点）与圆中心（蓝点）之间建一条边。

这将把圆的并集分解为一组两两不相交的多边形（阴影蓝色区域）和圆形扇形（阴影绿色区域），并覆盖原始的并集（也就是说，这是一个分区）。由于每个区域都很容易计算面积，因此可以通过求和各个区域的面积来计算并集的面积。

- Timothy Shields

---

我认为我可以相当容易地计算出一组红色/白色点，但我的图论不是太好：从节点+边缘列表到计算区域的算法是什么？ - user999305

该算法可以通过使用一组非重叠三角形而不是多边形来简化。弧（绿色区域）是仅包含在一个圆中的区域。随着添加更多的圆，扩大多边形的大小。（最后你甚至可以忘记你正在谈论多边形）。这使得布尔属性和区域更容易计算。当空心红点变成实心红点时，您只需向集合中添加更多三角形，并调整它被越来越多的相交圆所“吞噬”的弧。 - Steve

如何从一组蓝色和红色/白色点中区分多边形和圆弧？ - J. Schmidt

Answer 4

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

如果您能确定一个正方形是内部、外部还是与形状相交，那么这也适用于任何形状联合。

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

该算法的步骤是在四叉树中"绘制"圆形，从低分辨率开始（例如4个单元格被标记为空）。每个单元格要么：

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

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

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

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

- fa.

---

我猜测这个方法会比蒙特卡罗内/外点算法更快地收敛。 - Frank Krueger

这似乎更容易实现。绝对是建议中最好的暴力方法。谢谢！ - Anton Hansson

暴力算法在这里被称为挤压定理。 - fa.

这就是你在区间算术中使用的算法类型。http://en.wikipedia.org/wiki/Interval_arithmetic - rjmunro

Answer 5

我喜欢对于2个相交圆的解决方法--这里是我如何使用稍微变化的同样方法来解决更为复杂的情况。

这可能会更好地帮助我们推广算法以适用于更多半重叠圆的情况。

区别在于，我开始链接中心（因此顶点位于圆心之间，而不是圆相交的地方）。我认为这样可以更好地进行推广。（在实践中，也许蒙特卡罗方法很值得一试）

_{(源自：secretGeek.net)}

- Leon Bambrick

---

我认为按照你的图片所建议的多边形分割方式可能是一个非常好的方法。有很多细节需要解决才能编写出它。如果有一串由二十个圆组成的链，每个圆仅与前一个和后一个圆重叠，那么它将如何处理？虽然手动计算很容易，但你的算法是什么？ - PeterAllenWebb

Answer 6

如果你想得到离散（而不是连续）的答案，你可以使用类似像素绘画算法的方法。

在网格上绘制圆形，然后对于大部分位于圆内的网格单元（即其至少50％的面积在一个圆内），着色每个网格单元。对整个网格执行此操作（其中网格覆盖所有由圆覆盖的区域），然后计算网格中着色单元的数量。

- David R Tribble

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)

在IT技术中，A ∪ B表示A并B，A ∩ B表示A交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个圆的交集，这可以精确计算（但我不知道如何做到这一点）。

顺便说一下，可能有更好的方法——每增加一个圆，复杂度就显著增加（可能是指数级别的，但我不确定）。

- Justin

---

格式出了什么问题？对于使用n和u表示交集和并集，我很抱歉，可能有更好的方法... - Justin

添加了一些Unicode并集（∪）和交集（∩）符号。希望它们能够正常工作。 - Spoike

Answer 8

像@Loadmaster建议的像素绘画方法在各个方面都优于数学解决方案：

1. 实现要简单得多。上述问题可以在不到100行代码的情况下解决，如此JSFiddle解决方案所示（主要是因为它的概念更简单，并且没有边缘情况或异常需要处理）。
2. 它很容易适应更一般的问题。只要能用2D绘图库呈现任何形状，无论形态如何，它就可以使用 - 圆形、椭圆形、样条曲线、多边形，甚至是位图图像。
3. 与数学解决方案相比，像素绘画解决方案的复杂度约为O [n]。这意味着随着形状数量的增加，它的性能将更好。
4. 说到性能，通常会免费获得硬件加速，因为大多数现代2D库（例如HTML5的canvas）将渲染工作卸载到图形加速器上。

像素绘制的一个缺点是解决方案的有限精度。但是，只需根据情况要求渲染到更大或更小的画布即可调整。另请注意，2D渲染代码中的反锯齿（通常默认打开）将产生比像素级别更高的精度。因此，例如，将100x100的图形渲染到相同尺寸的画布中应该会产生大约1 /（100x100x255）= .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);

- broofa

---

这个解决方案未能考虑到使用圆的面积进行数学计算。它忽略了OP的问题要点。在处理几何形状时，很多时候渲染几何图形只是其中一部分。 - Steve

Answer 9

这个问题有高效的解决方案，使用所谓的功率图。不过这是非常复杂的数学问题，我并不想轻易尝试解决。如果你需要一个“简单”的解决方案，请查找线性扫描算法。基本原理是将图形分成条带，在每个条带中计算面积相对容易。

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

- Steve Thomas

Answer 10

我一直在解决模拟重叠恒星领域的问题，尝试通过估算密集领域中实际盘面积内的真实星数来掩盖较暗的大型明星。我也希望能够通过严谨的形式分析来完成这项任务，但未能找到该任务的算法。我通过在蓝色背景上生成绿色圆盘的星场来解决这个问题，其直径由概率算法确定。一个简单的程序可以将它们配对以查看是否有重叠（使星对变成黄色）；然后颜色的像素计数生成观察区域以与理论区域进行比较。然后生成真实计数的概率曲线。这可能是一种粗暴的方法，但它似乎可行。

_{(来源：2from.com)}

- user213660