Given a set of points, how can I approximate the main axis of its shape?

Question

Given the "shape" drawn by the user, I would like to "normalize" it so that they all have the same size and orientation. We have a set of points. I can approximate the size with a bounding box or circle, but the orientation is a bit more complicated.

The right way to do this, I think, is to calculate majoraxis its bounding ellipse . For this you need to calculate the eigenvector covariance matrix . It will probably be too difficult for my need, as I am looking for a good enough grade. Choosing min, max and 20 random points may be some kind of starter. Is there an easy way to get closer to this?

Edit : I found the “Power Mode” for iteratively approximating the eigenvector. Wikipedia article . For now, I like David's answer .

Answer 1

You would calculate the eigenvectors of the 2x2 matrix, which can be done with a few simple formulas, so it’s not so difficult. In pseudo code:

// 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 adding up only a few of the points to get an estimate if you expect the subset of points you have chosen to represent the complete set.

Change I think that x and y should be converted to a zero-average, that is, subtract the average from all x, y first (eed3si9n).

Answer 2

Here's a thought ... What if you did a linear regression on the points and used the slope of the resulting line? If not all points, at least a sample of them.

A value of r ^ 2 will also give you information about the general form. The closer to 0, the greater the circular / uniform shape (circle / square). The closer to 1, the more elongated the shape (oval / rectangle).

Answer 3

The ultimate solution to this problem is the PCA.
I wish I could find a nice little implementation so that you can turn to ...