Introduction
With the rapid development of continuous operation reference station (CORS) technology, surveying and mapping, earthquake and other industries and cities have successively established CORS, GAMIT/GLOBK software due to its data processing results High precision, fast calculation speed, high degree of automation, open source code, etc., have become the preferred software for data processing of high-precision reference control network.
In my country’s GPS measurement specifications, repeated baselines and independent closed loop inspections are required, but GAMIT/GLOBK software does not have this function. This contradiction brings to the production department that uses this software for high-precision data processing. It is difficult to come, so how to quickly and automatically generate repeated baselines and independent closed loops of the GAMIT baseline network.
GAMIT software forms a fully-combined baseline with a synchronization loop as a unit, and the number of baselines is large. If all the baselines participate in the network search for closing conditions, the calculation efficiency is too low and the formation of redundant closing conditions is too much.
Combined with the characteristics of the GAMIT baseline network, carefully analyze various baseline network structures, flexibly apply related concepts and algorithms in the subject of graph theory, and explore a complete set of GAMIT baseline network's simplest asynchronous loop search algorithm. The algorithm has a clear and simple idea, which can ensure that all check conditions are found and are independent of each other. The software developed based on this algorithm has been verified in practice and the results are complete and reliable.
Analysis of Graph Theory
The so-called "graph" in graph theory refers to a certain type of concrete things and the connections between these things. If we use points to represent these specific things, and use a line segment (straight or curved) connecting two points to represent the specific connection between two things, we get a geometric image describing this "graph". In other words, the graph consists of a set of points and The set of edges connecting these points is composed. Graph theory provides a mathematical model for any discrete system that contains a binary relationship. The model can be solved with the help of the concepts, theories and methods of graph theory. Obviously, the baseline network is a "graph", so the concepts and algorithms related to graph theory can be used to search for asynchronous loops on the baseline network.
Minimum spanning tree: In a connected graph G, if all the vertices and some of its edges are taken to form a subgraph g, if the edges in g connect all the points in the graph G without forming a loop , Then the subgraph g is called a spanning tree of the original graph G; if the sum of all edge weights in the spanning tree is the smallest spanning tree, then the spanning tree is called the minimum spanning tree of the graph (hereinafter referred to as Minimum tree). Co-tree: Remove all the edges of a spanning tree in a connected graph G. The remaining edges are called co-trees. Each edge in the co-tree is called co-branches, and a co-branches can form a closed loop.
The shortest path: the sum of the weights of the edges passing by a path between two mutually different vertices in the graph is defined as the weighted path length of the path, and there may be more than one between two vertices For a path, the path with the shortest weighted path length is called the shortest path.
In order to apply the algorithm in graph theory to solve the baseline network, that is, to search for the simplest independent closed loop, the baseline network needs to be "graphed" first. The essence of the graph is a two-dimensional matrix, so the baseline network is "mapped", that is, it is "matrix", and the matrix is stored in the form of an array in the computer, so the baseline needs to be stored in a two-dimensional array.
First, the points in the baseline network are numbered uniformly. Suppose there are m points, numbered from 1 to m; then an array of m rows and m columns is created, and all array elements are assigned a maximum value , Such as 9999; Finally, the baseline information is assigned to the array. For example, if there is a baseline between the two points numbered i and j, the two elements in the array are given baseline weights. After these three steps, the baseline network is "graphed", and the simplest independent closed loop can be searched by flexibly applying the concepts and algorithms of minimum tree, co-tree, and shortest path.
Asynchronous loop algorithm
Comparison of different networking baseline selection methods
As we all know, GAMIT performs baseline network solution time by time. The same A baseline is formed between two observation points during a period, and the closing error of the synchronous loop is zero. Therefore, to check the quality of the baseline, it must pass the closing error of the asynchronous loop. The so-called asynchronous loop means that the baseline forming the closed loop comes from different observation periods. Asynchronous loop in its simplest form. Therefore, in view of the characteristics of the GAMIT baseline network, the repeated baselines and independent closed loops mentioned in the GPS measurement specifications can be collectively referred to as asynchronous loops, and the same algorithm can be used to search. To form an asynchronous loop, it is necessary to connect the baseline of each period into a large network, and then search for the asynchronous loop. Therefore, how to select the network baseline is the key. The following analyzes the various methods of selecting the baseline one by one, and selects the best method.
(1) All baselines participate in networking
All baselines calculated by GAMIT will participate in networking, so there will be many redundant baselines, which greatly increases the workload of searching for closed loops , And form a lot of redundant closing conditions (synchronization loop), the graphic structure is complex and messy, and the calculation speed is slow, so it is generally not used.
(2) Boundary baseline participates in networking
That is, the boundary baseline is selected to participate in networking. In computational geometry, the boundary line of the point set is called the convex hull. This method ignores the simultaneous The internal points of the segment observation point set will cause the omission of the closing condition. Five points A, B, C, D, and E were observed in the first period, and four points C, D, E, and F were observed in the second period. The solid line is the baseline of the first period and the dashed line is the baseline of the second period. If only the boundary baseline is selected to participate in the networking, three asynchronous loops can be formed: A1B1-B1D1-D2E2-E2C2-C1A1, C2E2-E2D2-D1C1, C1D1-D2F2-F2C2, because the synchronization loop closure error of the GAMIT solution of the baseline is Zero, so the three asynchronous loops are essentially an asynchronous loop C1D1-D2C2 after simplification.
(3) Baseline that can form a triangulation network to participate in the network
That is, the baseline that can form a triangulation network is selected to participate in the network. There are multiple algorithms in the subject of computational geometry that can be automatically generated The point-set triangulation network, because the selected baseline is redundant, will form more closed conditions, so that the searched asynchronous loops are not completely independent of each other, but the closed conditions will not be missed.
(4) Independent baselines participate in networking
Only select independent baselines in the same period to participate in networking
that is, there are m points, then m-1 An independent baseline can connect all points without forming a closed loop. Because there are many ways to select independent baselines, one point can be connected to other points (star type), end to end can be connected point by point (solitaire), the smallest tree can be selected (that is, the shortest length of the selected independent baselines is the shortest after the addition), etc. , The closing conditions of different selection methods are different, but according to the characteristics of the simultaneous linear representation of the baselines of the same period of GAMIT calculation, the different closing conditions are essentially the same after simplification. Because all the selected baselines are independent, the closed conditions of the composition are independent and complete.
Refer to the first example, select different independent baselines to form a closed loop and analyze: After analyzing the above three baseline nets, you can see that no matter how you choose an independent baseline, there are only two closed conditions. Asynchronous loops formed after simplification can be the same or can be linearly marked with each other. Therefore, it is the best way to select independent baselines to form independent asynchronous loops, which can ensure that the searched asynchronous loops are neither omitted nor redundant.
Algorithm for automatic generation of independent closed loops
After selecting independent baselines and forming the baseline network, search for independent closed loops according to the following algorithm.
Step 1: Number the control points uniformly. If there are m points, the number is 1-m;
Step 2: Bring the point number to every GPS network End points of a baseline, and assign a weight to each baseline, so that each baseline can be uniquely determined by the number and weight of the end points;
Step 3: Build a square matrix , According to the method mentioned above, matrix the GPS baseline network. For multi-period baselines, only the first baseline weight is assigned to the matrix elements;
Step 4: Find the minimum tree based on the formed matrix;
Step 5: According to the numbers and weights of the two ends of the baseline, remove the baseline that constitutes the smallest tree from the baseline network, and the remaining baseline is redundant observations, which can be called a residual tree, an redundant baseline It means that a closed loop can be formed.
Step 6: Generate a matrix from the minimum tree, find the shortest paths in the matrix of the two ends of all redundant baselines one by one to form a closed loop, output the smallest closed loop among them, and put the corresponding redundant baselines back Matrix, that is, assign the baseline weight to the element in the matrix corresponding to its end point, and delete it from the remaining tree at the same time; repeat searching, putting back, and deleting until the remaining tree is empty.
The program flow of the simplest asynchronous loop automatic generation of the baseline network
The selection method of the baseline network, the search algorithm of the independent closed loop, and the closed loop were introduced in detail above. Simplify the program, the following is a review of the program flow for the automatic generation of the simplest asynchronous loop of the GPS baseline network.
The first step: select independent baselines from time to time;
The second step: connect the independent baselines of all time periods into a large network and search for asynchronous loops. If there are m points, n If you have a baseline, you can search for n-m+1 independent asynchronous loops;
Step 3: Simplify the searched asynchronous loop;
Step 4: Computational The simplified asynchronous loop is poorly closed.
Summary
According to the automatic generation algorithm of the asynchronous loop of the GPS baseline network solved by the GAMIT software, the program developed according to this algorithm can automatically and quickly search for the independent asynchronous loop and calculate the closing error. Very good practical value, it solves the contradiction that GAMIT software does not generate asynchronous loop and there is this requirement in the specification.
The closed-loop search algorithm introduced in this article is simple and clear. With reference to this algorithm, you can also write the closed-loop generation program of the level network and the gravity network.