CODEWITHSUNDEEP
javaalgorithmtreequadtree
krej
krej

Reputation: 468

Inserting an object into a quadtree in Java

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.

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.

So my thought process on how to insert an item into a node is this:

  1. Start at the root node
  2. For each node:
    1. Check and see which of the current node's children quad the current item fits in
    2. If it fits in one of them, insert it into that node(call the recursive method and start over)
    3. If it didn't fit into any, add it to the current node's list of objects and be done

Based on that, I created this:

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

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.

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:

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

However, I still have the same problem. Now I'm not sure what my problem is.

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.

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.

Can anyone see anything wrong with the code or my logic at all?

Upvotes: 2

Views: 4061

Answers (1)

dann.dev
dann.dev

Reputation: 2494

I think it is the way you've structured your program. The quadtree gets to test every quadrant, but it also alway adds the element at the end... So even though it will recursively make it's way to the bottom, on the way back up it will always run your last n.m_objects.add(e); therefore changing where it is added on the way back up through the recursion. You need to change it to more of an If (..) else if (...) else (...)

Upvotes: 3

Related Questions