# QuadTree-Javascript

**Repository Path**: youjiawei598/quad-tree-javascript

## Basic Information

- **Project Name**: QuadTree-Javascript
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: MulanPSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-12-06
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# QuadTree-JS版本

![gif](https://edu478.oss-cn-hangzhou.aliyuncs.com/2020/12/06/52ea5cf56fef4762b9156e374fb37d30quadTree.gif)

## 交互参数

1、控制每个cell中物体的数量
2、控制划分的深度
```
MAX_OBJECT = 3; // 默认每个cell中3个物体
MAX_LEVEL = 5; // 默认划分深度5
```

## 功能函数简介
### 1. `clear()`

主要负责在绘制每一帧的时候清空上一帧的四叉树状态。

### 2. `split()`

把空间划分为4个区域。

### 3. `getIndex()`

获取物体在空间中所在的象限，如果正好在分界线上返回`-1`。

### 4. `insert()`

把物体插入所在象限的四叉树节点中，如果位于象限分界线上，则插入父节点。

### 5. `queryQuadTree()`

遍历四叉树，返回四叉树每个节点中物体数组。

## 基本使用方式：
```
// 清空四叉树状态
quad.clear();

// 构造四叉树，时间复杂度O(n * log(n))
for (let i = 0; i < objects.length; i++) {
  quad.insert(objects[i]);
}

// 返回当前物体可能发生交互的相邻物体集合
// curObj为当前输入的物体包围盒(或直接为物体)
if(curObj != null){
  let result = quad.queryQuadTree([],curObj);
  //console.log(result);
}
```

## 参考资料
[1] <a href="https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374"> Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space</a>