title: Fast plane fitting to many points
body: <p>I'm looking to fit a plane to a set of ~ 6-10k 3D points. I'm looking to do this as fast as possible, and accuracy is not the highest concern (frankly the plane can be off by +-10 degrees in any of the cardinal axes).</p>
  
  <p>My current approach is to use best of best fit, but it's incredibly slow (I'm hoping to extract planes at a rate of about 10-50k times each time I run the algorithm, and at this rate it would finish in weeks, as opposed to hours) as it works on all possible combinations of 6000 points, so ~35,000,000,000 iterations, and frankly it has a much higher accuracy than I need.</p>
  
  <p>Does anybody know of any weaker plane-fitting techniques that might speed my algorithm up considerably?</p>
  
  <p>EDIT:</p>
  
  <p>I've managed to get the number of iterations down to ~42k by creating planes at each possible 3D angle (stepping through at 5 degrees each time) and testing the existing points against these to find the best plane, instead of fitting planes to the points I have.</p>
  
  <p>I'm sure there's something to be gained here by divide and conquering too, although I worry I could jump straight past the best plane.</p>