You need to enable JavaScript to run this app. 二维空间KD-Tree生成的边界矩形如何编号满足顺序单调性,该方法可否拓展至高维
优惠活动
大模型
产品
解决方案
定价
更多

二维空间KD-Tree生成的边界矩形如何编号满足顺序单调性,该方法可否拓展至高维

基于scikit-learn KD-Tree空间划分矩形的单调性编号探究

基础实验配置

  • 输入数据集:1000个二维空间数据点,存储为列表lst
  • 空间划分逻辑:基于scikit-learn框架的KD-Tree算法,设置参数leaf_size=30,生成尺寸近似相等的空间划分边界矩形,核心初始化代码为:
import sklearn
lst  # 存储1000个二维数据点
sklearn.KDTree(lst, leaf_size=30)
  • 提取的划分结果要素:
    • mins:所有划分矩形的左下角坐标集合
    • maxs:所有划分矩形的右上角坐标集合
    • data:每个矩形对应的归属数据点集合

核心探究目标

  • 验证第一类问题:是否存在可行的矩形编号(索引)规则,满足全局顺序单调性要求——若矩形B内任意点(x,y)的坐标分量全大于矩形A内任意点(x',y')(即同时满足x>x'且y>y'),则B的映射编号必须严格大于A的映射编号
  • 验证第二类问题:符合要求的编号规则是否能够拓展应用到更高维度的空间场景

已尝试方案的失效情况

此前测试了两类基于距离的排序编号方案,均存在跨位置矩形的单调性失效问题,空间中部区域的矩形排序错位尤为突出:

  • 方案一:按矩形左下角到原点的距离排序编号
  • 方案二:按矩形右上角到原点的距离排序编号

典型错位案例:采用右上角到原点距离排序生成的编号中,相邻编号13、14的矩形完全违反单调性要求:矩形13内存在坐标分量全大于矩形14内任意点的情况。仅手动互换这两个错位矩形的编号,虽在局部案例上逻辑自洽,但尚未从理论层面证明该调整思路的全局有效性。

现有距离排序逻辑实现代码

import numpy as np
# mins为所有矩形的左下角坐标集合
# maxs为所有矩形的右上角坐标集合
# data为每个矩形对应的归属数据点集合
mins, maxs, data

# 计算每个矩形右上角到原点的距离作为排序键
distances = [distance(i, [0]*2) for i in maxs]
sort_indices = np.argsort(distances)
# 按排序结果重排所有矩形的对应属性
mins = mins[sort_indices]
maxs = maxs[sort_indices]
data = [data[i] for i in sort_indices]

# 后续可通过matplotlib可视化矩形边界与归属数据点

内容的提问来源于stack exchange,提问作者George Wu

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.12 17:06:03