我(尝试)在Processing/Java中实现KD树,并遵循我在数十篇文章和维基百科文章中看到的逻辑,但我一定做错了什么,因为输出如下所示:
显然有些东西不对劲,因为节点是重复的,而且看起来根本不像维基百科树。
这是我的 buildKDTree 函数:
public Node buildKDTree(List<Point> pointList, int depth){
int size = pointList.size();
int axis = depth % 2;
Node newNode = new Node();
if(pointList.size() == 1)
{
System.out.print("I am a leaf \n");
System.out.print("Size of list: " + pointList.size() + "\n");
System.out.print("Point: " + pointList.get(0) + "\n");
newNode.point = pointList.get(0);
newNode.left = null;
newNode.right = null;
System.out.print("Node Point: " + newNode.point + "\n");
return newNode;
}
if(size <= 0)
{
return null;
}
if(axis == 0)
{
//sort by x
System.out.print("Sorting by X \n");
Comparator<Point> com = new xComp();
Collections.sort(pointList, com);
}
else if(axis == 1)
{
System.out.print("Sorting by Y \n");
Comparator<Point> com = new yComp();
Collections.sort(pointList, com);
}
int median = size/2;
//System.out.print("Median is: " + points.get(median) + " \n");
List<Point> beforeMedian = pointList.subList(0, median);
List<Point> afterMedian = pointList.subList(median, size);
newNode.point = pointList.get(median);
newNode.left = buildKDTree(beforeMedian, depth + 1);
newNode.right = buildKDTree(afterMedian, depth + 1);
return newNode;
}
我的KD Tree类、Node类和Point类:
class KDTree{
Node root;
public KDTree()
{
root = null;
}
}
class Node{
Node left;
Node right;
Point point;
Node(Point _p, Node l, Node r){
point = _p;
left = l;
right = r;
}
Node(Node l, Node r){
left = l;
right = r;
}
Node(){
left = null;
right = null;
point = null;
}
Node(Point _p)
{
point = _p;
left = null;
right = null;
}
void setPoint(Point _p)
{
point = _p;
}
}
class Point {
public PVector p;
boolean isNearestNeighbor = false;
boolean isSearchLocation = false;
public Point( float x, float y ){
p = new PVector(x,y);
isNearestNeighbor = false;
isSearchLocation = false;
}
public Point(PVector _p0 ){
p = _p0;
}
}
我如何打印树:
public void printLevelOrder(Node root)
{
if(root == null )
{
return;
}
Queue<Node> q =new LinkedList<Node>();
q.add(root);
while(true)
{
int nodeCount = q.size();
if(nodeCount == 0)
{
break;
}
while(nodeCount > 0)
{
Node node = q.peek();
System.out.print("("+node.point + ")");
q.remove();
if(node.left != null)
{
q.add(node.left);
}
if(node.right != null)
{
q.add(node.right);
}
if(nodeCount > 1)
{
System.out.print(", ");
}
nodeCount--;
}
System.out.println();
}
}
如有任何帮助,我们将不胜感激!我已经看了几个小时了,所以也许我错过了一些简单的东西。
最佳答案
我不想提供一些可能出现问题的提示,而是建议您自己解决此问题的一些步骤:
- 将
buildKDTree
方法分解为几个较小的方法,执行更小的功能(例如构建叶子、排序子列表等) - 对每个单元进行单元测试,确保其完全符合您的预期
- 使用简单案例转向更复杂的案例对整个功能进行单元测试
- 如果这些单元测试中的任何一个以异常方式运行,请使用交互式调试器来找出发生了什么
- 如果您无法理解为什么某些事物会以某种方式表现,请作为关于该案例的问题
- 最后,一旦一切正常,就可以应用到实际案例
这可能需要更长的时间,但您会在此过程中学到更多东西。
关于java - KD-Tree 点重复并给我错误的输出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58905980/