Sparsing lines/vectors build from data points or Angular Vector Track Simplification

by Nicole Faerber, 8th of August 2006

Problem Description

Assume a measuring device that measures distance and direction of movement. On certain events, like time, a measurement is taken and recorded. The result is a collection of data points the represent the movement. Same results can be achieved when moving on a raster grid and recording the coordinates.

If the movement was along a straight line then the recording contains a lot of redundant data, i.e. all the recorded data points between the start and the end point. Basically the start and end points would be enough to describe the same movement.

The difficulty is to judge which data points represent a significant or unsignificant recording.

Solution Description

The most interesting information that can be gathered from such a recording is the direction change of the movement. If the direction change is only minimal or none then the movement recording that leads to this is insignificant. Depending on the application "minimal" can be adjusted.

The direction is an angle of the movement vector towards a reference. Now assume four recorded data points A, B, C and D. The algorithm works as follows:

Image 1: Deletion of point

Since we keep the first reference point in the deletion case even smooth curves of several points will survive, see the following before and after examples. The red dots are the data points, a black line is a pure connection of two points:

Image 2: Original track

Image 3: AVTS track with minimum angle = 1,5 degree

First published here.