java - 需要有关 Quadtrees java 的帮助

Question

我一直在寻找在我的 2D 模拟中实现四叉树的方法，以使碰撞检测更快，但我发现这个概念很难掌握。sim 运行良好，因为它现在只是一旦我超过 160-180 个粒子，它就会变得非常慢，因为碰撞检测绝对不必要地通过所有粒子并且非常愚蠢。现在它只是一堆或圆圈在屏幕上相互碰撞，我可以通过单击并拖动鼠标以新的速度和位置生成新的圆圈。

edit1:

好吧，我想我现在可以创建树了，正如您在图片中看到的那样

我的四叉 TreeMap 像:http://i.stack.imgur.com/c4WNz.jpg

所以现在的问题是如何让它对我的碰撞检测有用...

我每次检查时都必须从零开始创建整棵树吗？

我在等待期间要做的事情，希望它在某种程度上是正确的 :P

1_检查每个节点中是否有球，如果没有则将该节点排除在外。2_继续检查交叉点，直到我达到叶级别并将那些相交的球添加到叶节点。3_在我继续前进之前在叶节点中碰撞球？？

这是我的 QuadTreeNode 类:

public class QuadTreeNode { 
    private QuadTreeNode parent;
    private QuadTreeNode[] children;    
    private int id;
    private double x;
    private double y;
    private double width;
    private double height;

public QuadTreeNode(double x, double y, double width, double height, int id, QuadTreeNode parent){
    this.x = x;
    this.y = y;
    this.width =  width;
    this.height = height;
    this.children = new QuadTreeNode[4];
    this.id = id;
    this.parent = parent;
    //System.out.println("<x:>"+x+"<y:>"+y+"<w:>"+width+"<h:>"+height);     
    if (this.width>=1000/12 && this!=null){
        nodes+=1;
        this.children[0] = new QuadTreeNode(x, y, width/2, height/2, id+1, this);
        this.children[1] = new QuadTreeNode(x + width/2, y, width/2, height/2, id+2, this);
        this.children[2] = new QuadTreeNode(x, y + height/2, width/2, height/2, id+3, this);
        this.children[3] = new QuadTreeNode(x + width/2, y + height/2, width/2, height/2, id+4, this);
    }
}

Answer 1

I find the concept quite hard to grasp

想法:

• 单元格的递归分区，因为:

  • 单元格包含固定数量的基元。
  • 出现最大分区数。

• 从整个场景的边界框开始。

• 递归:如果单元格中有太多基元，则划分单元格。
• 如果房间是空的则不划分(自适应分区)
• 几何所在的精分割区。

提示:由于层次结构中的许多上下移动，遍历相对昂贵。

• 将基元保存在内部节点或叶子中。

遍历:- 使用根的轴对齐边界框进行测试(首先:整个场景)

提示:第一个命中不可能是最近的。

简而言之，这就是四叉树或八叉树 (3D) 的原理。我这里有一张 cg 幻灯片，用图片描述了它，但我不想全部上传。我认为那不是您问题的完整答案，但也许会有所帮助。