网站建设方向论文提纲,安徽鑫华建设有限公司网站,西部数据网站建设,重庆seo排名游戏中常对物体进行空间划分#xff0c;对于均匀分布的划分一般用四叉树(八叉树)#xff0c;动态不均匀的分布可以采用kd-tree
构建kd-tree
构建思路#xff1a;
1.对节点进行各维度的方差分析#xff0c;选取方差最大(即离散程度最高)的维度进行排序。取中值节点作为分…游戏中常对物体进行空间划分对于均匀分布的划分一般用四叉树(八叉树)动态不均匀的分布可以采用kd-tree
构建kd-tree
构建思路
1.对节点进行各维度的方差分析选取方差最大(即离散程度最高)的维度进行排序。取中值节点作为分割点。并将其放入构建树的节点中2.被排序的节点按不同维度分割后划分为力左空间(划分维度下小于分割节点的值)与右空间(划分维度下大于分割节点的值)。对两个空间重复步骤1并且两个空间的分割点分别作为上一个分割点的左右子树加入构建树中。 (设置维度除了分析方差有时会选择所有维度循环设置)
树的节点的结构
struct TreeNode {int id; //节点唯一idVec2 pos;int split; //分割维度struct TreeNode* left;struct TreeNode* right;struct TreeNode* parent;
};获取分割维度
//计算所有节点各维度的方差确定分割维度
int KDTreeScene::chooseSplit(vectorVec2 posData) {float xEx1 0;float xEx2 0;float xDx 0;float size posData.size();for (auto v : posData) {xEx1 1.0 / size * v.x * v.x;xEx2 1.0 / size * v.x;}xDx xEx1 - xEx2 * xEx2;float yEx1 0;float yEx2 0;float yDx 0;for (auto v : posData) {yEx1 1.0 / size * v.y * v.y;yEx2 1.0 / size * v.y;}yDx yEx1 - yEx2 * yEx2;return xDx yDx ? 0 : 1;
}构建树
//rect是画分割线的辅助参数实际应用可无视
TreeNode* KDTreeScene::buildKdTree(vectorVec2 posData, Rect rect, int splitIdx) {if (posData.size() 0) return nullptr;int split chooseSplit(posData); //根据方差设置维度//split splitIdx; //循环设置维度if (posData.size() 1) {//空间只剩一个节点无需再划分TreeNode* TNode new TreeNode();TNode-id _id;_id;TNode-pos posData[0];TNode-left nullptr;TNode-right nullptr;TNode-split split;//根据维度画分割线drawClipLine(rect, split, posData[0]);return TNode;}int mid posData.size() / 2;vectorVec2 leftPosData;vectorVec2 rightPosData;//根据设置的维度进行排序if (split 0) sort(posData.begin(), posData.end(), cmpX); //垂直x轴分割则根据x值排序else sort(posData.begin(), posData.end(), cmpY); //垂直y轴分割则根据y值排序//获取中值作为分割点Vec2 midPos posData[mid];//小于中值的放入左空间for (int i 0; i mid; i) {leftPosData.push_back(posData[i]);}//大于中值的放入右空间for (int j mid 1; j posData.size(); j) {rightPosData.push_back(posData[j]);}//创建树的节点TreeNode* TNode new TreeNode();TNode-id _id;_id;TNode-pos midPos;drawClipLine(rect, split, midPos);// ---------------------//用来画分割线的辅助参数实际应用可无视Rect r1, r2;if (split 0) {r1 Rect(rect.getMinX(), rect.getMinY(), midPos.x - rect.getMinX(), rect.getMaxY() - rect.getMinY());r2 Rect(midPos.x, rect.getMinY(), rect.getMaxX() - midPos.x, rect.getMaxY() - rect.getMinY());}else {r1 Rect(rect.getMinX(), rect.getMinY(), rect.getMaxX() - rect.getMinX(), midPos.y - rect.getMinY());r2 Rect(rect.getMinX(), midPos.y, rect.getMaxX() - rect.getMinX(), rect.getMaxY() - midPos.y);}// ---------------------//splitIdx; //循环遍历设置维度的方法//对左空间进行kd树的构建步骤并把顶点作为当前节点的左子树TNode-left buildKdTree(leftPosData, r1, splitIdx % 2);if (TNode-left ! nullptr) TNode-left-parent TNode;//对右空间进行kd树的构建步骤并把顶点作为当前节点的右子树TNode-right buildKdTree(rightPosData, r2, splitIdx % 2);if (TNode-right ! nullptr) TNode-right-parent TNode;TNode-split split;//返回的节点为当前空间构造的kd树的顶点return TNode;
}效果演示 近邻搜寻
搜寻思路
维护一个最近邻居的优先级队列以及一个记录访问过节点的表
1.从根节点开始将目标点递归往下查询。与插入思路一样当前维度小于当前节点值的查询左子树大于当前节点值的查询右子树。直到移动到叶子节点将叶子节点进行访问。2.访问叶子节点。如果最近邻居优先级队列里的值小于所需邻居值或者该叶子节点到目标点的距离小于队列中最远的邻居节点到目标点的距离。则将该叶子节点更新到最近邻居的队列记录访问过的当前节点3.从叶子节点往上查询(获取该叶子节点的父节点或着解开递归等方式)。对父节点进行访问处理(步骤2)。如果父节点已经访问过则继续往上(重复步骤3)4.对该父节点对应维度的分割边进行距离判定 1.如果最近邻居优先级队列里的值小于所需邻居值或者目标点到分割边的垂直距离小于队列中最远的邻居节点到目标点的距离则对该父节点的另一半空间进行从步骤1开始往下的查询 2.否则直接忽略该父节点的另一半空间继续往上查询(回到步骤3)
往上的查询直到树的顶点即停止
void KDTreeScene::searchNearestPoint(Vec2 pos, TreeNode* tNode) {while (!_nearestQueue.empty()) {_nearestQueue.pop();}_searchDrawNode-clear();_exploredMap.clear();_searchDrawNode-drawDot(pos, 5, Color4F(0, 1, 0, 1));//-----------------//进入搜寻TreeNode* leaf searchLeafNode(pos, _kdTree);backCheck(pos, leaf);
//-----------------//下面是画出搜寻结果while (!_nearestQueue.empty()) {_searchDrawNode-drawDot(_nearestQueue.top().second-pos, 5, Color4F(0, 0, 0, 1));if (_model) {delete _nearestQueue.top().second;}_nearestQueue.pop();}
}访问对应节点
上述步骤2
bool KDTreeScene::checkInsertQueue(Vec2 pos, TreeNode* tNode) {//记录以访问过的节点_exploredMap[tNode-id] true;//_searchNode是需要获取的最近邻居节点数//近邻居优先级队列里的值小于所需邻居值则直接插入队列if (_nearestQueue.size() _searchNode) {_nearestQueue.emplace(pos.getDistance(tNode-pos), tNode);return true;}else {auto data _nearestQueue.top();float dist pos.getDistance(tNode-pos);//该叶子节点到目标点的距离小于队列中最远的邻居节点到目标点的距离则更新队列if (dist data.first) {_nearestQueue.pop();_nearestQueue.emplace(dist, tNode);return true;}}return false;
}递归查询到叶节点
上述步骤1
TreeNode* KDTreeScene::searchLeafNode(Vec2 pos, TreeNode* tNode) {if (tNode-split 0) {if (pos.x tNode-pos.x) {if (tNode-left nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-left);}else {if (tNode-right nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-right);}}else {if (pos.y tNode-pos.y) {if (tNode-left nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-left);}else {if (tNode-right nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-right);}}
}往上查询
上述步骤3和4
void KDTreeScene::backCheck(Vec2 pos, TreeNode* tNode) {//到顶点停止if (tNode-parent nullptr) {return;}else {//步骤3tNode tNode-parent;//已经访问过的节点直接跳过往上查询if (!_exploredMap[tNode-id]) {//访问父节点checkInsertQueue(pos, tNode);if (tNode-split 0) {//步骤4if (_nearestQueue.size() _searchNode || abs(pos.x - tNode-pos.x) _nearestQueue.top().first) {//步骤4 情况1//----------------------if (pos.x tNode-pos.x) {if(tNode-right) tNode searchLeafNode(pos, tNode-right);}else {if (tNode-left) tNode searchLeafNode(pos, tNode-left);}//----------------------}}else {if (_nearestQueue.size() _searchNode || abs(pos.y - tNode-pos.y) _nearestQueue.top().first) {if (pos.y tNode-pos.y) {if (tNode-right) tNode searchLeafNode(pos, tNode-right);}else {if (tNode-left) tNode searchLeafNode(pos, tNode-left);}}}}backCheck(pos, tNode);}
}
效果演示 完整效果
以下是对2000个物体查询最近的6个邻居的效果
对比了下对所有物体进行遍历找寻最近值的方式 搜寻3个最近物体时在1000个时差不多开始出现1ms的延迟在5000个3到4ms内的延迟在10000个时7ms延迟, 在100000时70ms延迟 就是成正比的延迟 而kd树的查询到10000000仍是0因为是类似二叉树的log的复杂度 主要耗时在构造树1000个物体差不多5ms5000个物体30ms10000个物体50ms100000个物体550ms1000000个物体6400ms5000000个物体37000ms10000000个物体76000ms差不多也是正比 不同机器效率不同但是趋势一样
代码
KDTreeScene.h
#ifndef __KDTREE_SCENE_H__
#define __KDTREE_SCENE_H__#include cocos2d.h
USING_NS_CC;
using namespace std;struct TreeNode {int id;Vec2 pos;int split;struct TreeNode* left;struct TreeNode* right;struct TreeNode* parent;
};struct cmp {bool operator()(pairfloat, TreeNode* a, pairfloat, TreeNode* b) {return a.first b.first;}
};class KDTreeScene : public Scene
{
public:static Scene* createScene();virtual bool init();virtual bool onTouchBegan(Touch* touch, Event* unused_event);TreeNode* buildKdTree(vectorVec2 posData, Rect rect, int splitIdx);int chooseSplit(vectorVec2 posData);void drawClipLine(Rect rect, int split, Vec2 pos);void searchNearestPoint(Vec2 pos, TreeNode* tNode);TreeNode* searchLeafNode(Vec2 pos, TreeNode* tNode);void backCheck(Vec2 pos, TreeNode* tNode);bool checkInsertQueue(Vec2 pos, TreeNode* tNode);// implement the static create() method manuallyCREATE_FUNC(KDTreeScene);void update(float dt);protected:EventListenerTouchOneByOne* _touchListener;Vec2 _touchBeganPosition;DrawNode* _mapDrawNode;DrawNode* _clipDrawNode;vectorVec2 _posData;TreeNode* _kdTree;bool _isDrawSplitLine false;DrawNode* _searchDrawNode;int _searchNode 6;priority_queuepairfloat, TreeNode*, vectorpairfloat, TreeNode*, cmp _nearestQueue;int _id;unordered_mapint, bool _exploredMap;bool _model false;
};#endif
KDTreeScene.cpp
#include KDTreeScene.h
#include chrono
using namespace std::chrono;Scene* KDTreeScene::createScene()
{return KDTreeScene::create();
}static void problemLoading(const char* filename)
{printf(Error while loading: %s\n, filename);printf(Depending on how you compiled you might have to add Resources/ in front of filenames in KDTreeScene.cpp\n);
}// on init you need to initialize your instance
bool KDTreeScene::init()
{//// 1. super init firstif (!Scene::init()){return false;}auto visibleSize Director::getInstance()-getVisibleSize();Vec2 origin Director::getInstance()-getVisibleOrigin();auto layer LayerColor::create(Color4B(255, 255, 255, 255));
layer:setContentSize(visibleSize);this-addChild(layer);_clipDrawNode DrawNode::create();this-addChild(_clipDrawNode);_mapDrawNode DrawNode::create();this-addChild(_mapDrawNode);_searchDrawNode DrawNode::create();this-addChild(_searchDrawNode);auto drawNode DrawNode::create();this-addChild(drawNode);auto vecData vectorVec2{ Vec2::ZERO, Vec2(100,0), Vec2(100,640), Vec2(0,640) };Vec2* ptr reinterpret_castVec2*(vecData.data());drawNode-drawPolygon(ptr, vecData.size(), Color4F(0, 0, 0, 1), 0, Color4F(0, 0, 0, 0));auto vecData1 vectorVec2{ Vec2(1300,0), Vec2(1400,0), Vec2(1400,640), Vec2(1300,640) };Vec2* ptr1 reinterpret_castVec2*(vecData1.data());drawNode-drawPolygon(ptr1, vecData1.size(), Color4F(0, 0, 0, 1), 0, Color4F(0, 0, 0, 0));_touchListener EventListenerTouchOneByOne::create();_touchListener-setSwallowTouches(true);_touchListener-onTouchBegan CC_CALLBACK_2(KDTreeScene::onTouchBegan, this);this-getEventDispatcher()-addEventListenerWithSceneGraphPriority(_touchListener, layer);this-scheduleUpdate();return true;
}bool KDTreeScene::onTouchBegan(Touch* touch, Event* event)
{_touchBeganPosition touch-getLocation();CCLOG(xxxxxxxxx %f? %f, _touchBeganPosition.x, _touchBeganPosition.y);if (_touchBeganPosition.x 100) {_posData.clear();_mapDrawNode-clear();_clipDrawNode-clear();_searchDrawNode-clear();_id 1;for (int i 0; i 5000000; i) {float x RandomHelper::random_realfloat(100, 1300);float y RandomHelper::random_realfloat(0, 640);_posData.push_back(Vec2(x, y));
// _mapDrawNode-drawDot(Vec2(x, y), 3, Color4F(0, 1, 1, 1));}auto last std::chrono::system_clock::now();auto timestamp std::chrono::time_point_caststd::chrono::milliseconds(last).time_since_epoch().count();_kdTree buildKdTree(_posData, Rect(0, 0, 1400, 640), 0);_kdTree-parent nullptr;auto now std::chrono::system_clock::now();auto timestamp1 std::chrono::time_point_caststd::chrono::milliseconds(now).time_since_epoch().count();CCLOG(build timestamp dif %d, timestamp1 - timestamp);}else if (_touchBeganPosition.x 1300) {_model !_model;}else {if (_posData.empty()) {_id 1;for (int i 0; i 2000; i) {float x RandomHelper::random_realfloat(100, 1300);float y RandomHelper::random_realfloat(0, 640);_posData.push_back(Vec2(x, y));
// _mapDrawNode-drawDot(Vec2(x, y), 3, Color4F(0, 1, 1, 1));}auto last std::chrono::system_clock::now();auto timestamp std::chrono::time_point_caststd::chrono::milliseconds(last).time_since_epoch().count();_kdTree buildKdTree(_posData, Rect(0, 0, 1400, 640), 0);_kdTree-parent nullptr;auto now std::chrono::system_clock::now();auto timestamp1 std::chrono::time_point_caststd::chrono::milliseconds(now).time_since_epoch().count();CCLOG(build timestamp dif %d, timestamp1 - timestamp);return true;}searchNearestPoint(_touchBeganPosition, _kdTree);}return true;
}void KDTreeScene::update(float dt) {}bool cmpX(Vec2 a, Vec2 b) {return a.x b.x;
}bool cmpY(Vec2 a, Vec2 b) {return a.y b.y;
}int KDTreeScene::chooseSplit(vectorVec2 posData) {float xEx1 0;float xEx2 0;float xDx 0;float size posData.size();for (auto v : posData) {xEx1 1.0 / size * v.x * v.x;xEx2 1.0 / size * v.x;}xDx xEx1 - xEx2 * xEx2;float yEx1 0;float yEx2 0;float yDx 0;for (auto v : posData) {yEx1 1.0 / size * v.y * v.y;yEx2 1.0 / size * v.y;}yDx yEx1 - yEx2 * yEx2;return xDx yDx ? 0 : 1;
}TreeNode* KDTreeScene::buildKdTree(vectorVec2 posData, Rect rect, int splitIdx) {if (posData.size() 0) return nullptr;int split chooseSplit(posData);//split splitIdx;if (posData.size() 1) {TreeNode* TNode new TreeNode();TNode-id _id;_id;TNode-pos posData[0];TNode-left nullptr;TNode-right nullptr;TNode-split split;drawClipLine(rect, split, posData[0]);return TNode;}int mid posData.size() / 2;vectorVec2 leftPosData;vectorVec2 rightPosData;if (split 0) sort(posData.begin(), posData.end(), cmpX);else sort(posData.begin(), posData.end(), cmpY);Vec2 midPos posData[mid];for (int i 0; i mid; i) {leftPosData.push_back(posData[i]);}for (int j mid 1; j posData.size(); j) {rightPosData.push_back(posData[j]);}TreeNode* TNode new TreeNode();TNode-id _id;_id;TNode-pos midPos;drawClipLine(rect, split, midPos);Rect r1, r2;if (split 0) {r1 Rect(rect.getMinX(), rect.getMinY(), midPos.x - rect.getMinX(), rect.getMaxY() - rect.getMinY());r2 Rect(midPos.x, rect.getMinY(), rect.getMaxX() - midPos.x, rect.getMaxY() - rect.getMinY());}else {r1 Rect(rect.getMinX(), rect.getMinY(), rect.getMaxX() - rect.getMinX(), midPos.y - rect.getMinY());r2 Rect(rect.getMinX(), midPos.y, rect.getMaxX() - rect.getMinX(), rect.getMaxY() - midPos.y);}splitIdx;TNode-left buildKdTree(leftPosData, r1, splitIdx % 2);if (TNode-left ! nullptr) TNode-left-parent TNode;TNode-right buildKdTree(rightPosData, r2, splitIdx % 2);if (TNode-right ! nullptr) TNode-right-parent TNode;TNode-split split;return TNode;
}void KDTreeScene::drawClipLine(Rect rect, int split, Vec2 pos) {
// if (split 0) {
// _clipDrawNode-drawSegment(Vec2(pos.x, rect.getMinY()), Vec2(pos.x, rect.getMaxY()), 1, Color4F(1, 0, 0, 0.5));
// }
// else {
// _clipDrawNode-drawSegment(Vec2(rect.getMinX(), pos.y), Vec2(rect.getMaxX(), pos.y), 1, Color4F(0, 0, 1, 0.5));
// }
}void KDTreeScene::searchNearestPoint(Vec2 pos, TreeNode* tNode) {while (!_nearestQueue.empty()) {_nearestQueue.pop();}_searchDrawNode-clear();_exploredMap.clear();_searchDrawNode-drawDot(pos, 3, Color4F(1, 0, 0, 1));auto last std::chrono::system_clock::now();auto timestamp std::chrono::time_point_caststd::chrono::milliseconds(last).time_since_epoch().count();if (_model) {for (auto p : _posData) {TreeNode* t new TreeNode();t-id _id;_id;t-pos p;checkInsertQueue(pos, t);}}else {TreeNode* leaf searchLeafNode(pos, _kdTree);backCheck(pos, leaf);}auto now std::chrono::system_clock::now();auto timestamp1 std::chrono::time_point_caststd::chrono::milliseconds(now).time_since_epoch().count();CCLOG(search timestamp dif %d, timestamp1 - timestamp);while (!_nearestQueue.empty()) {_searchDrawNode-drawDot(_nearestQueue.top().second-pos, 3, Color4F(0, 0, 0, 1));if (_model) {delete _nearestQueue.top().second;}_nearestQueue.pop();}
}bool KDTreeScene::checkInsertQueue(Vec2 pos, TreeNode* tNode) {_exploredMap[tNode-id] true;if (_nearestQueue.size() _searchNode) {_nearestQueue.emplace(pos.getDistance(tNode-pos), tNode);return true;}else {auto data _nearestQueue.top();float dist pos.getDistance(tNode-pos);if (dist data.first) {_nearestQueue.pop();_nearestQueue.emplace(dist, tNode);return true;}}return false;
}TreeNode* KDTreeScene::searchLeafNode(Vec2 pos, TreeNode* tNode) {if (tNode-split 0) {if (pos.x tNode-pos.x) {if (tNode-left nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-left);}else {if (tNode-right nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-right);}}else {if (pos.y tNode-pos.y) {if (tNode-left nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-left);}else {if (tNode-right nullptr) {checkInsertQueue(pos, tNode);return tNode;}else return searchLeafNode(pos, tNode-right);}}
}void KDTreeScene::backCheck(Vec2 pos, TreeNode* tNode) {if (tNode-parent nullptr) {return;}else {tNode tNode-parent;if (!_exploredMap[tNode-id]) {checkInsertQueue(pos, tNode);if (tNode-split 0) {if (_nearestQueue.size() _searchNode || abs(pos.x - tNode-pos.x) _nearestQueue.top().first) {if (pos.x tNode-pos.x) {if(tNode-right) tNode searchLeafNode(pos, tNode-right);}else {if (tNode-left) tNode searchLeafNode(pos, tNode-left);}}}else {if (_nearestQueue.size() _searchNode || abs(pos.y - tNode-pos.y) _nearestQueue.top().first) {if (pos.y tNode-pos.y) {if (tNode-right) tNode searchLeafNode(pos, tNode-right);}else {if (tNode-left) tNode searchLeafNode(pos, tNode-left);}}}}backCheck(pos, tNode);}
}
