如何计算圆伸出无限矩形的面积及解决代码重复计数问题

问题描述 #

现有场景为矩形从(0,0)向正无穷方向无限延伸，需计算圆心位于(3,2)、半径7的圆伸出该矩形的面积，并将方法推广至任意半径的圆与任意尺寸的矩形。

实际编程中遇到核心问题：计算多个不同圆在矩形内的占比时，当圆覆盖矩形角落，现有代码会重复计数外伸区域。例如圆心位于(0,0)时，代码会重复计算x轴左侧和y轴下方的外伸弓形面积，错误判定整个圆都在矩形外。无角落覆盖情况时，可通过计算圆与矩形各边缘的距离，结合几何公式计算外伸区域面积，但角落覆盖时的重叠区域重复统计问题始终无法解决。

现有问题代码 #

以下代码通过累加垂直于坐标轴的弓形面积得到外伸面积，但角落重叠区域会被重复计数：
参数说明：

• xbounds：矩形x轴范围元组(low, high)，实际场景中low=0，high为极大值
• ybounds：矩形y轴范围元组(low, high)
• range：圆的半径
• pos：复数类型，代表圆心坐标，实部为x坐标，虚部为y坐标

r2 = range * range
outarea = 0
        
if (b := -pos.real + range + xbounds[0]) > 0:
    theta = 2 * acos(1 - b / range)
    outarea = 0.5 * r2 * (theta - sin(theta))  # 此处应为累加，原代码赋值逻辑错误
        
if (b := pos.real + range - xbounds[1]) > 0:
    theta = 2 * acos(1 - b / range)
    outarea += 0.5 * r2 * (theta - sin(theta))
        
if (b := -pos.imag + range + ybounds[0]) > 0:
    theta = 2 * acos(1 - b / range)
    outarea += 0.5 * r2 * (theta - sin(theta))
        
if (b := pos.imag + range - ybounds[1]) > 0:
    theta = 2 * acos(1 - b / range)
    outarea += 0.5 * r2 * (theta - sin(theta))

解决思路与修正代码 #

问题根源是角落区域被两个方向的弓形面积重复计算，需用容斥原理修正：先累加四个边的外伸弓形面积，再减去四个角落中重复统计的重叠区域（每个角落的外伸区域被两个边的弓形各算一次，多算了一次，需减去）。

具体步骤 #

1. 计算四个边向外的弓形面积（修正原代码第一个赋值为累加逻辑）
2. 检查四个角落（左下、左上、右下、右上），判断圆是否在该角落有外伸区域，计算该区域面积并从总外伸面积中减去

修正后代码 #

import math

def calculate_outside_area(xbounds, ybounds, radius, pos):
    r = radius
    r2 = r * r
    outarea = 0
    x_low, x_high = xbounds
    y_low, y_high = ybounds
    cx, cy = pos.real, pos.imag

    # 计算四个边的外伸弓形面积
    # 左边界外伸
    b_left = -cx + r + x_low
    if b_left > 0:
        theta = 2 * math.acos(1 - b_left / r)
        outarea += 0.5 * r2 * (theta - math.sin(theta))
    # 右边界外伸
    b_right = cx + r - x_high
    if b_right > 0:
        theta = 2 * math.acos(1 - b_right / r)
        outarea += 0.5 * r2 * (theta - math.sin(theta))
    # 下边界外伸
    b_bottom = -cy + r + y_low
    if b_bottom > 0:
        theta = 2 * math.acos(1 - b_bottom / r)
        outarea += 0.5 * r2 * (theta - math.sin(theta))
    # 上边界外伸
    b_top = cy + r - y_high
    if b_top > 0:
        theta = 2 * math.acos(1 - b_top / r)
        outarea += 0.5 * r2 * (theta - math.sin(theta))

    # 减去四个角落重复计算的区域
    # 左下角：x < x_low 且 y < y_low
    if cx < x_low and cy < y_low:
        dx = x_low - cx
        dy = y_low - cy
        if dx*dx + dy*dy <= r2:
            angle = math.atan2(dy, dx)
            sector_angle = math.pi/2 - angle
            sector_area = 0.5 * r2 * sector_angle
            triangle_area = 0.5 * dx * dy
            corner_area = sector_area - triangle_area
            outarea -= corner_area
    # 左上角：x < x_low 且 y > y_high
    if cx < x_low and cy > y_high:
        dx = x_low - cx
        dy = cy - y_high
        if dx*dx + dy*dy <= r2:
            angle = math.atan2(dy, dx)
            sector_angle = angle - math.pi/2
            sector_area = 0.5 * r2 * sector_angle
            triangle_area = 0.5 * dx * dy
            corner_area = sector_area - triangle_area
            outarea -= corner_area
    # 右下角：x > x_high 且 y < y_low
    if cx > x_high and cy < y_low:
        dx = cx - x_high
        dy = y_low - cy
        if dx*dx + dy*dy <= r2:
            angle = math.atan2(dy, dx)
            sector_angle = math.pi/2 + angle
            sector_area = 0.5 * r2 * sector_angle
            triangle_area = 0.5 * dx * dy
            corner_area = sector_area - triangle_area
            outarea -= corner_area
    # 右上角：x > x_high 且 y > y_high
    if cx > x_high and cy > y_high:
        dx = cx - x_high
        dy = cy - y_high
        if dx*dx + dy*dy <= r2:
            angle = math.atan2(dy, dx)
            sector_angle = math.pi - angle
            sector_area = 0.5 * r2 * sector_angle
            triangle_area = 0.5 * dx * dy
            corner_area = sector_area - triangle_area
            outarea -= corner_area

    return outarea

# 示例：题目中的场景
xbounds = (0, float('inf'))
ybounds = (0, float('inf'))
radius = 7
pos = complex(3, 2)
print(calculate_outside_area(xbounds, ybounds, radius, pos))

代码说明 #

• 先计算四个边的外伸弓形面积，修正原代码第一个边的赋值错误（改为+=）
• 对每个角落，先判断圆心是否在角落外侧，且角落顶点在圆内（即圆覆盖该角落），然后计算该角落的外伸区域面积——这部分区域被两个边的弓形各计算了一次，所以需要从总外伸面积中减去一次
• 角落区域面积通过扇形面积减去直角三角形面积计算，其中扇形角度根据圆心与角落顶点的相对位置推导

推广到任意矩形与圆 #

上述代码适用于任意尺寸的矩形（包括从(0,0)延伸到正无穷的半无限矩形）和任意半径的圆：

• 对于半无限矩形（如x_high为无穷大），右边界的外伸判断b_right = cx + r - x_high会小于等于0，不会计入外伸面积，自动适配场景
• 对于有限矩形，只需传入对应的xbounds和ybounds即可

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