Finding centre of rotation for a set of points [cl

Question

If I have an arbitrary set of points, and then the same set of points rotated by some degree, does anyone know of any algorithms to calculate/estimate where the centre of the rotation is? Or an area of study where these kinds of algorithms are needed? I am having trouble finding any relevant information.

Thanks

Answer 1

Very interesting problem. My knowledge on this is a bit out of date, but as I recall, there's some research in the use of subgraph analysis on this; that is, characterizing subsections of the set of points by the distances between the points and the variances therein, and then correlating those subgraph analyses between the before and after rotations.

This is, of course, assuming a very complex set of points with a nonuniform distribution.

Answer 2

It would be crazy overkill for this type of problem, but I think the functionality of the generalized Hough transform for object detection at least encompasses what you want, even though it's not quite meant for this purpose.

Given an arbitrary shape created from a set of points, and another arbitrary set of points, it tries to find the shape in the set of the points even though it's been rotated, scaled, and translated. You might be able to take out the scaling and translation and get what you want.

Basically what it would come down to is brute forcing possible rotation points to see which one fit the second set of points best.

Answer 3

Lets say you have one point (x, y), that moved to (x', y').

Then the center of rotation must lie on the line that is perpendicular to (x,y)-(x',y'), and that intersects the center (x,y)-(x',y').

Now take another point, (x2, y2), that moved to (x'2, y'2). This also gives rise to a line on which the center of rotation must be located on.

Now take these two lines and compute the intersection. There you have the center of rotation.

---

Update: If you don't have the correspondence of which point went where, it shouldn't be too hard to figure out. Here is a suggestion from top of my head: Find the center of mass of the "before"-points. Order the points according to their distance from this point. Now do the same with the "after"-points. The order of the two sets should now match. (The point closest to the center of mass before rotation, should be the point closest to the center of mass after rotation.)

Answer 4

You need to find some signature on your data set that allows to identify the points from the first set (A) with those on the second set (B).

An easy way is as follows:

• For every element E in A, find the two nearest points (N1, N2) and calculate the angle between N1,E,N2 resulting in three values: the angle and the distances from E to N1 and N2 (ang, d1, d2).

• Find 3 points in A with unique tuples (ang, d1, d2).

• For every element in B calculate also the distance to its two nearest neighbors and the angle. Find the 3 points matching those selected from A.

• Calculating the rotation is just a matter of geometric analysis.

update: you need 3 points to determine the rotation in 3D space. In 2D, two will do.

update 2: as others have commented on other posts, there may be symmetries in A that would stop you for finding the 3 unique triplets for (ang, d1, d2). In that case, for every one of the selected three points in A, you will have to perform a search over all the elements in B matching their triplets until some combination results in a rotation that works for all the elements in A.