blocks|key|1202112|text|我找到了这个可能有用的链接。然而，似乎没有一个明确的答案。Google+answers。三个圆的另一个引用是Haruki's+theorem。那里也有一篇论文。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1202113|entityMap|0|LINK|mutability|MUTABLE|url|http://answers.google.com/answers/threadview?id=480288|1|http://math.kennesaw.edu/~mdevilli/haruki.html^0|T|E|0|1I|G|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

I found this link which may be useful. There does not seem to be a definitive answer though.
<a href="http://answers.google.com/answers/threadview?id=480288" rel="nofollow noreferrer">Google answers</a>. Another reference for three circles is <a href="http://math.kennesaw.edu/~mdevilli/haruki.html" rel="nofollow noreferrer">Haruki's theorem</a>. There is a paper there as well.

blocks|key|1417287|text|找到外周上的所有圆交点(例如，下图中的B、D、F、H)。将它们与相应圆的中心连接在一起，形成一个多边形。圆并集的面积是多边形的面积%2B由连续交点和它们之间的圆中心定义的圆切片的面积。您还需要考虑任何漏洞。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1417288|​|1417289|📷|atomic|offset|length|1417290|1417291|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/bd6f4b66be84056aba54e0b02d78c93d.png|imageAlt^0|0|0|0|1|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@$G|V|H|W|1|X]]|A|$]]|$1|I|3|C|5|6|7|Y|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|Q|R|-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.

<img src="https://i.stack.imgur.com/VTW7e.png" alt="circle overlap">

blocks|key|1417350|text|根据你试图解决的问题，得到一个上限和下限就足够了。上界很简单，就是所有圆圈的总和。对于下限，您可以选择一个半径，使所有圆都不重叠。为了更好地做到这一点，找到每个圆的最大半径(直到实际半径)，这样它就不会重叠。删除任何完全重叠的圆(所有这样的圆都满足%7CP_a+-+P_b%7C+<=+r_a)也应该是相当简单的，其中P_a是圆A的中心，P_b是圆B的中心，r_a是A的半径)，这既改善了上界也改善了下界。如果你对任意对使用配对公式，而不仅仅是所有圆的总和，你也可以得到更好的上限。可能有一个很好的方法来挑选“最佳”配对(导致总面积最小的配对。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1417351|给定上限和下限，您可能能够更好地调整蒙特卡洛方法，但没有具体的考虑。另一种选择(同样取决于您的应用程序)是光栅化圆形并计算像素。它基本上是具有固定分布的蒙特卡罗方法。|1417352|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Depending on what problem you are trying to solve it could be sufficient to get an upper and lower bound. An upper bound is easy, just the sum of all the circles. For a lower bound you can pick a single radius such that none of the circles overlap. To better that find the largest radius (up to the actual radius) for each circle so that it doesn't overlap. It should also be pretty trivial to remove any completely overlapped circles (All such circles satisfy |P_a - P_b| &lt;= r_a) where P_a is the center of circle A, P_b is the center of circle B, and r_a is the radius of A) and this betters both the upper and lower bound. You could also get a better Upper bound if you use your pair formula on arbitrary pairs instead of just the sum of all the circles. There might be a good way to pick the "best" pairs (the pairs that result in the minimal total area.

Given an upper and lower bound you might be able to better tune a Monte-carlo approach, but nothing specific comes to mind. Another option (again depending on your application) is to rasterize the circles and count pixels. It is basically the Monte-carlo approach with a fixed distribution.

blocks|key|1417418|text|如果你想要一个离散的(而不是连续的)答案，你可以做一些类似于像素绘制算法的事情。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1417419|在网格上绘制圆圈，如果网格的每个单元格主要包含在一个圆圈内(即至少50%25的面积在其中一个圆圈内)，则给每个单元格上色。对整个网格执行此操作(其中网格跨越圆覆盖的所有区域)，然后计算网格中彩色单元格的数量。|1417420|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

If you want a discrete (as opposed to a continuous) answer, you could do something similar to a pixel painting algorithm.

Draw the circles on a grid, and then color each cell of the grid if it's mostly contained within a cirle (i.e., at least 50% of its area is inside one of the circles). Do this for the entire grid (where the grid spans all of the area covered by the circles), then count the number of colored cells in the grid.

blocks|key|1202396|text|使用所谓的电源图可以有效地解决这个问题。这真的是很繁重的数学运算，我不想马上解决。要获得一个“简单”的解决方案，请查看行扫描算法。这里的基本原则是，您将图形划分为条带，其中计算每个条带中的面积相对容易。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1202397|因此，在包含所有没有擦掉的圆的图形上，在每个位置绘制一条水平线，该位置要么是圆的顶部，要么是圆的底部，要么是两个圆的交点。请注意，在这些条带中，您需要计算的所有面积看起来都是一样的:一个两边被圆形线段替换的“梯形”。因此，如果你能计算出这样的形状，你只需对所有单独的形状进行计算，并将它们相加。这种简单方法的复杂度是O(N%5E3)，其中N是图中的圆圈数。通过一些巧妙的数据结构使用，您可以将这种行扫描方法改进为O(N%5E2+*+log(N))，但是除非确实需要，否则可能不值得这么麻烦。|1202398|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

There are efficient solutions to this problem using what are known as power diagrams. This is really heavy math though and not something that I would want to tackle offhand. For an "easy" solution, look up line-sweep algorithms. The basic principle here is that that you divide the figure up into strips, where calculating the area in each strip is relatively easy.

So, on the figure containing all of the circles with nothing rubbed out, draw a horizontal line at each position which is either the top of a circle, the bottom of a circle or the intersection of 2 circles. Notice that inside these strips, all of the areas you need to calculate look the same: a "trapezium" with two sides replaced by circular segments. So if you can work out how to calculate such a shape, you just do it for all the individual shapes and add them together. The complexity of this naive approach is O(N^3), where N is the number of circles in the figure. With some clever data structure use, you could improve this line-sweep method to O(N^2 * log(N)), but unless you really need to, it's probably not worth the trouble.

I recently came across a problem where I had four circles (midpoints and radius) and had to calculate the area of the union of these circles.

Example image:

<img src="https://i.stack.imgur.com/LxEIF.png" />

For two circles it's quite easy,

<img src="https://i.stack.imgur.com/L9WCg.png" />

I can just calculate the fraction of the each circles area that is not within the triangles and then calculate the area of the triangles.

But is there a clever algorithm I can use when there is more than two circles?

Combined area of overlapping circles

数据结构

我最近遇到了一个问题，我有四个圆(中点和半径)，并且必须计算这些圆的并集的面积。示例图像：​​对于两个圆圈来说，这很容易，​​我可以只计算不在三角形内的每个圆的面积，然后计算三角形的面积。但是，当有两个以上的圆时，有没有一个聪明的算法可以使用呢？

问重叠圆的组合面积
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问重叠圆的组合面积EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问重叠圆的组合面积
EN