重叠圆圈的组合区域
我最近遇到了一个问题，我有四个圆圈（中点和半径），不得不计算这些圆圈的面积。
示例图像：
对于两个圈子来说很简单，
我可以计算不在三angular形内的每个圆圈区域的分数，然后计算三angular形的面积。
但是当有两个以上的圆圈时，我可以使用一个聪明的algorithm吗？
find外围的所有圆形交点（例如下图中的B，D，F，H）。 将它们与相应圆的中心连接在一起形成一个多边形。 圆的面积是多边形的面积+由连续交点定义的圆片的面积和它们之间的圆心。 你还需要考虑到任何漏洞。
我确定有一个聪明的algorithm，但是这是一个愚蠢的algorithm，不必去寻找它。
- 在圈子周围放一个边框;
- 在边界框内生成随机点;
- 确定随机点是否在一个圆圈内;
- 通过一些简单的加法和除法来计算面积（proportion_of_points_inside * area_of_bounding_box）。
当然是愚蠢的，但是：
- 你可以得到准确的答案，只要你想要的，只是产生更多的点;
- 它将适用于任何形状，你可以计算内部/外部的区别;
- 它会平行美丽，所以你可以使用所有的核心。
对于与前一个解决scheme不同的解决scheme，您可以使用四叉树以任意精度生成估计。
这也适用于任何形状的联合，如果你可以知道方形是内部还是外部或与形状相交。
每个单元格都有一个状态：空，全，部分
该algorithm包括从低分辨率（例如标记为空的4个单元）开始在四叉树中“绘制”圆圈。 每个单元格是：
- 至less在一个圆内，然后标记单元格已满，
- 在所有的圈外，将单元格标记为空，
- 否则将单元格标记为部分。
完成后，可以计算区域的估计值：全部单元给出下限，空单元给出更高的界限，局部单元给出最大面积误差。
如果错误对您来说太大，您可以细化部分单元格，直到获得正确的精度。
我认为这比实现许多特殊情况所需的几何方法更容易实现。
我喜欢2个相交的圆的情况下的方法 – 这是我如何使用相同的方法稍微变化的更复杂的例子。
它可能会更好的洞察到更广泛的半重叠圆的algorithm的推广。
这里的区别在于我从链接中心开始（所以在圆心之间有一个顶点，而不是在圆之间相交的地方），我认为这可以让它更好地概括。
（实际上，也许monte-carlo方法是值得的）
antAasma的回答给出了基本的想法，但是我想让它更具体。 看看下面的五个圆圈和他们被分解的方式。
- 蓝色圆点是圆心。
- 红点是圆形边界交点。
- 白色内部的红点是圆圈边界的交点， 不包含在其他任何圆圈中 。
识别这3种types的点很容易。 现在构build一个graphics数据结构，其中节点是蓝色的点，白色的内部是红色的点。 对于每个圆形，在圆的中间（蓝色圆点）与其交点（白色内部的红色圆点）之间留出一条边。
这将圆形联合分解成一对多边形（阴影蓝色）和圆形饼形件（阴影绿色），它们是成对分离的，并覆盖原始联合（即分区）。 由于这里的每个部分都是容易计算面积的东西，因此可以通过对这些部分的面积求和来计算联合的面积。
嗯，非常有趣的问题。 我的做法可能是以下几点：
- 找出一个方法来计算出任意数量的圆之间的交点，也就是说，如果我有三个圆，我需要能够计算出这些圆之间的交集是什么。 “蒙特卡罗”方法将是一个近似的好方法（ http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ）。
- 消除完全包含在另一个较大的圆圈（查看半径和两个圆的中心之间的距离的模数）的任何圆圈，我不认为是强制性的。
- select2个圆圈（称为A和B），并使用以下公式计算总面积：
（对于任何形状都是如此，无论是圆形还是其他形状）
area(A∪B) = area(A) + area(B) - area(A∩B) 如果A ∪ B意味着联盟B和A ∩ B意味着交叉B（你可以从第一步开始工作。
- 现在继续添加圆圈，并继续计算添加的区域作为圆圈的区域和圆圈之间的交点区域的加减。 例如对于3个圆圈（称为额外的圆C），我们使用这个公式计算出面积：
（这与上面A已经被A∪Breplace的A∪B ）
area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)
我们刚刚制定的area(A∪B)和area((A∪B)∩C)可以find：
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)
在那里你可以从上面find区域（A∩B∩C）。
棘手的一点是最后一步 – 越多的圈子被添加越复杂。 我相信有一个有限联合的交叉点的区域的扩大，或者你也许可以recursion地解决这个问题。
另外，在使用蒙特卡洛近似方法的区域方面，我认为可以减less任意数量的圆与四个圆的交点，这可以精确地计算出来（不知道该怎么做然而）。
可能有更好的方法做这个顺便说一句 – 复杂性显着增加（可能是指数级的，但我不知道）每增加一个额外的圆。
如果你想要一个离散的（而不是一个连续的）答案，你可以做一些像素绘画algorithm。
在网格上绘制圆，然后为网格中的每个单元格添加颜色（如果其大部分包含在圆圈内）（即其面积的至less50％位于圆圈内）。 对整个网格（网格跨越圆圈覆盖的所有区域）执行此操作，然后计算网格中的彩色单元格的数量。
我一直在研究一个模拟重叠星场的问题，试图从密集的实际磁盘区域估计真正的恒星数量，在那里较大的明亮的恒星可以掩盖较暗的恒星。 我也曾经希望能够通过严格的forms分析来做到这一点，但无法find一个任务的algorithm。 我通过在蓝色背景上生成星号字段来解决这个问题，因为绿色圆盘的直径是由概率algorithm确定的。 一个简单的例程可以将它们配对，看看是否有重叠（将星星对变成黄色）; 那么颜色的像素计数产生观察区域以与理论区域进行比较。 这然后生成真实计数的概率曲线。 暴力也许，但它似乎工作确定。
http://www.2from.comhttp://img.dovov.comsimulated_star_field.gif
这个问题有效的解决scheme使用所谓的功率图。 这个math真的很重，不是我想要的。 对于一个“简单”的解决scheme，查找线扫描algorithm。 这里的基本原则是，你把这个数字分成小条，在那里计算每个小条的面积比较容易。
因此，在包含所有没有任何东西的圆圈的graphics上，在每个圆圈的顶部，圆圈底部或2个圆圈的交点处画一条水平线。 请注意，在这些条的内部，需要计算的所有区域看起来都是一样的：一个“梯形”，两边被圆形段代替。 所以，如果你可以计算出如何计算这种形状，只需要对所有的形状进行计算并将它们加在一起即可。 这种天真的方法的复杂性是O（N ^ 3），其中N是图中圆的数目。 有了一些聪明的数据结构的使用，你可以将这种行扫描方法改进为O（N ^ 2 * log（N）），但是除非你真的需要，否则可能不值得麻烦。
我发现这个链接可能是有用的。 虽然似乎没有确定的答案。 Google回答 。 另外三个圈子的参考是Haruki的定理 。 那边还有一张纸。
根据你想要解决什么问题，可能足以得到一个上限和下限。 上限很容易，只是所有圈子的总和。 对于一个下界，你可以select一个半径，使得没有一个圆重叠。 为了更好地find每个圆的最大半径（直到实际半径），使其不重叠。 当P_a是圆A的中心，P_b是圆B的中心，r_a是A的半径时，去除任何完全重叠的圆（所有这些圆满足| P_a-P_b | <= r_a）也应该是非常简单的），并且这个上限和下限都变好了。 你也可以得到一个更好的上界，如果你在任意对上使用你的配对公式，而不是所有的圆的总和。 可能有一个很好的方法来select“最好的”对（导致最小总面积的对）。
给定一个上限和下限，你可能会更好地调整蒙特卡洛方法，但没有什么具体的想法。 另一个选项（再次取决于您的应用程序）是光栅化圆圈和计数像素。 基本上是具有固定分布的蒙特卡罗方法。
下面是一个在实践中应该很容易实现的algorithm，可以调整以产生任意小的错误：
- 通过以同一点为中心的正多边形来近似每个圆
- 计算近似圆的并集的多边形
- 计算合并的多边形的面积
步骤2和步骤3可以使用标准的，易于查找的计算几何algorithm来执行。
显然，每个逼近多边形的边数越多，答案越接近。 你可以近似使用内切和外接的多边形来获得确切答案的界限。
像素绘画方法（如@Loadmaster所build议的）在多种方面优于math解决scheme：
- 实现要简单得多。 上述问题可以用不到100行的代码解决 ， 因为这个JSFiddle解决scheme （主要是因为它在概念上更简单，没有边缘情况或exception处理）。
- 它很容易适应更一般的问题。 它可以与任何形状一起工作，不pipe形态如何，只要它可以用二维绘图库（即“所有这些”）进行渲染，即圆形，椭圆形，样条线，多边形等等。 哎呀，甚至位图图像。
- 像素绘画解决scheme的复杂性是〜O [n]，与math解决scheme的〜O [n * n]相比较。 这意味着随着形状数量的增加，它会performance得更好。
- 说到性能，你会经常得到免费的硬件加速，因为大多数现代化的二维库（比如HTML5的canvas，我相信）将把渲染工作交给graphics加速器。
像素绘画的一个缺点是解决scheme的有限精度。 但是，只要根据情况需要渲染较大或较小的canvas，就可以调整。 还要注意，2D渲染代码中的抗锯齿 （通常默认打开）会产生好于像素级的精度。 因此，例如，将一个100×100的graphics渲染成相同尺寸的canvas，我认为应该在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);
;){kind=link}