Line of Best Fit For Points in Three Dimensional SpaceDate: 11/22/2005 at 08:44:19 From: Abhi Subject: fitting a line to points in 3D space I have a problem where I have a set of points in 3D space. I know the (X,Y,Z) coordinates of the points. I have to fit a line so that the line is least distant from the points (least square fit is minimum, or any other applicable method). I have to code this in terms of a program. Please let me know if there are simple ways to solve this problem on a computer. Date: 11/22/2005 at 22:27:18 From: Doctor George Subject: Re: fitting a line to points in 3D space Hi Abhi, Thanks for writing to Doctor Math. The line you are looking for is called the 3D Orthogonal Distance Regression (ODR) line. This line can be computed without writing a lot of computer code if you already have code for the Eigen decomposition or the simgular value decomposition (SVD). Let's parameterize the line like this, x = x0 + at y = y0 + bt z = z0 + ct where (x0,y0,z0) is a point on the line and (a,b,c) is a unit vector. We want to minimize the sum of squared distances from the points to the line. The vector equation for the sum leads to f(x0,y0,z0,a,b,c) = SUM{[c(yi - y0) - b(z - z0)]^2 + [a(zi - z0) - c(x - x0)]^2 + [b(xi - x0) - a(y - y0)]^2} If we take the first derivatives with respect to x0, y0, and z0 and set the results equal to zero we get equations that can be manipulated to yield (x0-xbar)/a = (y0-ybar)/b = (z0-zbar)/c where (xbar,ybar,zbar) is the centroid of the data. Notice that (xbar,ybar,zbar) is a valid choice for (x0,y0,z0). This proves that the centroid is on the ODR line, and so we choose it for (x0,y0,z0). Now we just need to find vector (a,b,c). We need a little notation to make the next steps easier. Let C be the centroid, let L be the ODR line, and let P be the plane through C such L is perpendicular to P. We are doing this in order to make use of the ODR plane analysis, which is closely related. By the Pythagorean theorem, for a set of points Xi, SUM[distance(Xi,L)^2] = SUM[distance(Xi,C)^2] - SUM[distance(Xi,P)^2] We want to choose (a,b,c) so that SUM[distance(Xi,L)^2] is minimized. This is the same as maximizing SUM[distance(Xi,P)^2]. (Notice that SUM[distance(Xi,C)^2] is a constant). The ODR plane analysis can be found here: Orthogonal Distance Regression Planes http://mathforum.org/library/drmath/view/63765.html The ODR plane analysis uses matrices A and M. For the ODR plane we want the eigen vector of A that corresponds to its smallest eigenvalue. This is the same as the singular vector of M that corresponds to its smallest singular value. For the ODR line we instead want the eigen vector of A that corresponds to its largest eigenvalue, or the singular vector of M that corresponds to its largest singular value. This maximizes the desired sum. The decomposition of A or M gives us the vectors for both the ODR plane and the ODR line at the same time. To summarize, the 3D ODR line contains the centroid, and has as its direction vector the eigen vector (or singular vector) referred to above. Does that make sense? Write again if you need more help. - Doctor George, The Math Forum http://mathforum.org/dr.math/ Date: 11/23/2005 at 12:53:22 From: Abhi Subject: fitting a line to points in 3D space Thank you so much for that answer. It was very helpful. - Abhi |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/