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

 This thread is locked; no one can reply to it.
 Most ideal straight line through points [MATH]
 Ariesnl 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)Current project: [Star Trek Project ] Join if you want ;-)
 BitCruncher Member #11,279 August 2009 Sounds like you're looking for the line of best fit
 torhu Member #2,727 September 2002 Linear regression?
 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_regressionBasically, take the sum of the squared residuals as an objective function and minimize it.
 Ariesnl 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 :{"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"}...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) linesI 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 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"} -----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 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 algorithm1. 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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads