Direction that is perpendicular to a collection of 3D points?

Question

I have a collection of 3D points which form an imperfect circle and are stored in the order in which they appear in the circle. I'm positioning an object in the centre of the ring by calculating the mean position of all of the points, which works fine. Now, what I want is for the object in the centre to be facing up/down relative to the rest of the points (i.e perpendicular to the ring).

I've included an image to help clarify what I mean. Does anyone know of an algorithm that would be suitable for this?

Answer 1

You have to compute the plane that your points form and get its normal.

If the points are perfectly coplanar, just get three of them, a, b, and c, and compute two vectors. The normal vector n is the cross product of them:

v1 = b - a;
v2 = c - a;
n = v1 x v2;

If the points are not perfectly coplanar, you can get the plane that best fits the points and then, its normal. You can get the plane by solving a linear equation system of the form Ax=0. Since the general equation of a plane is Ax + By + Cz + D = 0, you get one equation per 3D point, obtaining this system:

| x1 y1 z1 1 |   | A |   |  0  |
| x2 y2 z2 1 | x | B | = |  0  |
| x3 y3 z3 1 |   | C |   |  0  |
|    ...     |   | D |   | ... |
| xn yn zn 1 |           |  0  |

The normal vector is (A, B, C).

Answer 2

Elaborating on a previous answer, you get a system of n equations in 4 unknowns when you solve for the best hyperplane normal vector with n points. You need to set one of the unknown coefficients (say D) to a constant like 1 and move the corresponding data column to the right hand side so that you don't get the trivial solution A=B=C=D=0. You can safely set one coefficient to 1 if it is non-zero because the solution A,B,C,D is still a solution if you scale it. So you get a system of n equations in 3 unknowns where the right hand side is a vector of all -1 instead of the zero vector, and your data matrix is simply your matrix of points and your unknown coefficients are A,B,C. In general such a system is overdetermined if you have more than 3 points so you need to solve it using linear regression. See http://en.wikipedia.org/wiki/Linear_regression to get the matrix formula for solving for the 3 coefficients using least squares best fit.