Problem Detail: Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to draw the surface that passes from all the points. I need a metric that tells me how fine the structure of the plane is preserved. Or how planar is the surface. What I have thought is, take random 3 points among 10 and derive the plane equation in terms of $ax + by + cz = d$. Then, for each remaining point $p(p_x,p_y,p_z)$, calculate the summation $ap_x + bp_y + cp_z$. Store the results and take the standard deviation. However this method fails for the following reason:
If there are 9 points on the same plane and only 1 point is far away, and if I pick the point who is far away, then the equation I generate is way too different then the plane defined by remaining 9 points. Plugging the coordinates of remaining points into the equation of the plane, I’ll get too many different results. Therefore, even though the surface is almost planar, standard deviation will be so high, depending on the generated equation. This problem (I think) can be reduced to line cover problem (covering a set of points in 2D with minimum number of lines), hence, NP-Complete. Or is it really? Is there a polynomial time algorithm that guarantees to find a value for all types of point sets? I thought about starting not with 3 but with 4 points, then testing the other points. Does that work?
If there are 9 points on the same plane and only 1 point is far away, and if I pick the point who is far away, then the equation I generate is way too different then the plane defined by remaining 9 points. Plugging the coordinates of remaining points into the equation of the plane, I’ll get too many different results. Therefore, even though the surface is almost planar, standard deviation will be so high, depending on the generated equation. This problem (I think) can be reduced to line cover problem (covering a set of points in 2D with minimum number of lines), hence, NP-Complete. Or is it really? Is there a polynomial time algorithm that guarantees to find a value for all types of point sets? I thought about starting not with 3 but with 4 points, then testing the other points. Does that work?
Asked By : cagirici
Answered By : D.W.
Option 1: Use least squares fit to find the closest plane. Then, measure the average squared error (the sum of the squared residuals). Option 2: Use robust regression instead of least squares. Or, use RANSAC. These will handle outliers better. All of these run in polynomial time.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28365 Ask a Question Download Related Notes/Documents
