Ant*_*sma 96
找到外围的所有圆形交叉点(例如下图中的B,D,F,H).将它们与相应圆的中心连接在一起以形成多边形.圆的并集区域是多边形的面积+由连续交叉点和它们之间的圆心定义的圆切片的面积.你还需要考虑任何漏洞.
- 当中心有洞时会发生什么？ (16认同)
- 您需要从总数中减去孔的中心连接多边形,并将该多边形的圆切片添加到总数中. (3认同)
- 很好,但我想这将需要很多实现细节来处理所有特殊情况(在其他一个圆内,没有交叉点,孔,一个点接触...) (3认同)
- 是的,但是孔的边界也是(小)弧.我仍然认为这需要很多代码才能正常工作. (3认同)
- +1是一个非常好的视觉描述问题. (2认同)
Hig*_*ark 31
我确信有一个聪明的算法,但这是一个愚蠢的,以节省不得不寻找它;
- 在圆圈周围放置一个边界框;
- 在边界框内生成随机点;
- 弄清楚随机点是否在其中一个圆圈内;
- 通过一些简单的加法和除法来计算区域(proportion_of_points_inside*area_of_bounding_box).
当然这是愚蠢的,但是:
- 您可以根据需要获得准确的答案,只需生成更多积分;
- 它适用于任何可以计算内/外区别的形状;
- 它会很好地并行化,因此您可以使用所有核心.
- 蒙特卡罗(或任何随机化)方法没有任何内在错误,前提是它提供了所需的准确度并且在合理的时间内完成. (8认同)
- 你是对的,我为自己感到羞耻,但我有一个拥有12,000个核心的集群,我可以负担得起奢侈品.我无法弄清楚如何使优雅的数学解决方案扩展到许多处理器. (5认同)
- 这样可行,但像这样的Monte-Carlo方法,仅基于均匀采样,通常没有最佳的收敛速度. (2认同)
- 对不起,但即使我感谢您的努力,并认为您的解决方案"实际可用",我认为您的方法是非常错误的.这是一个问题而不是可以而且应该通过数学解决,而不是蛮力.在这样的问题上浪费能源和核心是浪费和奢侈. (2认同)
Tim*_*lds 17
蚂蚁Aasma的回答给出了基本的想法,但我想让它更具体一点.看看下面的五个圆圈以及它们被分解的方式.
- 蓝点是圆心.
- 红点是圆边界交叉点.
- 带有白色内部的红点是圆形边界交叉点,不包含在任何其他圆圈中.
识别这三种类型的点很容易.现在构建一个图形数据结构,其中节点是蓝点,红点是白色内部.对于每个圆,在其边界之间的圆形中间(蓝点)和每个交叉点(带有白色内部的红点)之间放置一条边.
这会将圆形并集分解为一组多边形(阴影蓝色)和圆形饼图(绿色阴影),它们成对不相交并覆盖原始联合(即分区).由于这里的每一块都是易于计算区域的东西,你可以通过对碎片区域求和来计算联合区域.
fa.*_*fa. 16
对于与前一个解决方案不同的解决方案,您可以使用四叉树生成具有任意精度的估计.
如果您可以判断方形是在内部还是外部或与形状相交,这也适用于任何形状联合.
每个单元格都具有以下状态之一:空,满,部分
该算法包括以低分辨率(例如标记为空的4个单元)从四边形"绘制"圆形.每个单元格是:
- 在至少一个圆圈内,然后将单元格标记为已满,
- 在所有圈子之外,将单元格标记为空,
- 否则将单元格标记为部分.
完成后,您可以计算区域的估计:完整的单元格给出下限,空单元格给出更高的界限,部分单元格给出最大区域误差.
如果错误对您来说太大,则优化部分单元格,直到获得正确的精度.
我认为这比执行许多特殊情况所需的几何方法更容易实现.
- 我的猜测**是,这也会比monte carlo内/外点算法更迅速地收敛. (3认同)
Leo*_*ick 12
我喜欢2个交叉圆的情况 - 这里是我如何使用相同方法的略微变化来处理更复杂的例子.
它可以更好地洞察大量半重叠圆的算法.
这里的区别在于我从连接中心开始(所以在圆心之间有一个顶点,而不是在圆相交的地方之间)我认为这可以让它更好地推广.
(在实践中,也许monte-carlo方法是值得的)
alt text http://secretGeek.net/image/triangles_1667310.png
如果您想要一个离散（而不是连续）答案，您可以执行类似于像素绘画算法的操作。
在网格上绘制圆圈，如果网格的每个单元格大部分包含在圆圈内（即，至少 50% 的面积位于其中一个圆圈内），则为网格的每个单元格着色。对整个网格（其中网格跨越圆圈覆盖的所有区域）执行此操作，然后计算网格中彩色单元格的数量。