Most ideal straight line through points [MATH]
Ariesnl

I'm looking for a way to get a set of the most ideal straight lines "through" a set of points that not necessarily ly ON that line...
A sort of noise ignoring line tracker..

Any ideas ?

Douglass Peucker reduction does the job almost, but not quite..
I tried an area based version, with sometimes better results.. but also sometimes worse..

Any ideas ?

BitCruncher

Sounds like you're looking for the line of best fit

torhu

Linear regression?

Polybios

I don't know what you want to do in particular, but this sounds like a good start:

https://en.wikipedia.org/wiki/Simple_linear_regression

Basically, take the sum of the squared residuals as an objective function and minimize it.

Ariesnl

I need to detect the best straight lines over the "almost straight" slopes of a "wave like" pattern of points..

Like this :

{"name":"611156","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/8\/d88bb0ac8fd01ea1f7ed8b6b5bd02d8f.png","w":1484,"h":769,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/8\/d88bb0ac8fd01ea1f7ed8b6b5bd02d8f"}611156

...And that "wave pattern" can be in ANY direction ! ! !
so it is NOT a function !

The red lines are the most important..
The input is in points wich are sorted and made into ( a lot of) lines
I need the straight red lines , and the blue ones , but that is easy.

I have a working algorithm using douglass peucker reduction , but it is far from perfect, so I was wondering what other ways there might be.

Chris Katko

That sounds like you just want a spline (/ b-curve / etc), and then you just take the tangents.

{"name":"1200px-Parametic_Cubic_Spline.svg.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/b\/8bceabb0eb78b6af527d48549428d8ca.png","w":1200,"h":818,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/b\/8bceabb0eb78b6af527d48549428d8ca"}1200px-Parametic_Cubic_Spline.svg.png

https://www.wikiwand.com/en/Spline_(mathematics)

SiegeLord

I'd approach it as an optimization problem. I'd parametrize the solution as a set of line segments, defined by the coordinates of their end points. Then I'd define the loss function, which would be the minimum sum of distances between the segments and the data points. This can be implemented by computing the distance from each data point to each segment, and then picking the smallest such distance. I'd also maybe penalize the total length of line segments. Then I'd follow this algorithm

1. Start with a single line segment, two end points.
2. Minimize the loss by adjusting the end points using your favorite algorithm.
3. Add an additional end point, e.g. by subdividing an existing line segment.
4. Repeat 2, if the new loss isn't a lot better than the old loss, stop the algorithm.

Thread #617178. Printed from Allegro.cc