java - 如何用 Java 构建 KDTree

Question

我看过几个实现，它们有点令人困惑，我希望对从点列表构建 KDTree 所需的内容进行某种分割。我最终将使用这个 KDTree 来执行 2D K 最近邻搜索。

这是我到目前为止所拥有的，但不多。

点等级

   class Point{
   public PVector p;

   public Point(float x, float y){
     p = new PVector(x,y);
   }

   public Point(PVector _p0 ){
     p = _p0;
   }

   float getX(){ return p.x; }
   float getY(){ return p.y; }

   float x(){ return p.x; }
   float y(){ return p.y; }

   public float distance( Point o ){
     return PVector.dist( p, o.p );
   }

节点类

class Node{
  Node left;
  Node right;
  Point p;

  Node(Point _p, Node l, Node r){
    p = _p;
    left = l;
    right = r;
  }
}

KDTree类

class KDTree{
  Node root;

  KDTree()
  {
    root = null;
  }

}

如您所见，Node 和 KDTree 类并未真正实现，这就是我陷入困境的地方。

我想通过提供如下内容来最终构建这个 KDTree:ArrayList points

如有任何帮助，我们将不胜感激!

Answer 1

关于代码的结构和需要实现的方法，我建议它应该如下所示:

enum Axis {
    X, Y;

    public Axis next() {
        return values()[(ordinal() + 1) % values().length];
    }
}

interface Node {
    Point closestTo(Point point);
}

class Leaf implements Node {
    private final Point point;

    public Leaf(Point point) {
        this.point = point;
    }

    public Point closestTo(Point point) {
        return this.point;
    }
}

class Branch implements Node {
    private final Axis axis;
    private final Point median;
    private final Node smaller;
    private final Node larger;

    public Branch(Axis axis, Point median, Node smaller, Node larger) {
        this.axis = axis;
        this.median = median;
        this.smaller = smaller;
        this.larger = larger;
    }

    public Point closestTo(Point point) {
        ...
    }
}

class KD_Tree {
    private final Optional<Node> root;

    public KD_Tree(List<Point> points) {
        this.root = makeNode(points);
    }

    private Optional<Node> makeNode(Axis axis, List<Point> points) {
        switch (points.size()) {
            case 0: 
                return Optional.empty();
            case 1: 
                return Optional.of(new Leaf(points.get(0));
            default:
                Point median = medianOf(points);
                Node smaller = makeNode(axis.next(), lessThan(median, points)).get();
                Node larger = makeNode(axis.next(), greaterThan(median, points)).get();
                return Optional.of(new Branch(axis, median, smaller, larger));
        }
    }
}

还有很多逻辑需要写，但希望这能让您开始。