title: Inserting an object into a quadtree in Java
body: <p>I'm making a quadtree and need helping inserting an object into it. I understand the concept of doing it, but I'm not great with recursion and the way Java passes variables.</p>
  
  <p>I have a Quadtree class which contains a Node called root. The Node class has four Nodes inside of it, which are the four quads that make it up. The root node is created when you create the quad tree, and the four nodes inside each node aren't created until I call createChildrenQuads(). However, for the root node, that method is called when you create the quad tree.</p>
  
  <p>So my thought process on how to insert an item into a node is this:</p>
  
  <ol>
  <li>Start at the root node</li>
  <li>For each node:
  <ol>
  <li>Check and see which of the current node's children quad the current
  item fits in</li>
  <li>If it fits in one of them, insert it into that
  node(call the recursive method and start over) </li>
  <li>If it didn't fit into
  any, add it to the current node's list of objects and be done</li>
  </ol></li>
  </ol>
  
  <p>Based on that, I created this:</p>
  
  <pre><code>public void insert(Entity e) {
      insert(root, e);
  }
  
  private void insert(Node n, Entity e){
      Rectangle temp = e.getRectangle();
  
      if (!n.childrenHaveBeenCreated())
          n.createChildrenQuads(n.m_quadRect);
  
      //first check which node it can go into
  
      if ( n.NW.m_quadRect.contains(temp)) {
          n.NW = insert(n.NW, e);
          return;
      }
  
      if ( n.NE.m_quadRect.contains(temp)) {
          n.NE = insert(n.NE, e);
          return;
      }
  
      if ( n.SW.m_quadRect.contains(temp)) {
          n.SW = insert(n.SW, e);
          return;
      }
  
      if ( n.SE.m_quadRect.contains(temp)) {
          n.SE = insert(n.SE, e);
          return;
      }
  
      n.m_objects.add(e);
  }
  </code></pre>
  
  <p>I think quadtree-wise, the logic I have there is fine. When I debug the code, it looks like everything works as it should. However, I believe my problem is that Java passes parameters by value and not reference, so while I add it at the correct spot, it doesn't get "saved" because it is just a local variable. I believe that is the problem, but I could be wrong.</p>
  
  <p>So I tried changing it a bit to make it so that the insert method returns the current node, so that everything should get "saved" correctly. This is what I came up with:</p>
  
  <pre><code>public void insert(Entity e) {
      root = insert(root, e);
  }
  
  private Node insert(Node n, Entity e) {
      Rectangle temp = s.getRectangle();
  
      if (!n.childrenHaveBeenCreated())
          n.createChildrenQuads(n.m_quadRect);
  
      //first check which node it can go into
  
      if ( n.NW.m_quadRect.contains(temp)) {
          n.NW = insert(n.NW, e);
          return n;
      }
  
      if ( n.NE.m_quadRect.contains(temp)) {
          n.NE = insert(n.NE, e);
          return n;
      }
  
      if ( n.SW.m_quadRect.contains(temp)) {
          n.SW = insert(n.SW, e);
          return n;
      }
  
      if ( n.SE.m_quadRect.contains(temp)) {
          n.SE = insert(n.SE, e);
          return n;
      }
  
      n.m_objects.add(e);
      return n;
  }
  </code></pre>
  
  <p>However, I still have the same problem. Now I'm not sure what my problem is.</p>
  
  <p>I'm using this for a game, and I have it so that it draws an outline around where all of the quads are, and I can click to add an Entity into the quadtree. Both versions of my code seem to act the same. What happens is when I add an entity to the quadtree, it gets added and stays there, so I guess my theory of it not getting "saved" because of how Java passes references is wrong. </p>
  
  <p>However, my code should(at least in my mind should) place each entity into the quadtree to as low of a level as it can, creating new children quads in each node as it goes down the tree. What actually happens though, is that sometimes it seems to just add the new entity into the current quad, not going down the tree at all, or it goes down a level or two and that is it, when it can easily go down a few more levels.</p>
  
  <p>Can anyone see anything wrong with the code or my logic at all?</p>