二维KD树中同维度点的x轴分裂处理问题问询

出现的问题 #

当选择x轴对两个x值完全相同的点进行分裂时，常规KD树的中位数分裂逻辑会直接失效：

• 两个点的x值等于分裂阈值（中位数），按照<=或<的划分规则，它们会被同时划入左子树或右子树，导致其中一个子树为空，另一个子树包含所有点。
• 这种完全不平衡的分裂会彻底破坏KD树的空间划分效率，后续的近邻查询等操作无法获得预期的性能提升。

处理方法 #

针对这种场景，有几种实用的解决方式：

• 切换分裂维度：直接放弃当前的x轴，改用下一个维度（比如y轴）进行分裂。由于两个点在其他维度大概率存在差异，这样就能正常将点分到不同子树，保证分裂后的平衡。
• 调整分裂规则：如果必须使用当前维度，可以扩展划分逻辑：当点的维度值等于分裂阈值时，参考其他维度的取值来决定子树归属（比如比较y值，较小的进入左子树，较大的进入右子树），或者随机分配到左右子树，避免单一子树堆积所有点。
• 引入微小扰动：给其中一个点的x值添加极小的随机偏移（比如1e-9量级），让两个点的x值产生可区分的细微差异，这样就能沿用常规的中位数分裂规则。但要注意，这种方法可能会对精度敏感的场景产生影响，需要结合业务需求评估是否适用。

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