Basic recursive Algorithm in Java

Question

I'm trying to implement a basic RRT (rapidly-exploring random tree) algorithm in Java. I have a class TreeNode, which saves the x and y position of the node and in an ArrayList it saves all the child-nodes it has. In my main program I have the root of the tree. If I want to find the nearest neighbour in tree I call this code. The method is called with the root node as "node" and minAbstand is 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);
    }
}

I thought I am going recursively through all nodes and find that one, with the lowest distance. After the NEAREST_NEIGHBOUR method, the nearest neighbour shoudl be saved in xnearest. Now I add the new node to the nearest node via this method:

xnearest.addNode(xnew).

addNode is a method from the TreeNode class which calls arraylist.add(node), so just adding the node to the ArrayList. After this the new node should be a "child-node" of the nearest node. And then all starts from the beginning: - create random node, -finding nearest node to random node, - adding random node to nearest node,... But in fact this isn't what happens.

In the highlighted area you can see that it didn't choose the node with the lowest distance. What am I doing wrong there?

The whole code:

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

And the TreeNode class:

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

The solution?

Is this right now? Recursion is really tricky

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;

}

Something is not clear: What are you actually doing after finding a node nearest than the input node? You say you add it into a list, but in the code you ovewrite the xnearest variable. — Little Santi
– Little Santi, Commented Oct 10, 2015 at 18:55
And the graph you have posted, is it a tree or is it a dag (direct acyclic graph)? If it as actually a tree, the highlighted area covers two different branches, and I can't see clearly which one is the input node and which one is the assumed as nearest in your experiment. — Little Santi
– Little Santi, Commented Oct 10, 2015 at 19:09
I see no fails in NEAREST_NEIGHBOUR, but NEW_STATE is dark to me: Once you already have the xnearest and the xrand, why creating a new node? — Little Santi
– Little Santi, Commented Oct 10, 2015 at 19:32
I don't know why you think you should deface your question like that, but no, you shouldn't. I rolled back that edit, so the posted answer isn't meaningless anymore. — Tom
– Tom, Commented Oct 13, 2015 at 6:46

Little Santi · Accepted Answer · 2015-10-10 19:49:00Z

1

I must correct myself: The NEAREST_NEIGHBOUR method has a failing logic. Look:

When the method starts, compares the recived minAbstand with the distance to the current evaluated node. And, if it is lower, the minAbstand value is updated in order to restrict the search criterium within the current subtree recursively. So far, so good.

But, what about the sibling-subtrees? I mean: when the current subtree is completely browsed, the current method invocation ends, and thus, returns the control to the calling method, which its itself, in a previous recursive frame. But the values of the local variables get missed (like minAbstand).

What you need is to return minAbstand as the return value of NEAREST_NEIGHBOUR, and update it every time it is recursively invoked.

answered Oct 10, 2015 at 19:49

Little Santi

8,8532 gold badges22 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Little Santi Over a year ago

Yes! That's exactly what I meant.

Little Santi Over a year ago

One last suggestion: You'd better improve your code's readability avoiding long expressions (specially if they are repeated) like calculating the distance: Code that calculation in one only private method and call it wherever you need it.

Collectives™ on Stack Overflow

Basic recursive Algorithm in Java

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related