- Online Community 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]
Member #2,902
November 2002

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)

Member #11,279
August 2009

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

Member #2,727
September 2002

Member #12,293
October 2010

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

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

Member #2,902
November 2002

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

Like this :


...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)

Chris Katko
Member #1,881
January 2002

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


“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs

Member #7,827
October 2006

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: