我最近遇到了一个问题,我有四个圆(中点和半径),并且必须计算这些圆的并集的面积。
示例图像:
对于两个圆圈来说,这很容易,
我可以只计算不在三角形内的每个圆的面积,然后计算三角形的面积。
但是,当有两个以上的圆时,有没有一个聪明的算法可以使用呢?
发布于 2009-11-03 22:47:10
找到外周上的所有圆交点(例如,下图中的B、D、F、H)。将它们与相应圆的中心连接在一起,形成一个多边形。圆并集的面积是多边形的面积+由连续交点和它们之间的圆中心定义的圆切片的面积。您还需要考虑任何漏洞。
发布于 2009-11-04 00:20:41
如果你想要一个离散的(而不是连续的)答案,你可以做一些类似于像素绘制算法的事情。
在网格上绘制圆圈,如果网格的每个单元格主要包含在一个圆圈内(即至少50%的面积在其中一个圆圈内),则给每个单元格上色。对整个网格执行此操作(其中网格跨越圆覆盖的所有区域),然后计算网格中彩色单元格的数量。
发布于 2010-01-21 23:57:43
使用所谓的电源图可以有效地解决这个问题。这真的是很繁重的数学运算,我不想马上解决。要获得一个“简单”的解决方案,请查看行扫描算法。这里的基本原则是,您将图形划分为条带,其中计算每个条带中的面积相对容易。
因此,在包含所有没有擦掉的圆的图形上,在每个位置绘制一条水平线,该位置要么是圆的顶部,要么是圆的底部,要么是两个圆的交点。请注意,在这些条带中,您需要计算的所有面积看起来都是一样的:一个两边被圆形线段替换的“梯形”。因此,如果你能计算出这样的形状,你只需对所有单独的形状进行计算,并将它们相加。这种简单方法的复杂度是O(N^3),其中N是图中的圆圈数。通过一些巧妙的数据结构使用,您可以将这种行扫描方法改进为O(N^2 * log(N)),但是除非确实需要,否则可能不值得这么麻烦。
https://stackoverflow.com/questions/1667310
复制相似问题