- 上一篇：ASP.net基建管理信息系统设计+流程图
- 下一篇：基于组态软件的监控系统的设计+文献综述
（2）确定Node-data的域值。根据x轴方向的值2,5,9,4,8,7排序选出中值为7，所以Node-data = （7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于split = 0（x轴）的直线x = 7；
（3）确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分，如图3所示。X <= 7的部分为左子空间，包含3个节点{（2,3），（5,4），（4,7）}；另一部分为右子空间，包含2个节点{（9,6），（8,1）}。
图3 x=7将整个空间分为两部分
如算法所述，k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点（5,4）和（9,6）（也就是左右子空间的'根'节点），同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点，如图2所示。最后生成的k-d树如图4所示。
图4 上述实例生成的k-d树
注：每一级节点旁边的x和y表示以该节点分割左右子空间时split所取的值。
3.2.3 最近邻搜索算法
最近邻搜索算法(Nearest Neighbor Search )旨在找到距离给定输入点最近的点。这种搜索方法，可以通过使用树属性，快速高效地大幅削减搜索空间。
我们先以一个简单的实例来描述最邻近查找的基本思路。
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行回溯操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图5所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。
图5查找（2.1，3.1）点的两次回溯判断
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
另外举一个较为复杂的例子，如查找点为（2，4.5）。同样先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<（7,2），（5,4），（4,7）>，取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。以（2，4.5）为圆心，以3.041为半径作圆，如图6所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图7所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。
图6 查找（2，4.5）点的第一次回溯判断
图7 查找（2，4.5）点的第二次回溯判断
-
基于MATLAB的图像增强算法设计
-
基于Kinect的手势跟踪与识别算法设计
-
JAVA基于安卓平台的医疗护工管理系统设计
-
基于核独立元分析的非线...
-
基于Hadoop的制造过程大数据存储平台构建
-
基于安卓系统的测量软件...
-
基于VC++的GIS矢量图形系统开发
乳业同业并购式全产业链...
当代大学生慈善意识研究+文献综述
电站锅炉暖风器设计任务书
十二层带中心支撑钢结构...
杂拟谷盗体内共生菌沃尔...
河岸冲刷和泥沙淤积的监测国内外研究现状
java+mysql车辆管理系统的设计+源代码
酸性水汽提装置总汽提塔设计+CAD图纸
大众媒体对公共政策制定的影响
中考体育项目与体育教学合理结合的研究