# Detecting Planes through Point Cloud

Having a point cloud say (10000 points) which are randomly dispersed in 3D unit cube, the question is how to find planes within the cube that include more points with an acceptable tolerance (user choice say, 0.1 where the boundaries of the cube of point cloud are ([0,1],[0,1],[0,1])?
I thought since it is a geometry problem would be asked here, however your comments are more than welcome!

-
You have to be more precise about what a tolerance of 0.1 means. This can completly change your optimization problem. For example does it mean: for a given plane count the number of points that have an euclidean distance of less than 0.1 and try the find the plane where this number is maximal? This would be solved with RANSAC and has the advantage that it is relativly robust to outliers. Or does it maybe mean that the sum of squares of vertical distances should be less than 0.1 (linear least squares minimizes this sum, so if such a plane exists, it's that one)? – Peter Sheldrick Oct 31 '11 at 13:09
@PeterSheldrick Thanks for the comment. The first approach is of my interest for which the absolute euclidean distance is being measured. Furthermore I should add that it is desired that all points finally being associated with a plane even in the worst case where there were only three points for planes satisfying the condition of tolerance. – Developer Oct 31 '11 at 13:28
in RANSAC you just randomly pick three points, find the plane through them, evaluate your function to be minimized (for example counting number of points less than a tolerance) and just repeat that for another random three points (while saving the 'best' plane so far) until you think what you have is good enough. – Peter Sheldrick Oct 31 '11 at 13:37
A good starting point is the Hough transform, which is often used in computer vision applications. – mjqxxxx Nov 1 '11 at 5:23
@PeterSheldrick: This is my second time I'm being recommended to consider RANSAC. The first was on my other post. Your simple description above could help me to solve another problem even being not fully followed RANSAC stages. If you believe RANSAC could be one of the best solution could I ask you give the community a gift by answering the question in details? Mathematical background and some pseudo-code also could be helpful. – Developer Nov 2 '11 at 11:16