Getting curve details from points

Question

I have a List of 2D points. What's an efficient way of iterating through the points in order to determine whether the list of points are in a straight line, or curved (and to what degree). I'd like to avoid simply getting slopes between smaller subsets. How would I go about doing this?

Thanks for any help

Edit: Thanks for the response. To clarify, I don't need it to be numerically accurate, but I'd like to determine if the user has created a curved shape with their mouse and, if so, how sharp the curve is. The values are not too important, as long as it's possible to determine the difference between a sharp curve and a slightly softer one.

Answer 1

If you simply want to know if all your points fit more or less on a curve of degree d, simply apply Lagrange interpolation on the endpoints and d-2 equally spaced points from inside your array. This will give you a polynomial of degree d.

Once you have your curve, simply iterate over the array and see how far away from the curve each point is. If they're farther than a threshold, your data doesn't fit your degree d polynomial.

Edit: I should mention that iterating through values of d is a finite process. Once d reaches the number of points you have, you'll get a perfect fit because of how Lagrange interpolation works.

Answer 2

To test if it's a straight line, compute the correlation coefficient. I'm sure that's covered on wikipedia.

To test if it's curved is more involved. You need to know what kind of curves you expect, and fit against those.

Answer 3

Here is a method to calculate angle: Calculate Angle between 2 points using C#

Simply calculate angle between each and every point in your list and create list of angles, then compare if angles list values are different. If they are not different then it means it's straight line, otherwise it's curve...

If it's a straight line then angle between all points has to be a same.

Answer 4

The question is really hazy here: "I'd like to avoid simply getting slopes between smaller substes"

You probably want interpolation a-la B-splines. They use two points and two extra control points if memory serves me. Implementations are ubiquitous since way back (at least 1980's). This should get you underway

Remember that you'll probably need to add control points to make the curve meet the endpoints. One trick to make sure those are reached is to simply duplicate the endpoints as extra controlpoints.

Cheers

Update Added link to codeproject it would appear that what I remember from back in the 80's could have been Bezier curves - a predecessor of sorts.