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持っているものxとy価値観。値の中央値はx、 でソートしxてから、中央の要素x( が奇数の場合) または中央の 2 つの 'pointsの平均(が偶数の場合) を取得することで取得できます。pointsxpoints

または、 median-of-medians などの高速選択アルゴリズムを使用します。

于 2011-06-06T12:19:52.963 に答える