JS实现的四叉树算法详解

JS实现四叉树算法详解

什么是四叉树

四叉树是一种数据结构，在计算机科学中用于存储二维空间中的对象。四叉树允许管理大量对象，以便更快地进行搜索和查找操作。
四叉树的时间复杂度为 O(log n)，相对于普通的线性搜索的 O(n) 更加高效。

四叉树如何工作？

四叉树能够将二维空间分割成4个等大小的矩形，每个矩形又可以被分成4个矩形，如此递归下去，直到每个小矩形都只包含一个节点，或者小矩形的面积达到了一定的阈值。

搜索一个目标点时，四叉树可以通过类似二分查找的方式，逐步收缩搜索空间，直到找到目标点或者确定目标点不在区域内。

如何实现四叉树

我们可以使用面向对象的思想来实现四叉树。四叉树结构可以由一个QuadTree类来表示，

class QuadTree {
   constructor(bounds, capacity) {
      this.capacity = capacity;
      this.points = [];
      this.northwest = null;
      this.northeast = null;
      this.southeast = null;
      this.southwest = null;
      this.bounds = bounds;
   }
}

QuadTree类有一个容量参数（capacity），表示每个节点最多可以容纳的数据点个数。如果节点内的数据点数量大于容量，该节点将被分割成为四个子节点。bounds参数是一个边界矩形，表示该节点的范围。

插入数据时，算法会将数据点插入到四叉树最小的区域内。

QuadTree.prototype.insert = function(point) {
   // 如果点不在当前四叉树节点范围内，忽略
   if (!this.bounds.contains(point)) {
      return false;
   }

   // 达到容量限制，划分节点
   if (this.points.length < this.capacity) {
      this.points.push(point);
      return true;
   }

   // 不满足条件，划分成为四个子节点
   if (!this.northwest) {
      this.subdivide();
   }

   // 插入节点
   if (this.northwest.insert(point) || 
       this.northeast.insert(point) ||
       this.southeast.insert(point) ||
       this.southwest.insert(point)) {
      return true;
   }

   return false;
};

查询时，算法先找到相应目标的四叉树范围，然后在范围内递归查找目标点。代码如下所示：

QuadTree.prototype.query = function(range, found) {
   if (!found) {
      found = [];
   }

   if (!this.bounds.intersects(range)) {
      return found;
   }

   for (let p of this.points) {
      if (range.contains(p)) {
         found.push(p);
      }
   }

   if (this.northwest) {
      this.northwest.query(range,found);
      this.northeast.query(range,found);
      this.southeast.query(range,found);
      this.southwest.query(range,found);
   }

   return found;
};

四叉树的应用

四叉树在游戏开发、计算机图形学等领域广泛应用。比如网页上的图片热点区域检测，通过构建图片所在的四叉树图形结构，可以更快速准确地捕捉目标点信息。

示例一：划分城市地图

假设我们有一张城市地图，要将地图划分成若干区域并存储在四叉树中。其中，每个区域代表一个街区。当我们需要查询某个指定的街区时，可以快速找到该街区所在的区域，并返回相应数据。

示例二：检测众多物体碰撞

假设我们在开发一个类似于[愤怒的小鸟]的游戏，这个游戏中有大量的物体进行交互。假设这些物体都可以分解为一个一个的小点，我们可以使用四叉树来检测这些物体是否发生了碰撞。通过检测四叉树子节点的快速路径，我们可以快速查找出哪些小点之间相交并执行相应的动作。