如何在Java中构建KDTree

Question

我已经看过几个实现，它们有点令人困惑，我希望能根据一系列点对构建KDTree所需的内容进行一些分类。我将使用这个KDTree来执行2DK近邻搜索。

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

点类

   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< Point > 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));
        }
    }
}

仍然有很多逻辑需要写，但希望这能让你开始写。