优化几何算法：统计矩形区域内圆内整数节点数量

问题背景 #

节点是x-y平面上坐标(i,j)为整数的点。给定一个圆心为(xl, yl)、半径为R的圆，以及一个左下角坐标为(x1, y1)、右上角坐标为(x2, y2)的矩形网格，编写程序返回矩形网格内位于圆内（或圆周上）的节点数量。

原实现代码：

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测试用例，但剩余用例因超时失败。已尝试缩小遍历范围到圆边界内、提前终止单个轴超出半径的循环，但未解决超时问题。

优化方案 #

1. 精准缩小遍历范围 #

计算x的有效区间：x_start = max(x1, xl - R)，x_end = min(x2, xl + R)。若x_start > x_end，直接返回0，避免无效循环。同理y的范围后续通过数学计算直接推导，无需提前遍历。

2. 用数学计算替代内层循环 #

对每个有效x：

• 计算dx = x - xl，若dx*dx > R*R，直接跳过该x（无论y取何值都不可能在圆内）
• 计算剩余允许的y方向平方值：remaining = R*R - dx*dx
• 用整数平方根计算y的最大偏移量：y_offset = int(math.isqrt(remaining))（避免浮点精度问题）
• 推导y的理论范围[yl - y_offset, yl + y_offset]，再与矩形的y区间[y1, y2]取交集，得到实际有效y的范围[actual_y_low, actual_y_high]
• 若该范围有效，直接累加节点数：actual_y_high - actual_y_low + 1，无需遍历每个y

3. 预计算常量减少重复运算 #

提前计算R_squared = R*R，避免每次判断都重复计算，减少冗余乘法操作。

优化后代码示例 #

import math

def numPointsInCircle(x1, y1, x2, y2, xl, yl, R):
    num = 0
    R_squared = R * R
    x_start = max(x1, xl - R)
    x_end = min(x2, xl + R)
    
    if x_start > x_end:
        return 0
    
    for x in range(x_start, x_end + 1):
        dx = x - xl
        dx_squared = dx * dx
        if dx_squared > R_squared:
            continue
        remaining = R_squared - dx_squared
        y_offset = math.isqrt(remaining)  # Python 3.8+ 提供的整数平方根函数
        y_low = yl - y_offset
        y_high = yl + y_offset
        # 与矩形y范围取交集
        actual_y_low = max(y_low, y1)
        actual_y_high = min(y_high, y2)
        if actual_y_low <= actual_y_high:
            num += actual_y_high - actual_y_low + 1
    return num

关键优化说明 #

• 使用math.isqrt：返回非负整数的整数平方根，避免浮点运算的精度误差，运算速度也优于浮点平方根计算。
• 消除内层循环：时间复杂度从O((x2-x1)*(y2-y1))降至O(x_end - x_start)，在大尺寸矩形场景下效率提升显著。
• 提前过滤无效x：减少不必要的计算分支，进一步降低运算量。

内容的提问来源于stack exchange，提问作者user129393192