我在做一个四叉树和需要帮助插入对象进去。我理解这样做的概念，但我不是伟大的递归和Java将变量传递的方式。

我有一个包含一个称为根节点四叉树类。节点类有它内部的四个节点，这是四个四边形的补回来。在创建四叉树的根节点被创建，而不是创建的每个节点内的四个节点，直到我打电话createChildrenQuads（）。然而，对于根节点，该方法是在创建四叉树叫。

所以，我如何插入一个项目到一个节点的思维过程是这样的：

开始在根节点 对于每个节点： 检查，看其当前节点的孩子Quad中的电流 在项目符合 如果它选择一个适合，将其插入了 节点（调用递归方法，并开始了） 如果它不适合 任何，它添加到对象的当前节点的列表，并进行

在此基础上，我创造了这个：

 公共无效插入（实体E）{
    插入（根，E）;
}

私人无效插入（节点N，实体E）{
    矩形临时= e.getRectangle（）;

    如果（！n.childrenHaveBeenCreated（））
        n.createChildrenQuads（n.m_quadRect）;

    //首先检查该节点就可以进入

    如果（n.NW.m_quadRect.contains（临时））{
        n.NW =插入（n.NW，E）;
        返回;
    }

    如果（n.NE.m_quadRect.contains（临时））{
        n.NE =插入（n.NE，E）;
        返回;
    }

    如果（n.SW.m_quadRect.contains（临时））{
        n.SW =插入（n.SW，E）;
        返回;
    }

    如果（n.SE.m_quadRect.contains（临时））{
        n.SE =插入（n.SE，E）;
        返回;
    }

    n.m_objects.add（E）;
}
 

我觉得四叉树明智的，逻辑我也很好。当我调试code，看起来一切正常，因为它应该。不过，我相信我的问题是Java通过传递参数值，而不是引用，所以当我在正确的位置添加它，它没有得到拯救，因为它只是一个局部变量。我认为这是问题，但我可能是错的。

所以，我试图改变这一点，以让这个插入方法返回当前节点，让一切都应该得到正确的拯救。这就是我想出了：

 公共无效插入（实体E）{
    根=插入（根，E）;
}

私人节点插入（节点N，实体E）{
    矩形临时= s.getRectangle（）;

    如果（！n.childrenHaveBeenCreated（））
        n.createChildrenQuads（n.m_quadRect）;

    //首先检查该节点就可以进入

    如果（n.NW.m_quadRect.contains（临时））{
        n.NW =插入（n.NW，E）;
        返回N;
    }

    如果（n.NE.m_quadRect.contains（临时））{
        n.NE =插入（n.NE，E）;
        返回N;
    }

    如果（n.SW.m_quadRect.contains（临时））{
        n.SW =插入（n.SW，E）;
        返回N;
    }

    如果（n.SE.m_quadRect.contains（临时））{
        n.SE =插入（n.SE，E）;
        返回N;
    }

    n.m_objects.add（E）;
    返回N;
}
 

不过，我仍然有同样的问题。现在，我不知道我的问题是。

我用这一个游戏，我有它，这样它吸引周围，所有的四边形是一个轮廓，我可以点击添加一个实体到四叉树。这两个版本的我的code似乎做得一样。会发生什么事是，当我加入一个实体的四叉树，它被添加，并保持在那里，所以我想它我的理论没有得到，因为java如何通过引用是错误的保存。

不过，我的code应（至少在我的脑海里应该）将每个实体到四叉树为低的水平，因为它可以在每个节点创建新的儿童四边形因为它的股价下跌了树。实际发生的事情虽然是，有时它似乎只是添加新的实体到当前四，不下去的树在所有，或下降一个或两个级别，就是这样，当它可以很容易地往下走了几更多的水平。

任何人都可以看到什么不对的code或我的逻辑呢？

解决方案

我觉得这是你已经结构化程序的方式。四叉树得到测试每一个象限，但它也送花儿给人增加元素在最后......所以，即使它会递归使得它的方式到海底，在回来的路上了它将始终运行最后 n.m_objects.add（E）; 因此改变在那里的道路上添加备份通过递归。您需要将其更改为更多的如果（..）否则，如果（...）否则（...）

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:

Start at the root node For each node:

Check and see which of the current node's children quad the current item fits in If it fits in one of them, insert it into that node(call the recursive method and start over) 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?

解决方案

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 (...)