CN114998513B - Grid remapping method of earth simulation system with circulating boundary based on KD tree - Google Patents

Abstract

The invention belongs to the technical field of geographic information data processing and reconstruction, and discloses a grid remapping method of an earth simulation system with a circulating boundary based on a KD tree, which comprises the following steps: acquiring a grid of the earth simulation system, determining a source grid point, a target grid point and a circulation boundary, and placing all the source grid point and the target grid point in a specified circulation section of each circulation dimension; if the target grid points are concentrated near the loop boundary and the target grid points are far more than the source grid points, searching the source grid points corresponding to the target grid points based on a KD tree source point replication method; otherwise searching a source grid point corresponding to the target grid point based on a KD tree target point replication method; the grid information is remapped according to the target grid point and the corresponding source grid point. The method not only maintains the advantages of no requirement on the grid type and strong applicability of the KD tree, but also effectively solves the problem of cyclic boundaries in the grid remapping process of the earth simulation system, and has wide application prospect.

Description

Grid remapping method for earth simulation system with cyclic boundaries based on KD tree

Technical field

The invention belongs to the technical field of geographical information data processing and reconstruction, and in particular relates to a KD tree-based earth simulation system grid remapping method with cyclic boundaries.

Background technique

Data search in high-dimensional spaces is one of the most difficult problems in many applications. As a classic data structure, KD tree is widely used in data search in high-dimensional space, especially nearest neighbor search and range search. Typical application scenarios include ray tracing, grid mapping, cluster analysis, etc.

KD tree can be regarded as a special binary tree. The difference between KD trees and ordinary binary trees is that ordinary binary trees always use fixed dimensions for division, while KD trees can use any dimension for division in each layer as needed. The dimension with the largest variance or the largest dispersion is usually chosen for partitioning in order to split the search space as evenly as possible. The middle point is usually selected as the dividing point to build a balanced KD tree, thereby reducing the tree height and shortening the search time. After the KD tree is constructed, the entire search space is actually organized in the form of a binary tree according to the order of division. As shown in Figure 1, the KD tree uses hyperplanes to divide the space. The premise for obtaining independent, unique, non-overlapping subspaces is that any dimension of the space is acyclic. However, many real-world applications need to deal with cyclic boundary conditions. For example, in Earth simulation systems, the longitude of the global grid is cyclic. Once a cycle boundary exists in the search space, many pruning judgments in the original KD tree-based data search process will no longer hold.

Contents of the invention

It is crucial to design new data structures and algorithms based on the characteristics of cycle boundaries and solve the application problems of KD trees in high-dimensional cycle spaces. In view of this, the present invention proposes a KD tree-based earth simulation system grid remapping method with cyclic boundaries.

Specifically, the KD tree-based earth simulation system grid remapping method with cyclic boundaries disclosed by the present invention includes the following steps:

Step 1, place all source grid points and target grid points within the specified cycle segment of each cycle dimension;

Step 2: According to the distribution of target grid points and the number of target grid points and source grid points, choose different methods to search for the corresponding source grid points required to remap the target grid points;

Step 201, if the target grid points are concentrated near the cycle boundary, and the target grid points are far more than the source grid points, search for the source grid points corresponding to the target grid points based on the KD tree source point copy method;

Step 202, otherwise search for the source grid point corresponding to the target grid point based on the KD tree target point copy method;

Step 3: Remap the grid information based on the target grid point and the corresponding source grid point;

The source point copying method described in step 201 includes the following steps: for each loop boundary pair A and B, copy the source grid points near the loop boundary A to the outside of the loop boundary B, and copy the source grid points near the loop boundary B. The grid points are copied to the outside of the loop boundary A; a KD tree is constructed for the original source grid points and the copied source grid points based on geographical information data; the corresponding source is searched for the target grid point according to the classic KD tree search algorithm. Grid points; result post-processing, that is, mapping the searched source grid points back to the corresponding original source grid points;

The target point copying method described in step 202 includes the following steps: constructing a KD tree based on geographical information data; obtaining the target grid point, searching for the corresponding source grid point in the KD tree, and obtaining the current source grid point Search results; select an unprocessed cycle dimension, copy the target grid point to the corresponding position outside the cycle boundary on the far side from the target grid point, and search the corresponding source network again based on the copied target grid point Grid point search results, and compare and select the current optimal source grid point search results from the obtained source grid point search results; repeat the above operations for the remaining cycle dimensions to obtain the final optimal source grid point.

Further, the scope of the copy described in step 201 is determined by the distribution characteristics of the source grid point data, including:

If the maximum distance between any position in the search space and its nearest source grid point is L, then only the source grid points within the range L of the loop boundary need to be copied;

If the maximum distance between any position in the search space within the range L of the loop boundary and its nearest source grid point is L, then only the source grid points within the range L of the loop boundary need to be copied;

If the distribution characteristics of the source grid point data are unknown or uncertain, the maximum replicated area for each loop boundary will be half the search space.

Further, in the target point copying method described in step 202, before a new search starts, for the selected cycle dimension, if the distance between the target grid point and its nearest cycle boundary is greater than the current search threshold, then in that Target grid point copy and search canceled for selected cycle dimensions.

Further, in the target point copying method described in step 202, in a new search, the optimal distance between the current target grid point and the source grid point is used as the initial search distance.

Further, the nearest neighbor search method is used in the search process described in step 202, which specifically includes:

Set the initial closest distance between the initial target grid point and the source grid point to T ₀ ;

After the first round of nearest neighbor search, the shortest distance between the target grid point and its nearest source grid point is T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the size of the current shortest distance T, if S is not less than T, which means that the point near another loop boundary in the i-th dimension cannot be closer than the current point, then directly start processing the next loop dimension; otherwise, perform further search in the current loop dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary. Subsequent searches use the current shortest distance T as the initial shortest distance value to cut off more unnecessary branches in the new search;

Assume that the latest closest distance is t, compare between t and T, and select the smallest result as the latest search result;

After all cycle dimensions undergo the above operations, the final shortest distance and corresponding source grid point are obtained as the final result.

Further, the K neighboring point search method is used in the search process described in step 202, which specifically includes:

Set the initial Kth close distance T ₀ between the initial target grid point and the source grid point;

After the first round of nearest neighbor search, the final distance between the target grid point and its nearest Kth source grid point is T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the current nearest Kth source grid The size of the point distance T. If S is not less than T, it means that there is no relevant point near another cycle boundary in the i-th dimension, and the next cycle dimension will be processed directly; otherwise, further search will be performed in the current cycle dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding loop boundary. Subsequent searches use the current Kth short distance T as the initial shortest distance value to cut off more unnecessary points in the new search. branch;

Assume that the new Kth close distance is t, compare between t and T, and select the smallest result as the latest result;

After the above operations are performed in all cycle dimensions, the Kth close distance and corresponding source grid point are the final results.

Further, the range search method is used in the search process described in step 202, which specifically includes:

Set the search distance T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the size of the current search distance T, if S is not less than T, which means that there is no relevant point near another loop boundary in the i-th dimension, and then the next loop dimension will be processed directly; otherwise, further search will be performed in the current loop dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary, and then perform a new range search;

After all cycle dimensions undergo the above operations, the corresponding source grid points are obtained as the final result.

The beneficial effects of the present invention are as follows:

The invention can effectively solve the grid remapping problem of the earth simulation system with cyclic boundaries, and can greatly reduce the search time by using the target point copying method.

Description of the drawings

Figure 1 Schematic diagram of KD tree;

Figure 2 is a schematic diagram of the mirroring method of the present invention;

Figure 3 is an overall flow chart of the present invention;

Figure 4 is the source point copy mirroring method process of the present invention;

Figure 5 The target point copy mirroring method process of the present invention;

Figure 6. The search time of the source point copy mirroring method and the target point copying mirror method of the present invention changes with the number of source points;

Figure 7. The search time of the source point copy mirroring method and the target point copying mirror method of the present invention changes with the number of target points.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings, but the present invention is not limited in any way. Any transformation or replacement based on the teachings of the present invention falls within the protection scope of the present invention.

When the cyclic space is actually processed, a boundary is usually artificially divided, which is called the cyclic boundary. In this way, the search space has two virtual finite boundaries in the dimension where the cycle boundary is located. The present invention proposes to use the mirror method to realize KD tree data search in high-dimensional cyclic space, which includes the following steps:

Step 1, place all source grid points and target grid points within the specified cycle segment of each cycle dimension;

Step 2: According to the distribution of target grid points and the number of target grid points and source grid points, choose different methods to search for the corresponding source grid points required to remap the target grid points;

Step 201, if the target grid points are concentrated near the cycle boundary, and the target grid points are far more than the source grid points, search for the source grid points corresponding to the target grid points based on the KD tree source point copy method;

Step 202, otherwise search for the source grid point corresponding to the target grid point based on the KD tree target point copy method;

Step 3: Remap the grid information based on the target grid point and the corresponding source grid point;

The source point copying method described in step 201 includes the following steps: for each loop boundary pair A and B, copy the source grid points near the loop boundary A to the outside of the loop boundary B, and copy the source grid points near the loop boundary B to the outside of the loop boundary B. The grid points are copied to the outside of the loop boundary A; a KD tree is constructed for the original source grid points and the copied source grid points based on geographical information data; the corresponding source is searched for the target grid point according to the classic KD tree search algorithm. Grid points; result post-processing, that is, mapping the searched source grid points back to the corresponding original source grid points;

The target point copying method described in step 202 includes the following steps: constructing a KD tree based on geographical information data; obtaining the target grid point, searching for the corresponding source grid point in the KD tree, and obtaining the current source grid point Search results; select an unprocessed cycle dimension, copy the target grid point to the corresponding position outside the cycle boundary on the far side from the target grid point, and search the corresponding source network again based on the copied target grid point Grid point search results, and compare and select the current optimal source grid point search results from the obtained source grid point search results; repeat the above operations for the remaining cycle dimensions to obtain the final optimal source grid point.

The scope of copying described in step 201 is determined by the distribution characteristics of the source grid point data, including:

If the maximum distance between any position in the search space and its nearest source grid point is L, then only the source grid points within the range L of the loop boundary need to be copied;

If the maximum distance between any position in the search space within the range L of the loop boundary and its nearest source grid point is L, then only the source grid points within the range L of the loop boundary need to be copied;

If the distribution characteristics of the source grid point data are unknown or uncertain, the maximum replicated area for each cycle boundary will be half the search space.

In the target point copying method described in step 202, before a new search starts, for the selected cycle dimension, if the distance between the target grid point and its nearest cycle boundary is greater than the current search threshold, then in the selected cycle dimension Target grid point copying and search cancellation for loop dimensions.

In the target point copying method described in step 202, in a new search, the optimal distance between the current target grid point and the source grid point is used as the initial search distance.

The nearest neighbor search method is used in the search process described in step 202, which specifically includes:

Set the initial closest distance between the initial target grid point and the source grid point to T ₀ ;

After the first round of nearest neighbor search, the shortest distance between the target grid point and its nearest source grid point is T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the size of the current shortest distance T, if S is not less than T, which means that the point near another loop boundary in the i-th dimension cannot be closer than the current point, then directly start processing the next loop dimension; otherwise, perform further search in the current loop dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary. Subsequent searches use the current shortest distance T as the initial shortest distance value to cut off more unnecessary branches in the new search;

Assume that the latest closest distance is t, compare between t and T, and select the smallest result as the latest search result;

After all cycle dimensions undergo the above operations, the final shortest distance and corresponding source grid point are obtained as the final result.

The K neighboring point search method is used in the search process described in step 202, which specifically includes:

Set the initial Kth close distance T ₀ between the initial target grid point and the source grid point;

After the first round of nearest neighbor search, the final distance between the target grid point and its nearest Kth source grid point is T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the current nearest Kth source grid The size of the point distance T. If S is not less than T, it means that there is no relevant point near another cycle boundary in the i-th dimension, and the next cycle dimension will be processed directly; otherwise, further search will be performed in the current cycle dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding loop boundary. Subsequent searches use the current Kth short distance T as the initial shortest distance value to cut off more unnecessary points in the new search. branch;

Assume that the new Kth close distance is t, compare between t and T, and select the smallest result as the latest result;

After the above operations are performed in all cycle dimensions, the Kth close distance and corresponding source grid point are the final results.

The range search method is used in the search process described in step 202, which specifically includes:

Set the search distance T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the size of the current search distance T, if S is not less than T, which means that there is no relevant point near another loop boundary in the i-th dimension, and then the next loop dimension will be processed directly; otherwise, further search will be performed in the current loop dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary, and then perform a new range search;

After all cycle dimensions undergo the above operations, the corresponding source grid points are obtained as the final result.

Example

The mirror method has two options based on the selection of the mirror point. This embodiment takes the nearest neighbor point search in a 2-dimensional space with only cyclic boundaries on the left and right sides as an example: the first option is to select the source point for mirroring, that is, the cyclic boundary The points near A are copied to the outside of the loop boundary B, and the points near the loop boundary B are copied to the outside of the loop boundary A. The maximum copy area for each copy is half of the entire search space (Figure 2(a)) shown). The number of data points that need to be replicated can be further controlled if the distribution of the source data has certain characteristics that can be further exploited, such as the existence of a maximum distance between any position in the search space and its nearest source point. The second option is to select a target point for mirroring. After a search process, the target point can be copied to the outside of the loop boundary (assumed to be the B boundary) farther away from the target point, and a new round of search can be performed (as shown in Figure 2(b)). The final result is selected from the comparison of the two search results. If you want to further reduce the search time, you can use the characteristics of the KD tree and the distribution characteristics of the source data and target data to set up new data structures and algorithms to further prune. For example, before the second search starts, if the distance between the target point and the B boundary is greater than the first search result, the second search can be cancelled.

The following sections describe the method of the invention in detail:

Assume that the search space has K dimensions and C cycle boundaries. Without loss of generality, we set D[1] to D[c] as cyclic dimensions, where D[i] represents the i-th dimension.

Figure 4 shows the source point copy mirroring method process. For each cycle dimension, a source point near one cycle boundary is copied to the outside of the other corresponding cycle boundary. The scope of replication can be determined by the distribution characteristics of the source data. For example, if the maximum distance between any location in the search space and its nearest source point is L, then only source points that are within L from the loop boundary need to be copied. In fact, the preconditions can be weakened even further. As long as the density of source points near the loop boundary reaches this condition, the finite replication method is still valid. However, if the distribution characteristics of the source data are unknown or uncertain, the maximum repeat area for each cycle boundary will be half of the original search space. It should be noted that each replication is based on the original source data. After copying the relevant source points of each cycle dimension, a KD tree can be constructed and the nearest point is found according to classic algorithms (more details about these classic algorithms can be found in the non-patent papers Cao Y., Wang B. ,Zhao W.-J.,et al.,"Research on Searching Algorithms for Unstructured Grid Remapping Based on KDTree," 3rd International Conference on Computer and Communication EngineeringTechnology.pp.29-33, 2020). The final step is to map the searched source grid points back to the corresponding original source grid points.

Taking nearest neighbor point search as an example, the flow of the mirroring method based on target point copying is shown in Figure 5. The preliminary work, including KD tree construction and conventional nearest neighbor search, is the same as the ordinary nearest neighbor search based on KD tree. The initial closest distance T ₀ is usually set to a negative number or a sufficiently large value. After the first round of data search, the final shortest distance between the target point and its nearest source point is T. Subsequently, we should handle each loop dimension in a special way. For simplicity, these cyclic dimensions can be processed sequentially. When processing the unprocessed cycle dimension i, the distance S from the target point to the cycle boundary closest to the target point in the i-th dimension should be compared at the beginning with the size of the current shortest distance T. If S is not less than T, it means that the point near another cycle boundary in the i-th dimension cannot be closer than the current point, and you can directly start processing the next cycle dimension. Otherwise, further searches within the current loop dimension are required. Before starting a new search, we need to copy the target point to the same relative position outside the corresponding loop boundary. Subsequent searches can use the current shortest distance T as the initial shortest distance value, which may help us cut off more unnecessary branches in new searches. Suppose the new nearest distance is t, we should compare between t and T and choose the smallest result as the latest result. After all cycle dimensions have gone through the above operations, the final shortest distance and corresponding source point will be the final result.

If this method replaces the nearest distance with a specified distance, it can become a range search for the cyclic space. Specifically include:

Set the search distance T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the size of the current search distance T, if S is not less than T, which means that there is no relevant point near another loop boundary in the i-th dimension, and then the next loop dimension will be processed directly; otherwise, further search will be performed in the current loop dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary, and then perform a new range search;

After all cycle dimensions undergo the above operations, the corresponding source grid points are obtained as the final result.

If this method replaces the nearest distance with the Kth smallest distance, it can become a search for K neighboring points in the cyclic space. The K neighboring point search method is adopted, including:

Set the initial Kth close distance T ₀ between the initial target grid point and the source grid point;

After the first round of nearest neighbor search, the final distance between the target grid point and its nearest Kth source grid point is T;

Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the current nearest Kth source grid The size of the point distance T. If S is not less than T, it means that there is no relevant point near another cycle boundary in the i-th dimension, and the next cycle dimension will be processed directly; otherwise, further search will be performed in the current cycle dimension;

Before starting a new search, copy the target grid point to the same relative position outside the corresponding loop boundary. Subsequent searches use the current Kth short distance T as the initial shortest distance value to cut off more unnecessary points in the new search. branch;

Assume that the new Kth close distance is t, compare between t and T, and select the smallest result as the latest result;

After the above operations are performed in all cycle dimensions, the Kth close distance and corresponding source grid point are the final results.

The conventional KD tree construction method includes: after preparing the two-dimensional point set to be divided, the KD tree can be constructed. First, it is judged whether the point set to be divided is an empty set. If so, the construction process is ended. If not, the construction process is officially started. The first step is to select the division dimension K. The commonly used criterion is to prioritize the division of dimensions with high variance. For simplicity, the strategy of segmentation can be adopted. The second step is to select the split point. The commonly used criterion is to select the median point on the current split dimension so that the number of elements on the left and right subtrees after splitting is equal. The final binary tree is a balanced binary tree. Each search Quite deep. The selection of the median usually requires sorting the points, and the quick sort method is used here. The third step is to put the remaining points to be divided into the left subtree point set and the right subtree point set according to the selected split points. The specific rule is to put the points to be divided whose K-dimensional value is less than or equal to the K-dimensional value of the split point into the left subtree, and the others into the right subtree. The left and right subtree point sets are constructed recursively according to the method introduced before.

The conventional KD tree search algorithm is as follows: When the current point T of the KD tree is empty, the search ends. Otherwise, first determine the dimension K divided by T and calculate the distance between T and the target point M. If T is closer to M, the minimum distance D and the corresponding closest point need to be updated. After this, enter the subtree and continue the search. If the value of the target point M on the division dimension K is less than or equal to the value of the current point T on the K dimension, it means that M is located in the left subtree space of T, and the distance between the points in this space and M may be greater than that of the right subtree. The distance between the point in the space and M is smaller, so the left subtree of T is searched recursively first. Otherwise, the right subtree of T is searched first. When a leaf node is searched, the search process starts backtracking. Determine whether the distance between the target point and the current point in the K dimension is greater than the minimum distance D. If so, it means that there is no closer point in another subtree space of the current point T, and you can continue to backtrack. Otherwise, another subtree space of the current point T needs to be further searched. The range search process based on KD tree is similar to the nearest neighbor search process. It only needs to replace the minimum distance D with a fixed range value, and replace the operation of updating D and the nearest point with recording the current point T. For more details, please refer to the non-patent paper Cao Y., Wang B., Zhao W.-J., et al., "Research onSearching Algorithms for Unstructured Grid Remapping Based on KD Tree," 3rdInternational Conference on Computer and Communication EngineeringTechnology.pp .29-33, 2020.

Figure 6 shows the time of searching data for two mirroring methods under different number of source points. Both source points and target points are 4-dimensional data, the number of target points (M) is 2 ²¹ , the number of cycle boundaries is 4, and the number of source points (N) changes from 2 ¹⁸ to 2 ²⁴ , increasing by 2 times each time. It can be seen from the figure that the target point copying method is better than the source point copying method under the current configuration. The growth rate of the search time of the source point copying method is almost proportional to Mlog ₂ N, while the growth rate of the search time of the target point copying method obviously decreases with the increase in the number of source points. This is because the increase in the number of source points reduces the target Caused by the point copy ratio.

Figure 7 shows the time of searching data for two mirroring methods under different number of target points. Both the source point and the target point are 4-dimensional data, the number of source points is 2 ²⁴ , the number of cycle boundaries is 4, and the number of target points changes from 2 ¹⁸ to 2 ²⁴ , increasing by 2 times each time. It can be seen from the figure that the search time of the source point copy method and the target point copy method increases linearly with the increase of target points. In addition, the search time of the target point copy method is still less than the search time of the source point copy method.

The beneficial effects of the present invention are as follows:

The invention not only maintains the advantages of the KD tree having no requirements on grid types and strong applicability, but also effectively solves the problem of cyclic boundaries in the grid remapping process of the earth simulation system.

The above embodiment is an implementation mode of the present invention, but the implementation mode of the present invention is not limited by the above embodiment. Any other changes, modifications, substitutions, and combinations that deviate from the spirit and principles of the present invention are not allowed. , simplification, should all be equivalent replacement methods, and are all included in the protection scope of the present invention.

Claims (6)

1. A KD tree-based grid remapping method for earth simulation systems with cyclic boundaries, which is characterized by including the following steps: Step 1, place all source grid points and target grid points within the specified cycle segment of each cycle dimension; Step 2: According to the distribution of target grid points and the number of target grid points and source grid points, choose different methods to search for the corresponding source grid points required to remap the target grid points; Step 201, if the target grid points are concentrated near the cycle boundary, and the target grid points are far more than the source grid points, search for the source grid points corresponding to the target grid points based on the KD tree source point copy method; Step 202, otherwise search for the source grid point corresponding to the target grid point based on the KD tree target point copy method; Step 3: Remap the grid information based on the target grid point and the corresponding source grid point; The source point copying method described in step 201 includes the following steps: for each loop boundary pair A and B, copy the source grid points near the loop boundary A to the outside of the loop boundary B, and copy the source grid points near the loop boundary B to the outside of the loop boundary B. The grid points are copied to the outside of the loop boundary A; a KD tree is constructed for the original source grid points and the copied source grid points based on geographical information data; the corresponding source is searched for the target grid point according to the classic KD tree search algorithm. Grid points; post-processing of the results, that is, mapping the searched source grid points back to the corresponding original source grid points; the range of the copy is determined by the distribution characteristics of the source grid point data, including: If the maximum distance between any position in the search space and its nearest source grid point is L, then only the source grid points within the range L of the loop boundary need to be copied; If the maximum distance between any position in the search space within the range L of the loop boundary and its nearest source grid point is L, then only the source grid points within the range L of the loop boundary need to be copied; If the distribution characteristics of the source grid point data are unknown or uncertain, the maximum replication area for each loop boundary will be half the search space; The target point copying method described in step 202 includes the following steps: constructing a KD tree based on geographical information data; obtaining the target grid point, searching for the corresponding source grid point in the KD tree, and obtaining the current source grid point Search results; select an unprocessed cycle dimension, copy the target grid point to the corresponding position outside the cycle boundary on the far side from the target grid point, and search the corresponding source network again based on the copied target grid point Grid point search results, and compare and select the current optimal source grid point search results from the obtained source grid point search results; repeat the above operations for the remaining cycle dimensions to obtain the final optimal source grid point. 2. The earth simulation system grid remapping method with cyclic boundaries based on KD tree according to claim 1, characterized in that the target point copying method described in step 202, before starting a new search, for the selected For a certain cycle dimension, if the distance of the target grid point from its nearest cycle boundary is greater than the current search threshold, the copy and search of the target grid point in the selected cycle dimension are cancelled. 3. The KD tree-based earth simulation system grid remapping method with cyclic boundaries according to claim 1, characterized in that the target point copying method described in step 202 uses the current target in a new search. The optimal distance between the grid point and the source grid point is used as the initial search distance. 4. The KD tree-based earth simulation system grid remapping method with cyclic boundaries according to claim 1, characterized in that the nearest neighbor search method is used in the search process described in step 202, specifically including: Set the initial closest distance between the initial target grid point and the source grid point to T ₀ ; After the first round of nearest neighbor search, the shortest distance between the target grid point and its nearest source grid point is T; Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the size of the current shortest distance T, if S is not less than T, which means that the point near another loop boundary in the i-th dimension cannot be closer than the current point, then directly start processing the next loop dimension; otherwise, perform further search in the current loop dimension; Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary. Subsequent searches use the current shortest distance T as the initial shortest distance value to cut off more unnecessary branches in the new search; Assume that the latest closest distance is t, compare between t and T, and select the smallest result as the latest search result; After all cycle dimensions undergo the above operations, the final shortest distance and corresponding source grid point are obtained as the final result. 5. The KD tree-based earth simulation system grid remapping method with cyclic boundaries according to claim 1, characterized in that the K neighboring point search method is used in the search process described in step 202, which specifically includes: Set the initial Kth close distance T ₀ between the initial target grid point and the source grid point; After the first round of nearest neighbor search, the final distance between the target grid point and its nearest Kth source grid point is T; Each cycle dimension is processed in turn; when processing the unprocessed cycle dimension i, first compare the distance S from the target grid point to the cycle boundary closest to the target grid point in the i-th dimension and the current nearest Kth source grid The size of the point distance T. If S is not less than T, it means that there is no relevant point near another cycle boundary in the i-th dimension, and the next cycle dimension will be processed directly; otherwise, further search will be performed in the current cycle dimension; Before starting a new search, copy the target grid point to the same relative position outside the corresponding loop boundary. Subsequent searches use the current Kth short distance T as the initial shortest distance value to cut off more unnecessary points in the new search. branch; Assume that the new Kth close distance is t, compare between t and T, and select the smallest result as the latest result; After the above operations are performed in all cycle dimensions, the Kth close distance and corresponding source grid point are the final results. 6. The KD tree-based earth simulation system grid remapping method with cyclic boundaries according to claim 1, characterized in that the range search method is used in the search process described in step 202, specifically including: Set the search distance T; Each loop dimension is processed in turn; when processing the unprocessed loop dimension i, first compare the distance S from the target grid point to the loop boundary closest to the target grid point in the i-th dimension and the size of the current search distance T, if S is not less than T, which means that there is no relevant point near another loop boundary in the i-th dimension, and then the next loop dimension will be processed directly; otherwise, further search will be performed in the current loop dimension; Before starting a new search, copy the target grid point to the same relative position outside the corresponding cycle boundary, and then perform a new range search; After all cycle dimensions undergo the above operations, the corresponding source grid points are obtained as the final result.