Prob声明: 在从( - )无穷远到(+)infinity的图形上画出'N'个相等的半径圆。找到所有交点的总面积Ie图上由两个或更多圆圈覆盖的区域。每个半径为r的n个圆的交点面积
2
A
回答
2
首先是校正:这些不是圆圈。它们是椭圆(圆形是一个椭圆的特例,其中a = b)。您可以计算两个椭圆的交点,因此给定N个椭圆需要检查每对,因此整个操作为O(乘以任何交点操作)。
看看Intersection of Ellipses和The Area of Intersecting Ellipses。
编辑:圆圈是一个更容易的问题,但遵循相同的原则。看看Intersection Of Two Circles和Circle-Circle Intersection。
1
最简单的(不一定是最快或最好的)代码的方法是找到包含所有圆的边界框,然后使用数值随机方法进行整合。
现在,通过聪明,你可以分组圈并将它们分开包装,即在多个边界框中工作。甚至完全处理某些特殊情况。
但纯粹的随机方法具有容易实现(但可能很慢)的美感。
这只有在您有一个“近似”(但任意接近正确)的答案时才可以接受。
+0
如果粗糙或适度的精度是可以接受的,那就好了。 *绝对*想要检测重叠组并围绕每个组绘制边框,否则可能会产生疯狂的空白数量。 – dmckee 2010-02-14 03:39:31
这个问题的编程部分是?听起来像简单的数学给我。你在做什么语言? – 2010-02-07 06:21:23
如果上面的链接不起作用,那么请参考: http://i.imagehost.org/0772/circles.png – avi 2010-02-07 06:21:53
是的,它更多的是数学。我正在做C – avi 2010-02-07 06:23:15