Python递归四叉树/空间细分算法逻辑异常排查

你的代码共有4处核心逻辑错误，是递归两层后结果偏差的直接原因：

• Pygame绘制矩形参数错误：pygame.draw.rect要求传入的矩形元组格式为(左上角x, 左上角y, 矩形宽度, 矩形高度)，你传入的是(x,y,x2,y2)，误将右边界x2作为宽度、下边界y2作为高度传入。初始调用和第二层递归时因为左/上边界为0，宽高值刚好和右/下边界数值相等，所以视觉上表现正常；从第三层递归开始，左/上边界不再为0，传入的宽高值远大于实际需要的尺寸，绘制的矩形完全错位。
• 绘制顺序不符合需求：需求是仅当区域内点数超过阈值时才绘制边框、再递归细分，但当前代码进入函数就直接绘制矩形，会导致大量点数不达标的空白区域也被画上边框。
• 点范围判断存在缺陷：使用in range(x,x2)判断点是否在区域内有两个问题：一是Python的range为左闭右开区间，坐标刚好等于x2、y2的点会被漏算；二是递归时用int()截断坐标，会导致相邻子象限之间出现缝隙，部分点会被漏算或重复统计。
• 变量命名冲突：递归深度参数命名为max，和Python内置的max()函数重名，存在潜在逻辑风险。

修正后可直接运行的代码 #

import pygame
import random

# 初始化和测试数据生成部分和你原有逻辑一致
pygame.init()
screen = pygame.display.set_mode((1000, 1000))
xlist = []
ylist = []
for i in range(5):
    xlist.append(random.randint(0,1000))
    ylist.append(random.randint(0,1000))

def quadtree_recursion(x, x2, y, y2, depth):
    # 先统计当前区域内的点总数
    total_points = 0
    for px, py in zip(xlist, ylist):
        # 直接做数值区间判断，兼容浮点数、避免range的边界漏算问题
        if x <= px <= x2 and y <= py <= y2:
            total_points += 1

    # 点数未达阈值、或达到最大递归深度时终止递归
    if total_points <= 3 or depth >= 30:
        return

    # 仅当点数达标时绘制当前区域边框，传入正确的宽高参数
    rect_w = x2 - x
    rect_h = y2 - y
    pygame.draw.rect(screen, (0,255,255), (x, y, rect_w, rect_h), 1)

    next_depth = depth + 1
    mid_x = (x + x2) / 2
    mid_y = (y + y2) / 2
    # 按中点分割四个子象限递归，避免整数截断产生的缝隙
    quadtree_recursion(x, mid_x, y, mid_y, next_depth)    # 左上
    quadtree_recursion(mid_x, x2, y, mid_y, next_depth)   # 右上
    quadtree_recursion(x, mid_x, mid_y, y2, next_depth)   # 左下
    quadtree_recursion(mid_x, x2, mid_y, y2, next_depth)  # 右下

# 启动递归
quadtree_recursion(0, 1000, 0, 1000, 0)

# 常规pygame渲染循环
running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
    pygame.display.flip()
pygame.quit()

修正说明 #

• 调整了逻辑顺序，先统计点数，满足阈值条件才绘制边框、触发递归
• 矩形绘制时用右边界-左边界算宽度、下边界-上边界算高度，完全匹配pygame的参数要求
• 替换range判断为直接数值比较，分割子区域时用中点坐标而非整数截断，解决点漏算、区域错位问题
• 将原参数名max改为depth，避免和内置函数冲突

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