优化几何算法[圆内区域内的点]

Question

这是来自编码评估。问题是这样的：

节点是 x-y 平面 (i, j) 上的点，其中 i,j 是整数。给定一个以

R

为半径的圆和一个具有左下坐标 (x1, y1) 和右上角坐标 (x2, y2) 的矩形网格，编写一个程序，返回网格内的节点数包含在圆内（或圆的周边）。

我写了这个程序：

(xl, yl)

逻辑是：循环给出矩形网格内的所有

def numPointsInCircle(x1, y1, x2, y2, xl, yl, R):
  num = 0
  for x in range(x1, x2 + 1):
    for y in range(y1, y2 + 1):
      if (x - xl) ** 2 + (y - yl) ** 2 <= R ** 2:
        num += 1
  return num

“节点”，对于每个节点，我们测试它们到圆心的距离是否大于半径。

我通过了 9/15 个测试用例，其余的由于超出时间限制而失败。如何优化以提高效率？

我尝试过的一些事情：

限制右上角的网格最多为圆的右上角，右下的网格最多为圆的右下角

当
• (x, y)
或
• (x - xl)

   单独超过 

  (y - yl) 时，

  提前突破条件
  

Answer 1

Mathworld页面

关于高斯圆问题）

对于坐标

R

处的水平线，有

Y

点直到圆周或矩形右边缘。因此，遍历

1 + min(width, floor(sqrt(R^2-Y^2)))

范围内的

Y

值并对有效点求和。0..min(R,height)