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

Question

我正在遵循https://rosettacode.org/wiki/K-d_tree中的KD Tree实现的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

代码更改