/**

*?四叉樹(基于2D平面空間分割)數據結構

*?四叉樹或四元樹也被稱為Q樹(Q-Tree)。

*?四叉樹廣泛應用于圖像處理、空間數據索引、2D中的快速碰撞檢測、存儲稀疏數據等

*?為提升性能

*?1、廣度優先搜索

*?2、僅搜索葉節點

*/

export?class?QuadTree?{

/**?樹的高度?*/

protected?_height:?number;

/**?樹的深度?*/

protected?_depth:?number;

/**?根節點?*/

protected?_rootNode:?QuadTreeNode;

/**?矩形區域?*/

protected?_rect:?Rectangle;

/**?廣度搜索隊列(僅包含葉節點)?*/

public?breadthSearchQueue:?Queue>;

/**?對象與葉節點的映射表?*/

public?targetNodeMap:?HashTable>;

/**

*?構造函數

*?@param?rect?二維空間數據

*?@param?depth?樹的深度

*/

constructor(rect:?Rectangle,?depth:?number,?targets?:?T[])?{

this._rect?=?rect;

this._depth?=?depth;

this._height?=?this._depth;

this.breadthSearchQueue?=?new?Queue>();

this.targetNodeMap?=?new?HashTable>();

if?(depth?>=?0)?{

this._rootNode?=?new?QuadTreeNode(this,?null,?rect,?depth);

}

this.initBreadthSearchQueue();

}

/**

*?創建廣度搜索隊列

*?僅包含葉節點

*/

protected?initBreadthSearchQueue():?void?{

let?node:?QuadTreeNode;

let?findFromLeft?=?function(nodes:?QuadTreeNode[])?{

if?(nodes.length?<=?0)?{

return;

}

let?childsArr?=?[];

//?先遍歷鄰節點

for?(let?i?=?0;?i?

node?=?nodes[i];

if?(node.isLeaf())?{

this.breadthSearchQueue.push(node);

}

childsArr?=?childsArr.concat(node.getChildsAsArray());

}

//?再訪問子節點數組

findFromLeft(childsArr);

}.bind(this);

findFromLeft([this._rootNode]);

}

//?/**

//??*?綁定對象集合

//??*/

//?public?bindTargets(targets:?T[]):?void?{

//?????for?(let?i?=?0;?i?

//?????????const?target?=?targets[i];

//?????????let?node?=?this.find(target["x"],?target["y"]);

//?????????if?(node)?{

//?????????????this.targetNodeMap.insert(target["hashCode"],?node,?true);

//?????????}else?{

//?????????????console.debug(this,?"未找到關聯的節點1",?target["x"],?target["y"],?this._rootNode);

//?????????}

//?????}

//?}

/**

*?獲取對象所屬節點

*/

public?getTargetNode(target:?T):?QuadTreeNode?{

//?LogUtils.debug(this,?"狀態表",?target["x"],?target["y"],?this.targetNodeMap.get(target["hashCode"]));

return?this.targetNodeMap.get(target["hashCode"]);

}

/**

*?獲取所有對象合集

*/

public?get?targets():?T[]?{

return?this._rootNode.targets;

}

/**

*?獲取樹的高度

*/

public?get?height():?number?{

return?this._height;

}

/**

*?獲取樹的深度

*/

public?get?depth():?number?{

return?this._depth;

}

/**

*?搜索目標對象所在區域節點

*?@param?x?目標對象x坐標

*?@param?y?目標對象y坐標

*?@param?skipEmpty?是否忽略空數據節點

*/

public?find(x:?number,?y:?number,?skipEmpty:?boolean?=?false):?QuadTreeNode?{

let?node:?QuadTreeNode?=?null;

let?findFromNode:?Function?=?(pNode:?QuadTreeNode):?QuadTreeNode?=>?{

if?(!pNode)?{

return?null;

}

if?(skipEmpty?&&?pNode.isDataEmpty)?{

return?null;

}

if?(!pNode.isContains(x,?y))?{

return?null;

}

if?(pNode.isLeaf())?{

return?pNode;

}

let?leftChild?=?pNode.getLeftChild();

while?(leftChild)?{

node?=?findFromNode(leftChild);

if?(node)?{

return?node;

}else?{

leftChild?=?leftChild.nextNode;

}

}

};

//?從根節點開始查找

return?findFromNode(this._rootNode);

}

/**

*?搜索圓形目標對象所在樹根區域節點

*?@param?x?目標對象x坐標

*?@param?y?目標對象y坐標

*?@param?skipEmpty?是否忽略空數據節點

*/

public?findNodesInCircle(x:?number,?y:?number,?radius:?number,?skipEmpty:?boolean?=?false):?QuadTreeNode[]?{

let?nodes:?QuadTreeNode[]?=?[];

let?findFromNode:?Function?=?(pNode:?QuadTreeNode):?QuadTreeNode?=>?{

if?(!pNode)?{

return?null;

}

if?(skipEmpty?&&?pNode.isDataEmpty)?{

return?null;

}

if?(pNode.isLeaf())?{

if?(BaseTool.isPointsInCircle(x,?y,?radius,?[pNode.leftTop.x,?pNode.leftTop.y,?pNode.leftBottom.x,?pNode.leftBottom.y,

pNode.rightBottom.x,?pNode.rightBottom.y,?pNode.rightTop.x,?pNode.rightTop.y]))?{

nodes.push(pNode);

}

return;

}

let?leftChild?=?pNode.getLeftChild();

while?(leftChild)?{

findFromNode(leftChild);

leftChild?=?leftChild.nextNode;

}

};

//?從根節點開始查找

findFromNode(this._rootNode);

return?nodes;

}

/**

*?搜索矩形目標對象所在樹根區域節點

*?@param?x?目標對象x坐標

*?@param?y?目標對象y坐標

*?@param?width?目標對象寬

*?@param?height?目標對象高

*?@param?skipEmpty?是否忽略空數據節點

*/

public?findNodesInRect(x:?number,?y:?number,?width:?number,?height:?number,?skipEmpty:?boolean?=?false):?QuadTreeNode[]?{

let?nodes:?QuadTreeNode[]?=?[];

let?findFromNode:?Function?=?(pNode:?QuadTreeNode):?QuadTreeNode?=>?{

if?(!pNode)?{

return?null;

}

if?(skipEmpty?&&?pNode.isDataEmpty)?{

return?null;

}

//?if?(pNode.isLeaf())?{

//?????if?(BaseTool.isRectIntersect(x,?y,?width,?height,?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height))?{

//?????????nodes.push(pNode);

//?????}

//?????return;

//?}

if?(BaseTool.isRectIntersect(x,?y,?width,?height,?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height))?{

if?(pNode.isLeaf())?{

nodes.push(pNode);

}else?{

let?leftChild?=?pNode.getLeftChild();

while?(leftChild)?{

findFromNode(leftChild);

leftChild?=?leftChild.nextNode;

}

}

}else?{

//?console.log("不相交====",?x,?y,?width,?height,?"///",?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height);

}

};

//?從根節點開始查找

findFromNode(this._rootNode);

return?nodes;

}

/**

*?搜索凸多邊形目標對象所在樹根區域節點

*?@param?x?目標對象x坐標

*?@param?y?目標對象y坐標

*?@param?width?目標對象寬

*?@param?height?目標對象高

*?@param?skipEmpty?是否忽略空數據節點

*/

public?findNodesInPolygon(polygonPoints:?number[],?skipEmpty:?boolean?=?false):?QuadTreeNode[]?{

let?nodes:?QuadTreeNode[]?=?[];

let?findFromNode:?Function?=?(pNode:?QuadTreeNode):?QuadTreeNode?=>?{

if?(!pNode)?{

return?null;

}

if?(skipEmpty?&&?pNode.isDataEmpty)?{

return?null;

}

//?if?(pNode.isLeaf())?{

//?????if?(BaseTool.isRectIntersect(x,?y,?width,?height,?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height))?{

//?????????nodes.push(pNode);

//?????}

//?????return;

//?}

if?(BaseTool.isPointsInRect(pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height,?polygonPoints))?{

if?(pNode.isLeaf())?{

nodes.push(pNode);

}else?{

let?leftChild?=?pNode.getLeftChild();

while?(leftChild)?{

findFromNode(leftChild);

leftChild?=?leftChild.nextNode;

}

}

}else?{

//?console.log("不相交====",?x,?y,?width,?height,?"///",?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height);

}

};

//?從根節點開始查找

findFromNode(this._rootNode);

return?nodes;

}

/**

*?搜索橢圓形目標對象所在樹根區域節點

*?@param?cx?橢圓中心x坐標

*?@param?cy?橢圓中心y坐標

*?@param?rx?橢圓橫半軸

*?@param?ry?橢圓縱半軸

*?@param?angle?旋轉角度

*?@param?skipEmpty?是否忽略空數據節點

*/

public?findNodesInEllipse(cx:?number,?cy:?number,?rx:?number,?ry:?number,?angle:?number,?skipEmpty:?boolean?=?false):?QuadTreeNode[]?{

let?nodes:?QuadTreeNode[]?=?[];

let?findFromNode:?Function?=?(pNode:?QuadTreeNode):?QuadTreeNode?=>?{

if?(!pNode)?{

return?null;

}

if?(skipEmpty?&&?pNode.isDataEmpty)?{

return?null;

}

//?if?(pNode.isLeaf())?{

//?????if?(BaseTool.isRectIntersect(x,?y,?width,?height,?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height))?{

//?????????nodes.push(pNode);

//?????}

//?????return;

//?}

if?(BaseTool.isRectIntersectEllipse(pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height,?cx,?cy,?rx,?ry,?angle))?{

if?(pNode.isLeaf())?{

nodes.push(pNode);

}else?{

let?leftChild?=?pNode.getLeftChild();

while?(leftChild)?{

findFromNode(leftChild);

leftChild?=?leftChild.nextNode;

}

}

}else?{

//?console.log("不相交====",?x,?y,?width,?height,?"///",?pNode.rect.x,?pNode.rect.y,?pNode.rect.width,?pNode.rect.height);

}

};

//?從根節點開始查找

findFromNode(this._rootNode);

return?nodes;

}

/**

*?對象坐標發生更新的通知

*/

public?onTargetPosUpdate(target:?T):?void?{

//?let?x?=?target["x"];

//?let?y?=?target["y"];

//?let?curNode?=?this.targetNodeMap.get(target["hashCode"]);

//?if?(curNode?&&?curNode.isContains(x,?y))?{

//?????return;

//?}else?{

//?????let?node?=?this.find(x,?y);

//?????if?(node)?{

//?????????this.targetNodeMap.insert(target["hashCode"],?node,?true);

//?????????this._onTargetNodeChanged(target,?curNode,?node);

//?????}else?{

//?????????console.debug(this,?"未找到關聯的節點2",?x,?y,?this._rootNode);

//?????}

//?}

}

/**

*?通知對象?節點發生切換

*/

public?_onTargetNodeChanged(target:?T,?oldNode:?QuadTreeNode,?newNode:?QuadTreeNode):?void?{

if?(oldNode)?{

oldNode.removeTarget(target);

}

if?(newNode)?{

newNode.addTarget(target);

}

if?(target["onTreeNodeChanged"])?{

target["onTreeNodeChanged"](oldNode,?newNode);

}

}

}

總結

以上是生活随笔為你收集整理的mysql 四叉树的应用_游戏算法（2）：查找优化之四叉树的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。