# How close are pointa forming a line

This topic is 437 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I need a measure for how close a collection of points is to forming a straight line in 2d.

Currently I use Principle Component Analysis in 2d and take the mean of the of square on the second axis.

It works fine, but I feel it is overkill.

I would like something simpler I could express in a li rary like Tensorflow.

Is there a simpler way?

##### Share on other sites

What you did sounds very reasonable: Look at what fraction of the variance is explained by the top factor from PCA. The closer to 1 that number is, the closer the points are to forming a line.

##### Share on other sites

I have used least squares methods in the past, but they are axis dependent and give only approximizations. (Which means the result improves if you use the resulting line as the reference coordinate system for the next iteration).

Not sure if PCA is the same thing i did, but guess so.

So what i came up with is using average weighted angles, utilizing periodical nature of angles to get average lines or crosses. (I use degree 2 for lines to find curvature directions on meshes, and degree 4 to build crossfields from that.)

It calculates exact solution in one step and should work well for you too:

std::vector<vec2> points;
points.push_back(vec2(-3,1));
points.push_back(vec2(-1,2));
points.push_back(vec2(1,-2));
points.push_back(vec2(3,-1));
points.push_back(vec2(5,-2));
points.push_back(vec2(7,0));

vec2 com(0,0);
for (int i=0; i<points.size(); i++)
{
com += points[i];
}
com /= float(points.size());

//for (int i=0; i<points.size(); i++) // some code i've used to proof axis independence
//{
//	quat r; r.FromAxisAndAngle (vec(0,0,1), -20.0f/180.0f*PI);
//	points[i] = r.Rotate(points[i] - com) + com;
//}

float sinA = 0;
float cosA = 0;

float const degree = 2; // use 1 for vectors, 2 for lines, 4 for crosses etc...

for (int i=0; i<points.size(); i++)
{
vec2 d = points[i] - com;
float weight = d.Dot(d); // can use anything here, but i use squared distance as the weight, which has some backing from physics laws; you could multiply this also with point mass for axample.

float angle = atan2(d[0], d[1]);
angle *= degree;
sinA += sin(angle) * weight;
cosA += cos(angle) * weight;
}

float averageAngle = atan2 (sinA, cosA) / degree;

vec2 averageLine (sin(averageAngle), cos(averageAngle));

// visualize result

ImGui::Text("averageAngle: %f", averageAngle/PI*180.0f);
RenderVector (com, averageLine, 1,1,1);
RenderVector (com, -averageLine, 1,1,1);
for (int i=0; i<points.size(); i++) RenderPoint (points[i], 1,1,1);

I guess this is a common method but i don't know how people call it.

##### Share on other sites
On 9/4/2018 at 2:38 PM, JoeJ said:

I have used least squares methods in the past, but they are axis dependent and give only approximizations. (Which means the result improves if you use the resulting line as the reference coordinate system for the next iteration).

Not sure if PCA is the same thing i did, but guess so.

No, PCA doesn't have any dependence on axes, since what it does can be described without coordinates.

Not every least squares method has the problem you describe either. You can use total least squares and again the result won't depend on the choice of coordinates.

Another idea would be to compute the area [or volume, or hypervolume, depending on the dimensionality of the problem] of the convex hull of the points, perhaps divided by some normalizing factor (e.g., the hypervolume of a hypersphere with the same diameter as the sample data). [EDIT: Thinking about it a bit more, that is actually a terrible idea: For instance, 3D points that all lie on a plane would pass the test even if they are not on a line.]

Edited by alvaro

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 9
• 56
• 16
• 19
• 26