计算圈数的细胞被包含在

假设我们有给定的n cirlces，其构建体的细胞次。给出每个圆的中点（x-y坐标）和半径。一个细胞的特点是它的弧线与该细胞结合。

对于每个圆弧，给出以下信息： 1.它所属的圆的中点 2.源点和目标点为x-y坐标，圆弧从哪里开始和结束。 3.弧线本身的中点也由它的x-y坐标给出。

对于Cell1我用黄色，蓝色和棕色给圆弧着色。另外，我试图指出图片上弧线的中点，目标和来源。

现在，我想用运行时间O（n²）来计算每个单元所包含的圆的数量。例如，单元格C1只包含在1个圆圈内，单元格C11在2和C5在3中。

我的想法在O（m）中计算，其中m：=弧的数目。我认为一般来说弧的数量可以超过n²。

任何帮助或想法将非常感激！提前致谢。

2014-12-01 XerXes

这是在网格上吗？每个“细胞”都有一个x-y点吗？每个给定的圆圈都有一个x-y点的中心和半径？您可以遍历圆形列表并计算单元格的x-y点是否在每个圆形在网格上所占的空间内 – 2014-12-01 19:42:24

“我想要计算它”的意思是什么？这是什么你想要计算？（例如，如果给出的单元格只是计算与所有圆心的距离，并且您会知道单元格在哪个圆圈中。） – Trilarion 2014-12-01 19:42:47

是的，每个圆都有一个以其x-y坐标给出的中点。单元格没有任何x-y坐标，但单元格的圆弧由其所属的圆弧给出，圆弧的原点和目标是圆弧的原点和目标。我想计算每个单元格所包含的圆的数量。 – XerXes 2014-12-01 19:45:25

我认为一般情况下弧的数量可以超过n²。

你为什么这么想？

任何一对圆最多相交两处。所以一个圆圈最多会被其他圆圈分割成最多2n - 2圆弧。由于有n圈，最多有2n² - 2n = O(n²)弧。

2014-12-01 20:35:30 btilly

我不明白'2n^2 - 2n = O（n）'。那不是O（n^2）吗？ – Chris 2014-12-01 20:43:01

@XerXes我的意思是说'O（n²）'。我再说一遍，你为什么认为它超过了它？特别是我刚才证明它不是？ – btilly 2014-12-01 21:11:20

不确定您是否误读谁留下了该评论。我假设对OP的意见，但我不是他们。 – Chris 2014-12-01 21:14:38

回答