Best way to group 3d points into planes, if any If I have some 3d points, how can I discover parallel planes within them (not just arbitrary planes).

I want to know how many "levels" or "floors" something can travel within, after it has done so, so I want to cluster the positions into planes.

Some of them might not be in a plane, most of them are noisy (not perfectly planar), and I have no knowledge of the world orientation, so the planes aren't necessarily orthogonal to some known axis.

I know one way is a 3d-hough transform, but is there something better?
A reasonable approach is a continuous sample consensus method. The hough transform can be though of as a discrete sample consensus method, and so becomes intractable for some problems. Sample consensus is nice, because we can impose arbitrary constraints, and handle even the most horrific noise.

Getting Planes: Sample Consensus

The idea is determine the minimum number of observations needed to form a hypothesis, and then check how many observations agree with that hypothesis. We'll call those observations "inliers".


Three point determine a plane. Select three points (deterministically, at random, whatever) from your dataset, fit a plane to them.
Check how many points in your point cloud "support" the plane. Meaning that the plane existing in the world could explain what the sensor saw; the observations "support" the conclusion that the plane exists. For your case, a reasonable metric for "support" would be perpendicular distance to the plane.
In postprocessing, you might cull planes that don't have sufficient width.


Extracting Parallel Planes: Normal Binning

If you don't have a prior on the structure of your data other than "has parallel planes", then you're likely trapped trying to discover as many planes as possible and then filtering for parallel ones.

One might consider a "binning" approach


Start with the first plane, and say its normal belongs to $bin_0$
For each discovered plane, check the angle it makes with every existing bin
If the angle is less than $\epsilon$, add that plane to $bin_n$
If the angle is greater than (or equal, for completeness) to $\epsilon$, create a new bin, $bin_{n+1}$


Presumably the largest bin is the thing you want if you have culled small planes.

Other Notes

Sample consensus will generally perform better if, after fitting to data and finding points that agree, you run a quick optimization to fit a plane to all of the inlier points. Then recompute inliers, and re-run the optimization. After all, it's quite unlikely that the three points you happened to choose were exactly the true plane. Much more likely is that varying plane parameters to minimize point-to-plane error over all of the inlier observations will yield a nice plane, with the noise averaged out.