Introspectively, we may have a need, like to call a nearby car in the cabling software to pick us up, or to look at a nearby person in the qq. We all need to know the collection of other objects that are within our range. If the above example is abstracted, it's to focus on a point, a radius, and find other points in space. Admittedly, when there are fewer mid-points in space, we can use all the points to calculate the distance between the current point and the other points in a way that allows the results to be matched, but there are more points in space (false).

我们可能会有这样的一种需求，像是打车软件中呼叫附近的车来接送自己，或者是在qq中查看附近的人。我们都需要知道距离自己一定范围内的其它目标的集合。如果将上面举例的功能抽象出来，就是要实现以某个点为中心，以一定的距离为半径，在空间中查找其它点所构成的集合。诚然，当空间中点的数目较少时，我们可以采用遍历所有点的方式来计算出当前点与其它点之间的距离的方式来得到对应的结果集，但是空间中的点数目较多(假如达到千万级别)，且存在多个点要计算出距离当前点一定范围内的点所构成的集合时，这个计算的时间复杂度便达到了O(\(mn\))级别，为此，我们需要改进该实现方式。

我们先不考虑多维空间中的点，先考虑一维平面上的数，假如为1，92，8，11，18，91，7，47这几个数。如果我们想得到某个数一定距离范围内的那几个数，如数字11，想得到距离不超过为7的数(&lt;=7)。那么我们可以将这些数按照从小到大的顺序进行排序，使其有序，然后找到对应的数字，以该数为中心，分别往左和往右遍历对应的点并计算距离，如果是在符合要求的范围内，则将其纳入结果集中。以上面例子为例，将数字进行排序，得到 1，7，8，11，18，47，91，92的数字序列。然后找到数11，分别往左计算各点的距离，得到符合条件的数7，8(11-1=10&gt;7不符合条件)。往右计算各点的距离，得到符合条件的数18(47-11=36&gt;7不符合条件)。为此，可以得到符合条件的结果集7,8,18。

In addition to sorting numbers in this way, we can use the data structure of the two fork tree to narrow the range of data to be found by directly locating it to node 7 and searching for subtrees based on node 7. It is important to note that, if a number within a certain distance is required to be added, it can be found by first identifying the nearest number and using that number as a central point, or by adding the number to the pool and reordering it and searching it in the manner of the number at the centre.

We can think of points in space in a similar way, because they're multi-dimensional, we have to think about reducing them to one dimension and making them adjacent to one dimension in space, and to keep them largely adjacent in one dimension. In addition to reducing them, we can consider dividing space into sub-spaces in one way or another, so as to reduce the range of data that needs to be searched. To that end, we have two ways.

Rationale: The rationale is to divide space into multiple subspaces according to dimensions, so that points in space are evenly distributed in subspaces divided according to corresponding dimensions, thereby achieving the objective of reducing the range of data to be searched in space when searching for the target point.

Introduction: kd-tree is a two-fork tree with a multi-dimensional spatial division, which can be seen as an extension of the line tree to a multi-dimensional variant. Each node on the two-fork tree corresponds to a k-dimensional hyperrectangle area. The selection of dimensions to divide space can be made in a variety of ways, generally based on that dimension of the medium difference or the way the rotational dimension is selected. The selection of dimensions in space can affect the efficiency of finding, depending on the distribution of data.

kd-tree build process: The tree is built in a sequential process where no coordinates are stored at the non-leaf node, only the dimensions of the division and the corresponding division value are stored, and the leaf node keeps the corresponding node value, which facilitates the subsequent search process. The relevant pseudo-codes are as follows:

kd-tree search process: the kd-tree search process is a two-point search with a retroactive search, and after each two-point search to the leaf node, it returns to another branch that has not been visited to determine whether there are any closer points under the branch. The relevant pseudo-codes are as follows:

Here are a few test codes for debugging and testing.

分析： 构建一棵kd-tree的时间复杂度根据划分维度的选择方式不同，时间复杂度也不同。采用方差最大的那个维度作为空间划分的依据，其时间复杂度为O(nklogn)，采用轮流交替维度作为空间划分依据的，其时间复杂度为O(nlogn)。建树的空间复杂度为O(n)。查找过程的时间复杂度为O(\(n^{1-\tfrac{1}{k}}\)+m)，其中m为每次要进行查找的最近点个数，k为空间的维度。

适用情况： 该方式适用于点坐标变动较少甚至基本不变而且维度k不大的情况，其可以精确的获得所需的一定距离的点。对于每次空间中的点坐标发生变化的情况，其可以采用重新建立kd-tree数据结构的方式或者采用替罪羊方式实现的改进后的kd-tree来实现。对于维度k小于20时能够获得较高的效率，当空间维度较高时，其接近于线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N&gt;&gt;\(2^D\)，才能达到高效的搜索。

在介绍降维编码方式之前，我们可以先看下<a href="https://www.bilibili.com/video/BV1Sf4y147J9?spm_id_from=333.337.search-card.all.click">这个视频</a>让自己对如何降维多维空间有个直观的认识。

Space fill curves are mathematically viewed as a map function that converts N-dimensional data to a continuous one-dimensional space. In fact, storage disks (commonly related databases) are one-dimensional storage devices, while spatial data are mostly multi-dimensional and rarely have a single-dimensional sequence. So, in order to map adjacent elements in multi-dimensional space as much as possible along a straight line, experts have proposed a number of mapping methods. The most commonly used methods include Z Organization, Hilbert, Peano curves, etc.

To that end, we can use a certain way of de-viving a proximity point in a multi-dimensional space, so that it can be brought as close as possible to a point in a single dimension, and then find a proximity value in a single dimension to achieve the goal of finding a proximity point in a space.

For the manner in which the spatially filled curve is realized, we are only considering the achievement of the Gilbert space filled curve under two dimensions.

Analysis: Encodes a space point reduction dimension into one dimension of data with a time complexity of O (1). Maintains an orderly data structure with a time complexity of O (logn) and a time complexity of O (logn+m), of which m is the number of points to be found.

A Space Filling Curve applies to situations where the coordinates of the mid-point in space change frequently, or even the number of points change frequently, but its search effect is influenced by the selection of the filling curve, for which reason additional points closer to the point at a certain distance can be considered for more accurate results.

In production, we must have a flexible combination of performance to achieve the function efficiently, depending on the reality of the project. When the number of multidimensional mid-points is small and the number of calls for this function is low, it is not necessarily less efficient to use all the points through the cost of creating and maintaining the corresponding data structures than through the use of data structures or decoupling.

As the blogger himself has experienced before, there is a need to first get the closest point to a robot that may be operating abnormally, and then get the distance from the nearest point to determine whether the robot is deorbiting. Because robots are very unlikely to be deorbited, and maps are generally smaller and not easily altered. To achieve the closest efficiency by passing judgement, it will be more efficient and less expensive than by maintaining data structures and so on. But to accommodate large maps and anomalies, a threshold is set for this purpose, which, when satisfied, will be achieved in a way that preserves KD-Tree.

Application of KD-Tree and Gilbert Space Filling Curves