Given a set of points, how do I approximate the major axis of its shape?

Question

Given a "shape" drawn by the user, I would like to "normalize" it so they all have similar size and orientation. What we have is a set of points. I can approximate the size using bounding box or circle, but the orientation is a bit more tricky.

The right way to do it, I think, is to calculate the majoraxis of its bounding ellipse. To do that you need to calculate the eigenvector of the covariance matrix. Doing so likely will be way too complicated for my need, since I am looking for some good-enough estimate. Picking min, max, and 20 random points could be some starter. Is there an easy way to approximate this?

Edit: I found Power method to iteratively approximate eigenvector. Wikipedia article. So far I am liking David's answer.

Answer 1

You'd be calculating the eigenvectors of a 2x2 matrix, which can be done with a few simple formulas, so it's not that complicated. In pseudocode:

// sums are over all points
b = -(sum(x * x) - sum(y * y)) / (2 * sum(x * y))
evec1_x = b + sqrt(b ** 2 + 1)
evec1_y = 1
evec2_x = b - sqrt(b ** 2 + 1)
evec2_y = 1

You could even do this by summing over only some of the points to get an estimate, if you expect that your chosen subset of points would be representative of the full set.

Edit: I think x and y must be translated to zero-mean, i.e. subtract mean from all x, y first (eed3si9n).