怎么给网站做关键词排名百度一键优化

当前位置： 首页 > news >正文

怎么给网站做关键词排名,百度一键优化,跨境电商erp软件排名,WordPress创建简码介绍 K-D树是一种二叉树的数据结构#xff0c;其中每个节点代表一个k维点#xff0c;可用于组织K维空间中的点#xff0c;其中K通常是一个非常大的数字。二叉树结构允许对多维空间中的点进行非常有效的搜索#xff0c;包括最近邻搜索和范围搜索#xff0c;树中的每个非叶… 介绍 K-D树是一种二叉树的数据结构其中每个节点代表一个k维点可用于组织K维空间中的点其中K通常是一个非常大的数字。二叉树结构允许对多维空间中的点进行非常有效的搜索包括最近邻搜索和范围搜索树中的每个非叶节点都充当一个超平面将空间分割为两个区域。 这个超平面垂直于所选的轴该轴与K维相关联。 而区域在划分时有不同的选择轴的策略 划分轴策略 1.按深度划分 说明 重复地循环K维中的每一个轴并选择沿着它的中点来划分空间。例如对于具有和轴的二维点xy我们首先沿着x-轴进行分割然后是y-轴然后再次是-x轴(即偶数深度的x-轴分割奇数深度y-轴分割)以这种方式继续直到所有点都被考虑在内 范例 已有位置数据Vector2[] position {A,B,C,D,E,F} ,将其进行空间划分 第一次分割深度 0 Y 轴分割 A第二次分割深度 1 X 轴分割 B第三次分割深度 2 Y 轴分割 C第四次分割深度 2 Y 轴分割 D第五次分割深度 1 X 轴分割 E第六次分割深度 2 Y 轴分割 F 这种方式会有一种问题 –二叉树不平衡(当树的深度很深时很影响效率就必须将树进行重新排序) 2.以K维中的最大包围边划分 这里还有不同的策略有的是按最大密度边有的是按最长边这里的是按最长边 每一次分割空间以按内部元素的包围盒最大的那一边的中点位置进行分割直至分割到一个区域内只有一个对象 已有位置数据Vector2[] position {A,B,C,D,E,F} ,将其进行空间划分 第一次分割(A,B,C,D,E,F)其包围盒的X边 Y边以(E.x-B.x)/2的位置划分为 ab第二次分割(B,C,D)其包围盒的X边 Y边以(D.y-C.x)/2的位置划分为 cd第三次分割(B,C)其包围盒的X边 Y边以(B.y-C.x)/2的位置划分为 ef第四次分割(A,E,F)其包围盒的X边 Y边以(E.y-F.x)/2的位置划分为 gh第五次分割(A,F)其包围盒的X边 Y边以(A.y-F.x)/2的位置划分为 ij 这种二叉树就很平衡因为每次划分后都需要将位置数据进行重新排序而树则不用管在左图中可直接看出每次划分都将原始数据进行了拆分直至最后拆分到一个区域只有一个对象时停止 算法实现 这里采用的是第二种空间分割策略 【以K维中的最大包围边划分】 这里有两个问题要说明一下

1. “位置数据”的多少与树的总节点数的关系 因为位置数据会实时变动(数组长度不变仅是里面的数据元素值在变化暂不考虑动态长度的数组在二叉树中的求解)所以二叉树也很会随之频繁的重新构建那么构建就必须足够的轻量化(无CG)进而需要一个固定的数组容器来存放树节点 因为我们设定的是最极端的情况一个叶子节点所对应的空间内最多X个对象(X 1) 所以可用一个满的二叉树去计算那么其总节点数与叶子节点比关系为 2N-1 N 那么存放树节点的容器长度就为“位置数据”长度的2倍-1
2. 一个叶子节点所对应的空间内最多X个对象 这一点如果真的采用 X 1 的方式那可就太浪费了因为对象数可能会很密集放在同一个区域内的话岂不是能更快的查找所以 X 的值的大小的增加会减少树的深度那么树查找也就快了但X 值的增加也会同时增大空间分割的区域导致不能更快的定位位置所以必须要找到一个平衡 这和分割策略有很大的影响最理想的分割情况就是按区域内的成员密度进行分割这样的二叉树与叶子内对象分布最合理(但更复杂,暂不谈论) /树深度叶子内对象X 增大减小(树遍历加快)增大(对象定位减慢)X 减小增大(树遍历减慢)减少(对象定位加快) 代码示例 namespace Test.KDTree {public class KDTree{//树节点 –用于分割空间与记录容纳对象private struct AgentTreeNode{// [begin,end) 是代理容器内的一段区间范围表示该节点内的对象internal int begin;internal int end;internal int left; //左分支索引internal int right; //右分支索引// 该节点的 AABB 包围盒范围包围的就是 [begin,end] 成员的最大范围internal Vector2 min;internal Vector2 max;public float LengthX max.x - min.x;public float LengthY max.y - min.y;public float CenterX (max.x min.x)*0.5f;public float CenterY (max.y min.y)*0.5f;//返回该节点下的对象个数public int Count end - begin;//返回position距离包围盒的距离平方如果在包围盒内(含边框)返回0public float SqrDisBounds(Vector2 p){return sqr(Math.Max(0.0f, min.x - p.x)) sqr(Math.Max(0.0f, min.y - p.y)) sqr(Math.Max(0.0f, p.x - max.x)) sqr(Math.Max(0.0f, p.y - max.y));}float sqr(float scalar){return scalar * scalar;}}//二叉树要分割的对象代理(要与游戏中的对象解耦)public struct Agent{public int id; //游戏中的对象IDpublic Vector2 position; //游戏中的对象位置}//节点内容纳的最大对象数private const int MAX_LEAFSIZE 10;private Agent[] agents; //代理对象容器private AgentTreeNode[] agentTree; //代理节点容器//通过游戏中的对象数量初始化容器大小public void InitAgentCapacity(int count){agents new Agent[count];agentTree_ new AgentTreeNode[2 * agents.Length-1];}//添加代理public void AddAgent(int id){agents[id].id id;}//构建二叉树public void buildAgentTree(){//更新对象代理成员的位置数据for (int i 0; i agents.Length; i){agents[i].position getAgentPosition(agents[i].id);}buildAgentTreeRecursive(0, agents.Length, 0);}//递归构建二叉树private void buildAgentTreeRecursive(int begin, int end, int node){agentTree[node].begin begin;agentTree[node].end end;agentTree[node].min agentTree[node].max agents[begin].position;//计算该节点的Boundsfor (int i begin 1; i end; i){agentTree[node].max Vector2.Max(agentTree[node].max, agents[i].position);agentTree[node].min Vector2.Min(agentTree[node].min, agents_[i].position);}//当现有对象大于最大对象数时才进行分割也说明其不是叶子节点if (end - begin MAX_LEAFSIZE){//是否是垂直定向的bool isVertical agentTree[node].LengthX agentTree[node].LengthY;//定向的中间位置float splitValue isVertical ? agentTree[node].CenterX : agentTree[node].CenterY;int left begin; //在对象容器[begin,end]内的包含范围起始索引int right end; //在对象容器[begin,end]内的包含范围结束索引//根据中间位置将对象容器[begin,end]进行重排序//将小于中间位置的放置在容器[begin,end]左边将大于等于中间位置的放置在容器[begin,end]右边while (left right){while (left right (isVertical ? agents[left].position.x : agents[left].position.y) splitValue) left;while (right left (isVertical ? agents[right - 1].position.x : agents[right - 1].position.y) splitValue) –right;if (left right){Agent tempAgent agents[left];agents[left] agents[right - 1];agents[right - 1] tempAgent;left;–right;}}//获取容器[begin,end]左边(小于中间位置的对象)的数量int leftSize left - begin;//因为与中间值比较时等于的部分放置在了右边所以会出现左边无成员的情况(通常是有大量重叠)就让右边给左边让一个出来(其实你都全重叠到一个点上了不让也可以反正这时的二叉树时不可能平衡的)if (leftSize 0){leftSize;left;right;}//这里的二叉树存储结构时按照容器[begin,end]的左边数量进行决定该节点右分支的放置位置这样在满二叉树的状态下一个叶子节点对应一个对象agentTree[node].left node 1;agentTree[node].right node 2 * leftSize;//left 和 right 将容器[begin,end]划分为了两块这里让其递归计算其自身的分块buildAgentTreeRecursive(begin, left, agentTree[node].left);buildAgentTreeRecursive(left, end, agentTree_[node].right);}}public Funcint, Vector2 getAgentPosition; //获取指定代理对象的位置public Actionint callNear;//迭代查询指定位置下给定半径中的所有对象//rangeSq 为半径的平方为的是在计算两点位置时不用进行开根号处理public void queryAgentTreeRecursive(Vector2 position, float rangeSq, int node){//表示其为叶子节点可直接进行包含对象遍历if (agentTree_[node].Count MAX_LEAFSIZE){for (int i agentTree[node].begin; i agentTree[node].end; i){if (Vector2.SqrMagnitude(agents[i].position - position_) rangeSq){callNear(agents[i].id);}}}else{//每个节点下都有两个分支可二分查找最近的区域float distSqLeft agentTree[agentTree[node].left].SqrDisBounds(position);float distSqRight agentTree[agentTree[node].right].SqrDisBounds(position);if (distSqLeft distSqRight){if (distSqLeft rangeSq) //left区域是否在半径内,right 比left大就没必要else了{queryAgentTreeRecursive(position, rangeSq, agentTree[node].left);if (distSqRight rangeSq) //left right 都在半径范围内时right也要考虑{queryAgentTreeRecursive(position, rangeSq, agentTree[node].right);}}}else{if (distSqRight rangeSq){queryAgentTreeRecursive(position, rangeSq, agentTree[node].right);if (distSqLeft rangeSq){queryAgentTreeRecursive(position, rangeSq, agentTree[node].left);}}}}}} }项目包 package 导入Unity 内即可