如何根据坐标计算四叉树中对应节点的层级与尺寸

先对齐这套四叉树的固定规则，所有逻辑基于规则推导，适配任意根节点尺寸：

• 层级0为根节点，中心固定在(0,0)，根节点宽度可配置（示例值为16，最大支持4096及以上），覆盖范围为x、y坐标均在[-root_width/2, root_width/2)区间内
• 每向下递归一级，单个节点拆分为4个等大子节点，子节点宽度为父节点的1/2，节点间无重叠、无偏移
• 最大递归深度可配置（示例值为3，对应最小节点宽度为2）

核心逻辑 #

不要从根节点往下递归查找，从最深的最小节点开始往上层校验，逻辑最简单，不会出边界bug，性能也足够：

1. 第一步先做范围拦截：如果输入坐标的x或y绝对值大于等于根节点半宽，直接判定为非法地址，超出四叉树覆盖范围
2. 从最深层级开始，逐层向上校验：
   • 对当前校验层级，计算对应节点宽度node_width = 根宽度 / 2^当前层级，节点半宽half = node_width / 2
   • 合法节点的中心坐标一定满足：(x + half)能被node_width整除，且(y + half)能被node_width整除。只要满足这个条件，当前坐标就对应当前层级的节点中心，直接返回层级和节点宽度即可
   • 不满足条件就往上走一级（节点宽度翻倍），重复校验，直到校验完根节点层级
3. 如果从最深到根节点所有层级都不满足整除条件，说明坐标落在节点间隙，判定为非法地址

可直接复用的代码实现 #

def quadtree_locate(x: int, y: int, root_width: int, max_level: int):
    root_half = root_width // 2
    # 超出根节点覆盖范围直接返回非法
    if abs(x) >= root_half or abs(y) >= root_half:
        return None

    # 从最细粒度节点往根节点遍历
    for level in range(max_level, -1, -1):
        node_width = root_width // (2 ** level)
        half = node_width // 2
        if (x + half) % node_width == 0 and (y + half) % node_width == 0:
            return (level, node_width)
    
    # 所有层级都不匹配，落在节点间隙
    return None

参考示例校验（和给出的测试用例完全一致） #

测试参数统一用root_width=16，max_level=3：

• 输入(1,1)：层级3对应节点宽度2，半宽1，(1+1)%2=0、(1+1)%2=0，返回(3, 2)，匹配预期
• 输入(4,6)：从层级3到层级0逐次校验均不满足整除条件，返回None（非法地址），匹配预期
• 输入(-6,-2)：层级2对应节点宽度4，半宽2，(-6+2)%4=0、(-2+2)%4=0，返回(2, 4)，匹配预期

这个实现没有硬编码任何尺寸参数，根节点宽度不管是16还是4096，只要传入对应参数就能直接跑，时间复杂度和最大层级正相关，哪怕最大层级到20（对应根宽度1048576，最小节点宽度1）也只有20次循环，没有性能问题。

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