如何在kd-tree实现中包含同一分割线上的点

Question

下面是来自https://rosettacode.org/wiki/K-d_tree的KD树实现的python代码，代码如下：

from random import seed, random
from time import clock
from operator import itemgetter
from collections import namedtuple
from math import sqrt
from copy import deepcopy


def sqd(p1, p2):
    return sum((c1 - c2) ** 2 for c1, c2 in zip(p1, p2))


class KdNode(object):
    __slots__ = ("dom_elt", "split", "left", "right")

    def __init__(self, dom_elt, split, left, right):
        self.dom_elt = dom_elt
        self.split = split
        self.left = left
        self.right = right


class Orthotope(object):
    __slots__ = ("min", "max")

    def __init__(self, mi, ma):
        self.min, self.max = mi, ma


class KdTree(object):
    __slots__ = ("n", "bounds")

    def __init__(self, pts, bounds):
        def nk2(split, exset):
            if not exset:
                return None
            exset.sort(key=itemgetter(split))
            print('-------------------------------')
            print('set: ',exset, 'split: ',split)
            m = len(exset) // 2
            d = exset[m]
            print('pivot point:', d, 'm: ',m)
            while m + 1 < len(exset) and exset[m + 1][split] == d[split]:
                m += 1
            print('pivot point:', d, 'm: ',m)
            s2 = (split + 1) % len(d)  # cycle coordinates
            return KdNode(d, split, nk2(s2, exset[:m]),
                                    nk2(s2, exset[m + 1:]))
        self.n = nk2(0, pts)
        self.bounds = bounds


if __name__ == "__main__":
    seed(1)
    P = lambda *coords: list(coords)
    kd1 = KdTree([P(2, 3), P(5, 4), P(9, 6), P(4, 7), P(8, 1), P(7, 2)],
                  Orthotope(P(0, 0), P(10, 10)))

结果如下：

-------------------------------
set:  [[2, 3], [4, 7], [5, 4], [7, 1], [7, 2], [9, 6]] split:  0
pivot point: [7, 1] m:  3
pivot point: [7, 1] m:  4
-------------------------------
set:  [[7, 1], [2, 3], [5, 4], [4, 7]] split:  1
pivot point: [5, 4] m:  2
pivot point: [5, 4] m:  2
-------------------------------
set:  [[2, 3], [7, 1]] split:  0
pivot point: [7, 1] m:  1
pivot point: [7, 1] m:  1
-------------------------------
set:  [[2, 3]] split:  1
pivot point: [2, 3] m:  0
pivot point: [2, 3] m:  0
-------------------------------
set:  [[4, 7]] split:  0
pivot point: [4, 7] m:  0
pivot point: [4, 7] m:  0
-------------------------------
set:  [[9, 6]] split:  1
pivot point: [9, 6] m:  0
pivot point: [9, 6] m:  0

我稍微改变了这个例子，p（8,1）到p（7,1）（我画了下面的点），然后发现p（7,2）将不会被生成到KdNode，因为第一个轴心点是（7,1），KdNode将把集合拆分为{[2,3]，[4,7]，[5,4]，[7,1]}和{[9,6]}，根据代码，这将使p（7,2）消失

我想知道在旋转点的同一条分割线上是否还有其他点（这里是垂直线交叉点（7,1）），应该包括哪一组p（7,2），以及何时必须将其作为KdNode

感谢您的阅读和帮助，我们将不胜感激

Answer 1

代码变更

return KdNode(d, split, self.nk2(s2, exset[:m]),self.nk2(s2, exset[m + 1:]))

到

return KdNode(exset[m], split, self.nk2(s2, exset[:m]),self.nk2(s2, exset[m + 1:]))

虽然split对我来说看起来很奇怪，但我正在努力包含缺失的一点。不过我还是希望听到更好的答案！谢谢大家!