algorithm - 最近邻搜索的二维树实现苦苦挣扎

Question

我在实现 2d Tree 数据结构时遇到了困难。我将概述我在这里所做的事情，希望有人能够告诉我出了什么问题。

非常感谢大家的时间。

这是作业：https ://coursera.cs.princeton.edu/algs4/assignments/kdtree/specification.php

这是最近邻搜索的方法规范：要找到到给定查询点的最近点，从根开始并使用以下修剪规则在两个子树中递归搜索：如果到目前为止发现的最近点比查询点与对应于 a 的矩形之间的距离更近节点，则无需探索该节点（或其子树）。也就是说，仅当一个节点可能包含一个比目前找到的最佳节点更近的点时才搜索它。剪枝规则的有效性取决于快速找到附近的点。为此，组织递归方法，以便当有两个可能的子树要向下时，您始终选择位于分割线同一侧的子树作为查询点作为要探索的第一个子树——找到的最近点在探索第一个子树时，可以修剪第二个子树。

这是我所做的。

1. 设置一个等于根的冠军。
2. 取冠军的左右节点。
3. 如果两者都不为空，请计算三件事 - a。当前冠军到p点的距离（championDistance），b。从点 p 到左矩形的距离 (leftRectDistance)，c。从 p 到右矩形的距离 (rightRectDistance)。注意：这最后两个计算都使用了 RectHV 类中的 distanceSquaredTo(Point2D p) 方法。
4. 计算哪个更小 - 这是我将首先搜索的一侧。说，为了论证，它是左节点。
5. 对于这个左节点 - 检查这个节点的点是否比 ChampionDistance 更近。如果是这样，则将冠军设置为该节点并从（2）重新开始

（5）中的递归完成后，检查右节点的 rightRectDistance 是否小于递归后冠军节点的点到 p 的距离。如果是这样，则找到正确节点的“冠军”并从（2）重新开始。然后，将左边的冠军点与右边的冠军点进行比较，并选择距离较近的一个。

回复：步骤 (3) - 如果只有一个节点不为空，则重复 (5)，但仅针对可用的一个节点。

6. 完成所有这些之后，冠军应该指向与 p 最接近的节点。

    // a nearest neighbor in the set to point p; null if the set is empty
    public Point2D nearest(Point2D p) {
        if (p == null) throw new IllegalArgumentException();
        return nearest(root, p, root.point.distanceSquaredTo(p));
    }

    private Point2D nearest(Node champNode, Point2D queryPoint, double champDistance) {
        if (champNode.lb == null && champNode.rt == null) return champNode.point;

        Point2D champPoint = champNode.point;
        if (champNode.lb != null && champNode.rt != null) {

            // to determine which side to examine first
            double leftRectDistance = champNode.lb.rect.distanceSquaredTo(queryPoint);
            double rightRectDistance = champNode.rt.rect.distanceSquaredTo(queryPoint);

            // exploring left side first
            if (leftRectDistance < rightRectDistance) {
                double potentialDistance = champNode.lb.point.distanceSquaredTo(queryPoint);
                // update champ point
                if (potentialDistance < champDistance) {
                    champPoint = nearest(champNode.lb, queryPoint, potentialDistance);

                    // search right side if rightRectDistance < distance to the current champion.
                    if (rightRectDistance < champPoint.distanceSquaredTo(queryPoint)) {
                        Point2D potentialNewChampPoint = nearest(champNode.rt, queryPoint,
                                                                 champDistance);

                        // compare two "champ" points
                        if (potentialNewChampPoint.distanceSquaredTo(queryPoint) < champPoint
                                .distanceSquaredTo(queryPoint)) {
                            champPoint = potentialNewChampPoint;
                        }
                    }
                }
            }
            // exploring right side first
            else {
                double potentialDistance = champNode.rt.point.distanceSquaredTo(queryPoint);
                // update champ point
                if (potentialDistance < champDistance) {
                    champPoint = nearest(champNode.rt, queryPoint, potentialDistance);

                    // search left side if leftRectDistance < distance to the current champion.
                    if (leftRectDistance < champPoint.distanceSquaredTo(queryPoint)) {
                        Point2D potentialNewChampPoint = nearest(champNode.lb, queryPoint,
                                                                 champDistance);

                        // compare two "champ" points
                        if (potentialNewChampPoint.distanceSquaredTo(queryPoint) < champPoint
                                .distanceSquaredTo(queryPoint)) {
                            champPoint = potentialNewChampPoint;
                        }
                    }
                }
            }
        }
        if (champNode.lb != null && champNode.rt == null) {
            double leftRectDistance = champNode.lb.rect.distanceSquaredTo(queryPoint);
            if (leftRectDistance < champPoint.distanceSquaredTo(queryPoint)) {
                double potentialDistance = champNode.lb.point.distanceSquaredTo(queryPoint);
                Point2D potentialNewChampPoint = nearest(champNode.lb, queryPoint,
                                                         potentialDistance);
                if (potentialNewChampPoint.distanceSquaredTo(queryPoint) < champPoint
                        .distanceSquaredTo(queryPoint)) {
                    champPoint = potentialNewChampPoint;
                }
            }
        }
        if (champNode.rt != null && champNode.lb == null) {
            double rightRectDistance = champNode.rt.rect.distanceSquaredTo(queryPoint);
            if (rightRectDistance < champPoint.distanceSquaredTo(queryPoint)) {
                double potentialDistance = champNode.rt.point.distanceSquaredTo(queryPoint);
                Point2D potentialNewChampPoint = nearest(champNode.rt, queryPoint,
                                                         potentialDistance);
                if (potentialNewChampPoint.distanceSquaredTo(queryPoint) < champPoint
                        .distanceSquaredTo(queryPoint)) {
                    champPoint = potentialNewChampPoint;
                }
            }
        }
        return champPoint;
    }

非常感谢！

标签： algorithmdata-structurestree