quadtree.java

java learn PPT java learn PPT java learn PPT java learn PPT

     import java.awt.*;
     import java.awt.geom.*;
     import java.util.*;

     // QuadTree管理方式的根结点
     public class QuadTree extends QuadNode
     {
          // 树的总体深度
          protected int globalDepth;

          // 全局的叶子节点链表
          public static LinkedList leaves = new LinkedList();

          // 将被绘制的物体的全局链表
          public static LinkedList paintList = new LinkedList();

          // 用传入的深度、总体边界和可见屏幕边界创建一个QuadTree
          public QuadTree(int depth, Rectangle2D r)
          {
               super(null, depth, r);

               // 总体深度必须比零大
               if(depth <= 0)
               {
                    throw new IllegalArgumentException("depth must be greater than zero");
               }

               globalDepth = depth;
              
               // 初始化溢出链表
               objects = new LinkedList();
          }

          // 在全局叶子链表中添加一个叶子节点
          public static void addLeaf(QuadNode node)
          {
               if(! leaves.contains(node))
               {
                    leaves.add(node);
               }
          }

          // 在全局绘制链表中添加一个Moveable物体
          public static void addToPaintList(Moveable m)
          {
               if(! paintList.contains(m))
               {
                    paintList.add(m);
               }
          }

          // QuadTree 必须覆盖insert方法来处理不在场景边界中的物体
          public void insert(Moveable c)
          {
               // 如果物体不在场景边界中,则把它添加到堆中
               if(! bounds.contains(c.getBounds()) && ! bounds.intersects(c.getBounds()))
               {
                    if(! objects.contains(c))
                    {
                         objects.add(c);
                    }
                    return;
               }

               // 将物体添加到全局绘制链表中
               addToPaintList(c);

               // 试图将物体添加到所有的孩子节点中去
               for(int i = 0; i < 4; i++)
               {
                    if(nodes[i] != null)
                    {
                         nodes[i].insert(c, false);
                    }
               }
          } 

          public void update()
          {
               //  更新堆链表
               if(objects != null && !objects.isEmpty()) 
               {
                    for(int i = 0; i < objects.size(); i++)
                    {
                         Moveable a = (Moveable) objects.get(i);
                         a.update();
  
                         // 检查物体是否进入树中;如果是则添加它,并将它从堆中删除
                         if(bounds.contains(a.getBounds()) || bounds.intersects(a.getBounds()))
                         {
                              insert((Moveable) objects.remove(i), false);
                         }
                     }
               }

               //  堆所有叶子节点检查冲突和帧移动
               for(int i = 0; i < leaves.size(); i++) 
               {
                    ((QuadNode) leaves.get(i)).update();
               }
          }

          // 绘制全局绘制链表中的所有物体            
          public void paint(Graphics2D g2d)
          {
               Actor2D a;
               for(int i = 0; i < paintList.size(); i++)
               {
                    a = (Actor2D) paintList.get(i);
                    // 只有物体在边界中才绘制物体
                    if(bounds.contains(a.getBounds()) || bounds.intersects(a.getBounds())) 
                    {
                         a.paint(g2d);     
                    }
               }
          }

          // paints gridlines showing the bounds of each leaf node
          public void paintBounds(Graphics2D g2d, Color color)
          {
               // 绘制所有的叶子结点
               for(int i = 0; i < leaves.size(); i++)
               {
                    ((QuadNode)leaves.get(i)).paintBounds(g2d, color);
               }
          }

     }    // QuadTree