0

I would like to find the best fit plane from a list of 3D points. It means the plane has the least square distance from all the points. I read the article

Best fit plane by minimizing orthogonal distances
and 3D Least Squares Plane

I fully understand the solutio but it turns other to be impractical in my situation. I need to read a very very large list of 3d points, direcltly impementation would result in ill posed problem. Even I subtract the data with their average,(refere to the document here-> part3 : http://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf) the number is still very large. So what can I do?

Is there an iterative way to implement it ?

I have changed the way to ask the question, I hope may be there are someone can give me more advices on it ?

Given a list of 3D Points
{(x0,y0,z0),
(x1,y1,z1)...
(xn-1,yn-1,zn-1)}

I would like to construct a plane by fitting all the 3D points. In this sense, I mean to find the plane with format (Ax+By+Cy+D = 0), thus its uses four parameters(A,B,C,D) to characterize a plane. The sum of distance between each point and the plane should be minimium.

I do try the menthod provided in the below link
http://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf

But there are two problems:
-During calculation, the above algorithm needs to do summation of all points value, which lead to overflow problem if my number of points increases

-given newly added points, it has to do all the calculation again, is there a way to use the before calculated plane parameter and the newly given points to somehow fine tune the planes parameters?

PS:I am a bit greedy, if we need to involve all the points, it is possible that the plane finally obtained isn't good enough.I am thinking of using random sample consensus(RANSAC), is it the right direction?

Community
  • 1
  • 1
Carl
  • 105
  • 3
  • 12
  • 2
    Please be more specific at why the solutions at the link you gave do not work. The second link explicitly gives a very good approach. – Petr Oct 13 '15 at 11:53
  • Most of the algorithm i read need to computation the sum of all x coordinate or the y coodinate, but since my points are numerous. the resulting value always cause overflow. Thus it is the problem. – Carl Oct 13 '15 at 12:49
  • why don't you use a floating point type? Anyway your answer will be floating point... – Petr Oct 13 '15 at 12:50

1 Answers1

1

If you are expecting a plane then most of the points are not that useful since even a handful should give you a good approximation of the final solution (module a bit more noise).

So here's the solution. Sample down your data set to something that works and run the smaller set through the fitting algorithm.

If you are not expecting that the points are on a plane then sub-sampling should still work, but you must consider error ranges for any solution (since they will likely be fairly big).

Sorin
  • 11,863
  • 22
  • 26