Jump to content
  • Advertisement
taxfromdk

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!