ghostsf

0x00 Factors Affecting Trajectory#

1. Coordinate Acquisition Frequency Issue: Trajectory lines are composed of trajectory points, and trajectory points are always discrete. The degree of discreteness depends on the frequency of coordinate acquisition. Higher frequency results in increased power consumption and trajectory storage, but the trajectory features are more obvious. Lower frequency makes the trajectory line features easier to lose. How can we intelligently adjust the coordinate reporting frequency?

2. Coordinate Acquisition Keep-Alive Issue: Mobile devices commonly have power-saving mode and screen-off function, which can easily cause the GPS acquisition program to be cleared by the system, resulting in the inability to collect coordinates or signal interruption during a certain period of time. However, internet apps are often added to the whitelist by devices (due to cooperation with manufacturers, etc.), so they do not have this problem.

3. Trajectory Coordinate Conversion Issue: GPS coordinates are in WGS84 format, while Beidou coordinates are in CGCS2000 format. The maps used for trajectory display are often maps of different coordinate systems, requiring coordinate conversion between them. Unlike internet applications that only use one type of map and only need to solve the conversion of one coordinate type, coordinate conversion in urban management involves multiple map types and uncontrollable map accuracy (such as declassified maps). The accuracy of coordinate conversion directly affects the display effect of the trajectory.

4. Coordinate Accuracy Issue: Satellite positioning requires observing at least 4 satellites simultaneously (due to its three-sphere positioning principle, plus using time as a variable, at least 4 satellites are needed for observation). However, in many cases, mobile devices cannot receive signals from more than 4 satellites simultaneously (e.g., indoors, obstructed by high-rise buildings), which will result in large positioning errors. How can we improve the accuracy of satellite positioning?

5. Trajectory Coordinate Denoising Issue: Coordinate accuracy is an unavoidable problem. In this case, a method is needed to remove abnormal points from the coordinates to ensure that the display of the trajectory is not affected by these abnormal points.

6. Trajectory Line Connection Issue: The point-to-point connection of trajectory lines will inevitably result in uneven transitions between lines, and connecting only the trajectory points directly can easily cause the trajectory line to "pass through walls" (if point A and point B are in different places at a crossroads, connecting them directly will cause the line to pass through non-road buildings in the middle).

7. Trajectory Playback Issue: Trajectories are naturally dynamic, and describing them solely with trajectory lines cannot truly represent the spatiotemporal characteristics of the trajectories. How can we beautifully display the dynamic nature of trajectories and give users a sense of watching animated films?

0x01 Optimization of Collection#

Optimization Strategy for Coordinate Acquisition Frequency:#

1. The system has default acquisition frequencies for personnel and vehicles, which are different.

2. When consecutive collection points are stationary or have small differences (within the threshold range), the coordinate acquisition frequency can be appropriately slowed down.

3. When the distance between consecutive collection points is greater than the threshold range, the coordinate acquisition frequency can be appropriately increased.

Optimization of Coordinate Acquisition Program Keep-Alive:#

The keep-alive mechanism includes: persistent notification bar, dual-process guarding, broadcast screen lock, and custom screen lock.

Optimization of Coordinate Accuracy#

The signal strength of coordinates has a significant impact on positioning accuracy. For example, when the device is indoors or under tall buildings, the coordinate signal is significantly weakened. The following optimization strategies can be used:

1. Record signal strength as one of the filtering conditions for subsequent trajectory outlier points.

2. When the signal is weak and exceeds a certain threshold, switch to Baidu positioning solution.

0x02 Fitting#

Strategies for optimizing trajectory points at the algorithm level. Depending on different implementation conditions and display requirements, trajectory point fitting research is conducted from three different directions.

1. Road Network Matching Fitting Based on Road Lines#

As the name suggests, this solution requires road line data. The principle is to match each trajectory point to the node with the closest vertical distance to the road and connect the previous and next points along the road.
Advantages: The trajectory is entirely on the road, resulting in a visually pleasing display.
Disadvantages: It relies on the completeness of road data and may result in distorted display.

2. Denoising Algorithm Based on Spatiotemporal Clustering#

The idea of this algorithm is to cluster trajectory points in space and time, while preserving the characteristics of the points as much as possible, in order to reduce the clutter caused by tangled trajectory points. However, this algorithm is not just a conventional spatial clustering algorithm. Since trajectories have a natural time attribute, not considering the time dimension of trajectories will result in the loss of many trajectory feature information. For example, on a two-way road, if the time dimension is not considered, the trajectory points on both sides will be clustered onto one side.
Advantages: Solves the problem of tangled trajectory points in display.
Disadvantages: Does not handle the connection between trajectory points smoothly.

3. Trajectory Optimization Solution Based on Kalman Filtering#

Kalman filtering is an algorithm that uses a linear system state equation to estimate the system state optimally based on input-output observation data. In trajectory processing, it can adjust the trajectory position by predicting the deviation between predicted trajectory points and actual trajectory points, achieving trajectory smoothing.
Advantages: Smooths the trajectory line, resulting in a more visually pleasing display.
Disadvantages: Difficult to control the level of smoothness, resulting in distorted trajectory, blurred trajectory features, and trajectory noise points greatly affecting the overall smoothing effect.

4. Final Fitting Solution#

Each of the above solutions has its advantages and disadvantages, but if they can be effectively combined with other data processing processes, the quality of trajectory points will be further improved. The specific description is as follows:

Remove some trajectory points with large errors based on coordinate accuracy parameters.
Remove some "outlier points" based on abnormal changes in trajectory point velocity.
Aggregate trajectory points based on spatiotemporal clustering algorithm.
Smooth and beautify the trajectory using Kalman filtering, while controlling excessive smoothness.
For vehicle trajectories, use road network matching algorithm when there is complete road line data.

0x03 Beautification and Animation#

1. Smooth Moving People (Vehicles)
   

Static icons cannot represent real changes, and icons that jump with the acquisition of position coordinates appear abrupt. If the position changes of people (vehicles) can be displayed in real-time and smoothly, it will give users a stronger sense of "participation". Taking people as an example, to achieve this goal, design 16 directional icons for personnel and select different icons based on the angle between coordinate points. The icon changes when people move forward are calculated based on the distance between two points and the playback speed, resulting in effects such as the swinging of hands when people move forward.

2. Flowing Trajectory Arrows
   

The flowing arrows not only add dynamic effects to the overall trajectory display but also indicate the direction of the trajectory. However, if the trajectory arrows are too dense, they will also affect the aesthetics of the trajectory. Therefore, when the map is zoomed to a certain level, the trajectory arrow flow effect appears.

3. "Didi"-like Multi-Trajectory Display Effect
   

The trajectory display solution used by "Didi" and similar internet platforms has been increasingly accepted by the public, especially for real-time display of multiple vehicles (personnel) trajectories. Through continuous research on trajectory big data storage, trajectory information flow, and front-end display algorithms, the display can now be comparable to such solutions. It has also been verified in actual projects, such as real-time trajectory tracking of 16,000 vehicles in a dust control project for an entire city.

4. 2D and 3D Integrated Trajectory Display Effects
   

Displaying trajectories in a 3D scene will provide more visual intuitiveness and impact. By leveraging the ideas of game scene display, users will have a better sense of interaction.