Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Most ideal straight line through points [MATH]

This thread is locked; no one can reply to it. rss feed Print
Most ideal straight line through points [MATH]
Ariesnl
Member #2,902
November 2002
avatar

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 ?

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

BitCruncher
Member #11,279
August 2009
avatar

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

torhu
Member #2,727
September 2002
avatar

Polybios
Member #12,293
October 2010

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
Member #2,902
November 2002
avatar

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.

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

Chris Katko
Member #1,881
January 2002
avatar

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)

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

SiegeLord
Member #7,827
October 2006
avatar

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.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Go to: