Как вы создаете KDTree в Java

Я просмотрел пару реализаций, и они немного сбивают с толку, и я был бы признателен за какую-то разбивку того, что мне нужно для создания 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‹ Point > points

Любая помощь будет оценена по достоинству!


java nearest-neighbor kdtree
person agaiuqer    schedule 13.11.2019    source источник
comment
Добро пожаловать в СО. Ваш вопрос читается как просьба к кому-то написать для вас реализацию KDTree. Могу ли я предложить вам прочитать описание стандартного алгоритма балансировки дерева на en.wikipedia.org /wiki/K-d_tree и попробовать реализовать его самостоятельно? Этот форум лучше всего подходит для ответов на конкретные технические проблемы, с которыми вы столкнулись, а не для общих вопросов "как мне реализовать X?"   -  person sprinter    schedule 14.11.2019
comment
Да, я читал вики. На самом деле я не прошу, чтобы кто-то закодировал это для меня, более того, я спрашиваю, выглядит ли мой класс Node точным, и какие функции мне нужно реализовать для класса KDTree.   -  person agaiuqer    schedule 14.11.2019
comment
Хорошо, я могу дать несколько советов по этим вещам в ответе.   -  person sprinter    schedule 14.11.2019

Ответы (1)


arrow_upward
0
arrow_downward

Что касается структуры вашего кода и методов, которые вам нужно будет реализовать, я бы посоветовал, чтобы он выглядел примерно так:

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

Там еще много логики, но, надеюсь, это поможет вам начать.

person sprinter    schedule 13.11.2019