python - 对二维空间中的矩形进行编号以满足单调性

Question

给定二维空间中的一组数据点（本例中为 1000 个），我运行 KD-tree 算法来生成大小大致相等的边界框。来自sklearn：

import sklearn

lst # 1000 points
sklearn.KDTree(lst, leaf_size=30)

对于每个矩形，我想知道是否有办法对矩形进行编号（或索引），如果 B 中的点 (x,y) 更大，则矩形 A 中包含的所有点都小于矩形 B 中包含的所有点比 A 中的 (x', y') 。如果有，这种方法可以扩展到更高的维度吗？

换句话说，如果 x > x' 并且 y > y'，则 B 的映射 > A 的映射。

我考虑过使用底角的距离排序，顶角的距离排序，但中间框似乎总是存在问题。

举个例子：

方框的编号标注在左上角的右侧。这是通过从右上角对距离进行排序而创建的。

对于框 14 到 13，属于 13 的点的所有坐标都大于框 14，这不是我想要的。以下是图片形式的解释：

如果把 13 和 14 调换了，这种方法可能一般都行得通，但我不知道这是否可以证明。

这是我如何运行此代码的python中的伪代码。

import numpy as np
# mins is the bottom_left corner of a box
# maxs is the top_right corner of a box
# data is the data points that belongs in the box described by mins[i], maxs[i]

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]

# Draw mins, maxs, and data with matplotlib.

标签： pythondatabasenumpygeometrykdtree