math - n个圆的交集区域，每个圆的半径为'r'

Question

概率陈述：在（-）无穷到（+）无穷的图形上绘制“N”个相等半径的圆。求相交的总面积，即图形上被两个或多个圆覆盖的所有区域。

Answer 1

首先更正：这些不是圆圈。它们是椭圆（圆是椭圆的一种特殊情况，其中 a = b）。您可以计算两个椭圆的交集，因此给定 N 个椭圆，您需要检查每一对，因此整个操作为 O(n ² )（乘以任何交集操作）。

看看椭圆的相交和相交椭圆的面积。

编辑：圆的交点是一个更容易的问题，但遵循相同的原则。看看Intersection Of Two Circles和Circle-Circle Intersection。

Answer 2

最简单（不一定是最快或“最好”）的编码方式是找到包含所有圆圈的边界框，然后使用数值随机方法进行积分。

现在，通过聪明，您可能可以对圆圈进行分组并将它们分别装箱，即在多个边界框中工作。甚至可以准确处理某些特殊情况。

但是纯随机方法具有易于实现（但可能很慢）的优点。

仅当您乐于获得“近似”（但任意接近正确）答案时，这才可以接受。