title: Fitting a plane to a set of points using Singular Value Decomposition
body: <p>I am trying to fit a plane to a set of points in 3D space. I originally tried an exhaustive least squares fit but this turned out to be way too slow. I read that the most efficient solution would be to perform singular value decompositon.</p>
  
  <p>The maths for this is beyond me, but I have found a bunch of resources to try get this to work.</p>
  
  <p>According to the answer in <a href="https://math.stackexchange.com/questions/99299/best-fitting-plane-given-a-set-of-points">this post</a>, I need to compute the centroid of the points, subtract the centroid from all of the points, put them into a 3xN matrix and perform SVD. I then take the left singular vector as the normal for the plane.</p>
  
  <p>So far so good.</p>
  
  <p>I found a C#  maths library called alglib which has a function for SVD. The definition of the algorithm can be found <a href="http://www.alglib.net/matrixops/general/svd.php" rel="nofollow noreferrer">here</a>. This is where I am having issues, as it requires two more matrices as inputs in addition to the data points matrix, and I don't really understand what to put inside them. I ran this code regardless:</p>
  
  <pre><code>Vector3 centroid = getCentroid(planeVerts);
      double[,] dataMat = substractCentroid(planeVerts, centroid);
      double[] w = new double[3];
      double[,] u = new double[1,1];
      double[,] t = new double[1, 1];
  
      bool a = alglib.svd.rmatrixsvd(dataMat, 3, planeVerts.Length, 0, 0, 2, ref w, ref u, ref t);
  
      Vector3 planeNorm = new Vector3((float) w[0], (float) w[1], (float) w[2]);
  </code></pre>
  
  <p>So in theory I thought "w" would contain my plane normal, but unfortunately it doesn't (I visualised it in Unity3D and it was at the wrong angle). The "u" and "t" matrices are the ones which confound me, and I don't really know what I should be setting them to.</p>
  
  <p>The detailed API for the rmatrixsvd function can be found <a href="http://www.alglib.net/translator/man/manual.csharp.html#unit_svd" rel="nofollow noreferrer">here</a>.</p>
  
  <p>Are there any maths or algorithm veterans who could share their knowledge on this matter? I need to use C# as my project is in Unity3D. I'll be happy to provide more info if needed.</p>