重叠圆的组合面积

我发现这个链接可能是有用的。但似乎没有一个明确的答案。 谷歌回答 。另一个关于三个圈的参考是 春树定理。那里也有一篇论文。

我敢肯定有一个聪明的算法，但这里有一个愚蠢的节省寻找它;

• 在圆周周围放置一个边框;
• 在所述包围盒内生成随机点;
• 计算出随机点是否在其中一个圆内;
• 通过一些简单的加法和除法计算面积(比例 _ _ 点 _ 内 * 面积 _ 的 _ 边界 _ 盒子)。

虽然很蠢，但是:

• 你可以得到你想要的准确答案，只是得到更多的分数;
• 它适用于任何形状，你可以计算内部/外部的区别;
• it will parallelise beautifully so you can use all your cores.

我喜欢这种处理两个相交圆的方法——下面是我如何在更复杂的示例中使用相同方法的一点变化。

它可能给更好的洞察力推广算法的更多数量的半重叠圆。

这里的不同之处在于，我从连接中心开始(所以在圆的中心之间有一个顶点，而不是在两个圆相交的地方之间) ，我认为这样可以更好地概括。

(在实践中，也许蒙特卡洛方法是值得的)

_{(来源: Secret Geek.net)}

嗯，非常有趣的问题。我的方法大概是这样的:

• 找出一种方法来计算任意数量的圆之间的交点面积，也就是说，如果我有3个圆，我需要能够计算出这些圆之间的交点面积。“蒙特卡罗”方法将是一个很好的方法来近似这个(http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/)。
• 消除任何完全包含在另一个大圆圈中的圆圈(看半径和两个圆圈中心距离的模数) ，我不认为这是强制性的。
• Choose 2 circles (call them A and B) and work out the total area using this formula:

(对于任何形状，无论是圆形还是其他形状，都是如此)

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

Where A ∪ B means A union B and A ∩ B means A intersect B (you can work this out from the first step.

• 现在继续添加圆，并且继续计算作为圆的面积和/减去的面积以及圆与圆之间的交点的面积所添加的面积。例如，对于3个圆(称为额外的圆 C) ，我们用下面的公式计算面积:

(这与上面用 A∪B代替 A的情况相同)

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个圆的交集，这样就可以精确地计算出来(但是不知道如何做到这一点)。

顺便说一下，可能有一个更好的方法来做到这一点——对于每增加一个额外的圆，复杂性都会显著增加(可能是指数级增长，但我不确定)。

Find all circle intersections on the outer perimeter (e.g. B,D,F,H on the following diagram). Connect them together with the centres of the corresponding circles to form a polygon. The area of the union of the circles is the area of the polygon + the area of the circle slices defined by consecutive intersection points and the circle center in between them. You'll need to also account for any holes.

根据你试图解决的问题，它可能足以得到一个上限和下限。上界很简单，就是所有圆的总和。对于一个下限，你可以选择一个单一的半径，使任何圆重叠。为了更好地找到每个圆的最大半径(直到实际半径) ，这样它就不会重叠。去掉任何完全重叠的圆(所有这些圆都满足 | P _ a-P _ b | < = r _ a) ，其中 P _ a 是圆 A 的中心，P _ b 是圆 B 的中心，而 r _ a 是 A 的半径)也应该是相当琐碎的，这样就更好地得到了上界和下界。如果在任意对上使用配对公式，而不仅仅是所有圆的和，你也可以得到一个更好的上界。可能有一个很好的方法来选择“最佳”对(导致最小总面积的对)。

给定一个上限和下限，您可能能够更好地调优 Monte-Carlo 方法，但是没有什么具体的想法。另一个选择(同样取决于您的应用程序)是栅格化圆圈并计算像素。它基本上是具有固定分布的蒙特卡罗方法。

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

这也适用于任何形状联合，如果你可以告诉一个正方形是内部或外部或相交的形状。

每个单元格都有一种状态: 空、满、部分

该算法包括在四叉树中“绘制”以低分辨率开始的圆(例如标记为空的4个单元格)。每个细胞都是:

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

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

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

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

如果您希望得到一个离散的(而不是连续的)答案，那么您可以做一些类似于像素绘制算法的事情。

在一个网格上画圆，然后如果网格的每个单元格大部分都包含在一个圆里面(也就是说，至少50% 的面积是在其中一个圆里面) ，就给它上色。对整个网格执行此操作(网格覆盖了圆圈覆盖的所有区域) ，然后计算网格中有色单元格的数量。

这里有一个算法，应该很容易在实践中实现，并可以进行调整，以产生任意小的错误:

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

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

显然，每个近似多边形使用的边越多，你的答案就越精确。您可以近似地使用内接和外接多边形来获得精确答案的边界。

我一直在研究一个模拟重叠恒星区域的问题，试图从密集区域的实际圆盘区域估算出真正的恒星数量，在那里较大的明亮恒星可以掩盖较暗的恒星。我也曾希望能够通过严格的形式分析来做到这一点，但未能找到任务的算法。我通过在蓝色背景上以绿色圆盘的形式生成星场来解决这个问题，绿色圆盘的直径是由概率算法决定的。一个简单的例程可以将它们配对以查看是否有重叠(将星对变为黄色) ; 然后颜色的像素计数生成观察区域以与理论区域进行比较。然后生成真实计数的概率曲线。也许是蛮力，但看起来还不错。

_{(来源: 来自网站)}

对于这个问题有一些有效的解决方案，这就是所谓的功率图。这是一个非常复杂的数学问题，我不想一下子就解决。对于一个“简单”的解决方案，查找行扫描算法。这里的基本原理是将图形划分为条形，这样计算每个条形的面积就相对容易了。

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

The pixel-painting approach (as suggested by @Loadmaster) is superior to the mathematical solution in a variety of ways:

1. Implementation is 很多 simpler. The above problem can be solved in less than 100 lines of code, as this JSFiddle solution demonstrates (mostly because it’s conceptually much simpler, and has no edge cases or exceptions to deal with).
2. It adapts easily to more general problems. It works with any shape, regardless of morphology, as long as it’s renderable with 2D drawing libraries (i.e., “all of them!”) — circles, ellipses, splines, polygons, you name it. Heck, even bitmap images.
3. 与数学解的复杂度相比，像素绘制解的复杂度为 ~ O [ n ]。这意味着随着形状数量的增加，它将表现得更好。
4. 说到性能，你通常会得到免费的硬件加速，因为大多数现代的2D 库(我相信就像 HTML5的画布)会将渲染工作转移到图形加速器上。

像素绘制的一个缺点是解的精度有限。但是，可以根据情况的需要简单地将其渲染为更大或更小的画布。还要注意的是，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);

Ants Aasma's answer gave the basic idea, but I wanted to make it a little more concrete. Take a look at the five circles below and the way they've been decomposed.

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

识别这3种类型的点很容易。现在构造一个图形数据结构，其中的节点是蓝点和红点，内部为白色。对于每个圆，在圆的中间(蓝点)和它的每个交叉点(红点与白色内部)之间的边缘在它的边界上。

This decomposes the circle union into a set of polygons (shaded blue) and circular pie pieces (shaded green) that are pairwise disjoint and cover the original union (that is, a partition). Since each piece here is something that's easy to compute the area of, you can compute the area of the union by summing the pieces' areas.

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

如果我把 L和 M这样

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

所以沿逆时针方向积分，得到区域的 地区，沿顺时针方向积分，得到负的 地区。那么

(沿着逆时针方向的红色弧线集成 + 沿着顺时针方向的蓝色弧线集成)