核心概述：二维 KD 树对点集做递归空间划分，支持单点最近邻查询（可扩展到三维），构建 O(n log n)、查询期望 O(log n)。
Description: KD-tree (2d, can be extended to 3d) Status: Tested on excellentengineers
展开阐述：
-
定义与背景
- KD 树（k-d tree）是一种对 k 维点集进行二叉空间划分（BSP）的数据结构，常用于最近邻、范围查询与加速碰撞/光线等几何检索。
- 本实现面向二维，接口与节点定义可自然扩展到三维（k=3）。
-
接口/数据结构（据实现）
- 结构体 Node：
- pt：节点存储的点 P。
- 边界矩形 bbox = (x0, x1, y0, y1)：覆盖该节点及其子树所有点的最小轴对齐矩形。
- 子节点 first / second：按某一维分割所得到的左右子树。
- 构造 KDTree(vp)：对点集 vp 递归建树；
- 选择划分维度：比较当前 bbox 的宽与高，若宽≥高按 x 轴划分，否则按 y 轴划分。
- 将点集按所选维度排序，取中位数作为切分值，左右子集递归生成子树；叶节点仅含一个点。
- 距离与启发：
- distance(p)：返回点 p 到某节点 bbox 的最小距离平方（若 p 在 bbox 内则为 0）。
- 查询 nearest(p)：返回 pair<T, P>，T 为距离平方、P 为最近邻点坐标。
- 结构体 Node：
-
核心算法流程（最近邻搜索）
- 若为叶：直接计算 (p, pt) 的距离平方，作为当前候选。
- 否则：
- 计算 p 到两个子 bbox 的最小距离平方 dL、dR，按较小者先搜（启发式剪枝）。
- 在首选子树返回值更新当前最优 best。
- 若另一个子树的 bbox 最小距离平方 < best 距离平方，则有潜在更优解，继续搜索该子树；否则剪枝。
- 返回全局最优 pair<T,P>。
- 若需要排除自匹配：在叶或比较阶段检测 pt 是否等于查询点 p 并跳过。
-
复杂度与边界条件
- 构建：每层对当前子集排序，经典实现整体 O(n log n)；若使用线性时间选择中位数可降常数。
- 查询：期望 O(log n)，依赖数据分布与划分平衡性；最坏情况下 O(n)（如退化分布或所有 bbox 都被访问）。
- 数值与稳定性：距离平方对 ll 可能溢出，建议使用更大整数类型或 long double 存储与比较。
- 退化：点高度聚集或共线时，树形不平衡，查询退化；可通过随机化输入或轮换维度减缓。
-
实现细节与常见坑
- 维度选择：本实现按 bbox 尺寸选择分割维，有利于降低树高与剪枝命中率；也可采用层号奇偶轮换（x/y/x/…）。
- 中位选择：排序取中位简单稳健；若多维相同坐标，需保证分割后两侧非空（可按索引稳定划分）。
- 剪枝判定：必须使用“到 bbox 的下界距离平方 < 当前 best”的准则；比较边界用严格或非严格要与实现一致，避免漏解。
- 去除 sqrt：全程比较距离平方，避免开方带来的精度与性能损耗。
- 多解处理：等距多个最近点返回其一；若需稳定性，可在比较相等时按字典序取较小点。
-
变体与扩展
- k 近邻（k-NN）：在搜索中维护大小为 k 的最大堆，剪枝门限为堆顶距离。
- 范围查询（矩形/圆形）：访问与范围相交的子树并收集命中点。
- 三维扩展：bbox 扩展到盒体 (x0,x1,y0,y1,z0,z1)，分割维度增加 z 的选择与比较。
- 动态更新：标准 KD 树不擅长动态插入/删除；可批量重建或采用平衡 KD 树/BBF 等近似结构。
-
正确性要点与不变式
- bbox 必须覆盖子树全部点；distance(p, bbox) 是到该子树任一点距离的下界，保证剪枝安全。
- 先搜更近子树可快速收紧 best，下界判定提高剪枝率，保持期望对数查询。
-
对比与取舍
- 与024-几何-最近点对：最近点对是全局两点对问题；KD 树 nearest 是单源最近邻，问题语义不同。
- 与栅格/哈希分桶：KD 树对各向异性分布更稳健；分桶在均匀分布与邻域固定半径时更快更简单。
- 与 R 树/BVH：若查询以范围/相交为主，层次包围体（AABB 树/BVH）更适宜；KD 树擅长最近邻。