Line Approximation Tools for Python.

Karl Skretting, University of Stavanger.

Contents on this page:	Relevant papers and links to other pages:
A brief introduction Some example problems Methods Results Files and details	The presentation given at the NOBIM conference in Tromsø, June 7th-8th 2023.

1. A brief introduction

This page may be of interest to readers working on problems where a set of points needs to be approximated by a smaller number of straight line segments. The example problems are solved using Python.

The content was originally developed in connection with a presentation I gave at the NOBIM conference in Tromsø in June 2023. Since then, only minor updates have been made. Although I had intended to expand on this work, that plan was never fully realized—so you’ll find several “more to be inserted here” placeholders throughout the page.

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[t_i] where t_i 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 N-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.

`funAFCCSP.py`	Functions for Always Forward and Cardinality Constrained Shortest Path algorithm.
`testAFCCSP.py`	Functions that test and demonstrate functions in `funAFCCSP.py`.
`py_fun_and_test.zip`	A zip-file containing, among several Python-files, `funMyTools.py`
`clsLineApprox.py`	Mainly the class `LineApprox`
`testLineApprox.py`	Functions that test and demonstrate `clsLineApprox.py`.
`testLineApproxOnGpx.py`	Functions that test and demonstrate `clsLineApprox.py` using GPX data file.
`testAustralia.py`	Functions that test and demonstrate `clsLineApprox.py` using Australia contour.
`australia.gif`	Image file used in `testAustralia.py`.
`australiaThin.gif`	Image file used in `testAustralia.py`.

Last update: July 4th, 2025. Karl Skretting

Visit my home page.