1

我正在尝试实施和理解KdTree,以下是我找到的链接。 http://ldots.org/kdtree/#buildingAkDTree 但我无法理解以下算法

tuple function build_kd_tree(int depth, set points):
    if points contains only one point:
        return that point as a leaf.

    if depth is even:
        Calculate the median x-value.
        Create a set of points (pointsLeft) that have x-values less than
            the median.
        Create a set of points (pointsRight) that have x-values greater
            than or equal to the median.
    else:
        Calculate the median y-value.
        Create a set of points (pointsLeft) that have y-values less than
            the median.
        Create a set of points (pointsRight) that have y-values greater
            than or equal to the median.

    treeLeft = build_kd_tree(depth + 1, pointsLeft)
    treeRight = build_kd_tree(depth + 1, pointsRight)

    return(median, treeLeft, treeRight)

我不明白是什么意思 Calculate the median x-value.

4

1 回答 1

0

你的points拥有xy价值观。值的中位数x可以通过排序获得x,然后取中间元素的x(对于奇数个)或两个中间元素的points平均值(对于偶数个)。pointsxpoints

或者,使用快速选择算法,例如中位数中位数。

于 2011-06-06T12:19:52.963 回答