我正在尝试在Java中实现基本的RRT（快速探索随机树）算法。我有一个名为TreeNode的类，它保存节点的x和y位置，并在一个ArrayList中保存它拥有的所有子节点。在我的主程序中，我有树的根节点。如果我想在树中找到最近的邻居，我会调用这段代码。该方法以根节点作为“node”进行调用，minAbstand为Integer.MAX_VALUE。
private void NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) <= minAbstand){//normal method to find the distance
minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
xnearest = node;
}
for(int i = 0; i < node.getNodes().size(); i++){
NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
}
}
我原以为我会通过递归遍历所有节点，并找到距离最近的一个。在使用NEAREST_NEIGHBOUR方法后，最近邻居应该被保存在xnearest中。现在我通过这种方法将新节点添加到最近节点：
xnearest.addNode(xnew)。
addNode是TreeNode类的一个方法，它调用arraylist.add(node)，所以只需要将节点添加到ArrayList中。之后，新节点应该是最近节点的"子节点"。然后从头开始：-创建随机节点，-找到最近的节点到随机节点，-将随机节点添加到最近的节点，......但实际上情况并非如此。
在突出显示的区域中，可以看到它没有选择距离最近的节点。我在这里做错了什么？
整个代码：
private void doRRT(Canvas canvas, PaintEvent e, int K, int deltaT){
for(int i = 0; i < K; i++){
xrand = new TreeNode(new Random().nextInt(canvas.getSize().x * 2) - 500, new Random().nextInt(canvas.getSize().y * 2) - 300);
NEAREST_NEIGHBOUR(xrand.getxPos(), xrand.getyPos(), xstart, Integer.MAX_VALUE);
NEW_STATE(xrand.getxPos(), xrand.getyPos(), deltaT);
e.gc.drawRectangle(xnearest.getxPos() - 1, xnearest.getyPos() - 1, 2, 2);
e.gc.drawLine(xnearest.getxPos(), xnearest.getyPos(), xnew.getxPos(), xnew.getyPos());
}
}
private void NEW_STATE(int xrand, int yrand, int deltaT) {
int nearx = xnearest.getxPos(), neary = xnearest.getyPos();
if(Math.sqrt(Math.pow(nearx - xrand, 2) + Math.pow(neary - yrand, 2)) > deltaT){
float faktor = (float) (Math.sqrt(Math.pow(nearx - xrand, 2) + Math.pow(neary - yrand, 2)) / deltaT);
xnew = new TreeNode((int) (nearx + (xrand - nearx)/ faktor), (int) (neary + (yrand - neary)/ faktor));
} else {
xnew = new TreeNode(xrand, yrand);
}
xnearest.addNode(xnew);
}
private void NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
counter2++;
if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) < minAbstand){
minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
xnearest = node;
}
for(int i = 0; i < node.getNodes().size(); i++){
NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
}
}
还有TreeNode类：
TreeNode(int x, int y){
xPos = x;
yPos = y;
nodes = new ArrayList<TreeNode>();
}
public ArrayList<TreeNode> getNodes() {
return nodes;
}
public int getxPos() {
return xPos;
}
public int getyPos() {
return yPos;
}
public void addNode(TreeNode node){
nodes.add(node);
}
解决方案？
现在这样做对吗？递归确实很棘手。
private int NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) < minAbstand){
minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
xnearest = node;
}
for(int i = 0; i < node.getNodes().size(); i++){
minAbstand = NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
}
return minAbstand;
}
NEAREST_NEIGHBOUR中没有看到失败，但是NEW_STATE对我来说很难理解：一旦你已经有了xnearest和xrand，为什么还要创建一个新节点？ - Little Santi