如何为存储R²中点的四叉树定义矩形边界条件

一、修正半开区间划分，覆盖所有边界点 #

不用放弃子集不相交的数学要求，调整半开区间的划分规则就能完整覆盖闭矩形[-l,l]×[-l,l]内的所有点：
假设节点覆盖区域为[x_min, x_max] × [y_min, y_max]，中心坐标为cx=(x_min+x_max)/2、cy=(y_min+y_max)/2，四个象限的半开区间可定义为：

• 西北象限：[x_min, cx) × [cy, y_max]
• 东北象限：[cx, x_max] × [cy, y_max]
• 西南象限：[x_min, cx) × [y_min, cy)
• 东南象限：[cx, x_max] × [y_min, cy)

这种划分逻辑下：

• 所有落在垂直中线x=cx的点，统一归属于东北/东南象限
• 所有落在水平中线y=cy的点，统一归属于西北/东北象限
• 初始闭矩形的东边界x=l、南边界y=-l的点，会被对应象限的闭区间端点包含，不会出现丢失，同时每个点仅属于一个象限，无归属歧义。

二、退而求其次：闭区间+固定优先归属规则 #

如果觉得半开区间的逻辑容易混淆，也可以放弃子集不相交的严格要求，采用闭区间划分，同时给边界点设定明确的优先归属顺序，确保每个边界点只存入一个节点：

• 设定固定的象限检查顺序，比如东北→西北→东南→西南，当点落在边界上时，存入第一个满足闭区间判断的象限
• 以C#为例，实现代码示例：

// 当前节点中心cx、cy，边长s
private bool IsInNortheast(double x, double y) => x >= cx && y >= cy;
private bool IsInNorthwest(double x, double y) => x <= cx && y >= cy;
private bool IsInSoutheast(double x, double y) => x >= cx && y <= cy;
private bool IsInSouthwest(double x, double y) => x <= cx && y <= cy;

public void Insert(double x, double y)
{
    if (IsInNortheast(x, y))
        northeastNode?.Insert(x, y);
    else if (IsInNorthwest(x, y))
        northwestNode?.Insert(x, y);
    else if (IsInSoutheast(x, y))
        southeastNode?.Insert(x, y);
    else
        southwestNode?.Insert(x, y);
}

这种方式代码实现更直观，唯一需要注意的是严格遵循设定的优先顺序，避免边界点重复存储。

三、浮点数精度处理注意事项 #

不管采用哪种方案，在C#或C++中处理浮点数坐标时，要避免直接用==判断点是否落在中线上，建议引入极小的精度阈值（如1e-9）来判断近似相等，防止因浮点数精度误差导致点被误判：

• C#示例：Math.Abs(x - cx) < 1e-9
• C++示例：fabs(x - cx) < 1e-9

内容的提问来源于stack exchange，提问作者Tacet.Discipulus