performance - Fast plane fitting to many points -

i'm looking fit plane set of ~ 6-10k 3d points. i'm looking fast possible, , accuracy not highest concern (frankly plane can off +-10 degrees in of cardinal axes).

my current approach use best of best fit, it's incredibly slow (i'm hoping extract planes @ rate of 10-50k times each time run algorithm, , @ rate finish in weeks, opposed hours) works on possible combinations of 6000 points, ~35,000,000,000 iterations, , frankly has higher accuracy need.

does know of weaker plane-fitting techniques might speed algorithm considerably?

edit:

i've managed number of iterations down ~42k creating planes @ each possible 3d angle (stepping through @ 5 degrees each time) , testing existing points against these find best plane, instead of fitting planes points have.

i'm sure there's gained here divide , conquering too, although worry jump straight past best plane.

use standard plane equation ax + + cz + d = 0, , write equation matrix multiplication. p unknown 4x1 [a;b;c;d]

g = [x y z 1];  % represent point augmented row vector g*p = 0;        % point on plane 

now expand actual points, nx4 matrix g. result no longer 0, it's error you're trying minimize.

g*p = e;   % e nx1 vector 

so want closest vector null-space of g, can found svd. let's test:

% generate test data = 2; b = 3; c = 2.5; d = -1;  g = 10*rand(100, 2);  % x , y test points % compute z plane, add noise (zero-mean!) g(:,3) = -(a*g(:,1) + b*g(:,2) + d) / c + 0.1*randn(100,1);  g(:,4) = ones(100,1);   % augment matrix  [u s v] = svd(g, 0); p = v(:,4);             % last column plane equation 

ok, remember p can vary scalar. show match:

scalar = 2*p./p(1); p./scalar 

ans = 2.0000 3.0038 2.5037 -0.9997