问题
?
给定一系列的点，和一个矩形。求矩形中包含的点的数量。
?
解答
?
这个问题可以通过建立矩阵来进行求解。首先将一个空间分割成矩阵，将点放置在对应的格子中，再计算矩形覆盖的格子，再判断格子中的点是否包含在矩形中
?
这种方法的问题是，可能这些点全都集中在一个格子中。这种情况下算法的效率比较低。
?
?
这种问题在地图的应用中非常常见。
?
?
因此需要引入2D树的概念，使得矩阵的分解会根据点的密度自动适应。
?
2D树
?
下图展示了2D树的样子。
?
?
2D树的构建
?
每次加入一个点时，将平面分成两半。
?
?
加入第二个点时，由于第二个点在第一个点的右侧，因此在第一个点的右子节点创建一个新的节点。由于父节点是竖直的，所以子节点需要水平分割。
?
?
增加更多的点之后，就会形成如下的二叉树。
?
?
搜索操作
?
搜索矩形中包含的点。
?
?
搜索的时候需要从根节点开始。从根节点知道，矩形在节点的左侧，因此只需要搜索左侧即可。到了点3，由于矩形覆盖了两边的区域，因此需要搜索两边。一直迭代循环，直到节点搜索完毕为止。
?
这种算法的平均复杂度是logN，最坏复杂度是sqrtN。
?
问题
?
给定一系列点，和一个待测点。求与待测点最近的点。
?
用2D树的数据结构时，有时可以将搜索范围缩小到一半。
?
Kd树就是2D树的推广形式，处理二维以上的数据时非常高效。
?
N体模拟算法
?
关键思想就是对于单个质点来说，将距离较远的那些点看成一个质点。
?
具体实现可以参考论文
http://www.cs.montana.edu/courses/spring2005/580/papers/0906008.pdf