Line Approximation Tools for Python.
Karl Skretting, University of Stavanger.
The page is still under construction.
1. A brief introduction
This page may interest readers that want to solve problems where a set of points
should be approximated by a smaller set of straight line segments. The example problems
are solved using Python.
2. Some example problems
The mathematical-like definition of the problem is:
From a path given by a large ordered set of points, x[i] = x[ti]
where ti are the time indexes for i in 1,2,3,...,L
and x is a scalar or more commonly a vector of N dimensions,
a subset of K of these points are to be selected, always first and last, such that the line segments
between these K points approximate the path as well as possible.
One way to express "as well as possible" is to say that the sum of all (squared) errors should be
as low as possible. Each point n is approximated by a point on the line segment
between selected point i where i is as large as possible but smaller or equal to n
and selected point j where j is as small as possible but larger (or equal) to n.
The approximation can be the orthogonal projection onto this line segment, or it can
be a point on the line segment given by the t-value of points i, j, and n.
The distance between a point and its approximation gives the error measure used,
here often the squared error (SE) is used.
The goal is to find a subset of K points where the sum of squared errors (SSE) is minimized.
A relaxation, and a more difficult problem, is to don't restrict the selected points
to be in the original set of points, to select points "freely" in the M-dimensional space.
- Robot path recording.
Several years ago we discussed how a robot path could be given by recording the movements
and orientations of a tool that were moved along the desired path. Typically, the sampling rate
would give more points than what is wanted in the path description, and a method to reduce the path
to a set of straight lines, and perhaps also circle segments, was required.
The problem was addressed by starting with some simpler problems as in the following points.
As I work on this problem only when there is no other, more urgent, activity the progress has
been slow. The original idea was abandoned before any result was ready.
- GPX track reduction.
more to be inserted here
- Contour coding.
more to be inserted here
3. Methods
more to be inserted here
3.1. Calculations of erros
more to be inserted here
3.2. Greedy algorithms
more to be inserted here
3.3. Optimal algorithm, AFCCSP
more to be inserted here
3.4. Adjust points freely
more to be inserted here
4. Results
more to be inserted here
5. Files and details
As a start only the functions for Always Forward and Cardinality Constrained Shortest Path
(AFCCSP) algorithm are included. These as independent and don't need any of
the other Python files I have made, although if you want to use data from gpx-file
some other code needs to be included or added.
I hope that I soon will include all files needed for the experiments done and
presented at NOBIM conference i Tromsø June 2023.
| |
Last update: June 20, 2023. Karl Skretting |
Visit my home page. |
