2

我正在制作四叉树，需要帮助将对象插入其中。我理解这样做的概念，但我不擅长递归和 Java 传递变量的方式。

我有一个 Quadtree 类，其中包含一个名为 root 的节点。Node 类内部有四个 Node，它们是组成它的四个四边形。创建四叉树时会创建根节点，并且在调用 createChildrenQuads() 之前不会创建每个节点内的四个节点。但是，对于根节点，在创建四叉树时会调用该方法。

所以我关于如何将项目插入节点的思考过程是这样的：

  1. 从根节点开始
  2. 对于每个节点：
    1. 检查并查看当前项目适合当前节点的哪个子节点
    2. 如果它适合其中一个，则将其插入该节点（调用递归方法并重新开始）
    3. 如果它不适合任何东西，请将其添加到当前节点的对象列表中并完成

基于此，我创建了这个：

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

我认为在四叉树方面，我的逻辑很好。当我调试代码时，看起来一切正常。但是，我相信我的问题是 Java 通过值而不是引用传递参数，所以当我将它添加到正确的位置时，它并没有得到“保存”，因为它只是一个局部变量。我相信这是问题所在，但我可能是错的。

所以我尝试对其进行一些更改以使其插入方法返回当前节点，以便所有内容都应该正确“保存”。这就是我想出的：

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

但是，我仍然有同样的问题。现在我不确定我的问题是什么。

我正在将它用于游戏，并且我拥有它以便它在所有四边形所在的位置绘制轮廓，并且我可以单击以将实体添加到四叉树中。我的代码的两个版本似乎都是一样的。发生的情况是，当我将实体添加到四叉树时，它会被添加并保留在那里，所以我猜我关于它没有得到“保存”的理论是因为 Java 传递引用的方式是错误的。

但是，我的代码应该（至少在我的脑海中应该）将每个实体放入四叉树中尽可能低的级别，在每个节点沿着树向下时在每个节点中创建新的子四边形。但实际发生的情况是，有时它似乎只是将新实体添加到当前四边形中，根本不下树，或者它下降一两个级别，就是这样，当它很容易下降几个更多级别。

任何人都可以看到代码或我的逻辑有什么问题吗？

4

1 回答 1

3

我认为这是您构建程序的方式。四叉树可以测试每个象限，但它也总是在最后添加元素......所以即使它会递归地到达底部，在备份的路上它总是会运行你的最后一个n.m_objects.add(e); 因此改变它的位置在通过递归备份的路上添加。您需要将其更改为更多If (..) else if (...) else (...)

于 2011-10-20T01:08:52.557 回答