我已经看了几个实现,它们有些令人困惑,对于从点列表构建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
任何帮助,将不胜感激!
最佳答案
关于代码的结构和您将需要实现的方法,我建议它看起来应类似于以下内容:
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));
}
}
}
仍然有很多逻辑要写,但是希望可以让您入门。