2
$\begingroup$

This comes from a programming problem from CodeAbbey, however, I cannot figure out the mathematical formula to solve the problem. Within the problem here we have a graph, then the same graph afterwards with all the points SHIFTED and ROTATED by an ambiguous amount, with some going off the graph as well, with only ONE point that does NOT go off the graph not following the same pattern

I know that there is a rotation formula: $$\begin{bmatrix}x'\\y'\end{bmatrix} =\begin{bmatrix}\cos \theta &-\sin \theta \\\sin \theta &\cos \theta \end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}. $$ (from Wikipedia's Rotation Article)

I also know you can easily solve tranformation: Simply calculate the change within distance...

However, when you are given only the before and afterimage of what points exist following both rotation and transformation (rather than one step at a time), how do I do this? Plug in distances into the rotation formula? Guess and check? Is there an easier way to do this?

$\endgroup$
6
  • $\begingroup$ "[W]hen you are given only the afterimage": do you mean you cannot find out where any points were before the transformation? Or do you mean you have the points before and after, but not the numerical parameters of the transformation? $\endgroup$
    – David K
    Jul 12, 2016 at 14:59
  • $\begingroup$ my bad, yes, I do have before and after, just no numbers $\endgroup$
    – Goodwin Lu
    Jul 12, 2016 at 15:15
  • $\begingroup$ Do you know which before and after points are paired up or do you have to figure that out, too? $\endgroup$
    – amd
    Jul 12, 2016 at 17:30
  • $\begingroup$ If you know exactly only three matched pairs ( 2 matched triangles in fact) that's enough to solve the problem .. of' course if their coordinates are accurate... $\endgroup$
    – Widawensen
    Jul 12, 2016 at 17:41
  • $\begingroup$ hmmm.... ah, it seems that the stars are listed in a random order, at least that's what it looks like to me. The designer of the problem didn't state that they were in order, and it doesn't look like that either (for example, the first point is -47.5 -10.4 in first sector while the first point in second sector is -14.8 10.9, which is obviously not where it shifted....)--this is made more obvious by the fact that the solution is "29 3", while we think it should only be off by 3 numbers due to the fact that only that much stars "fall off" the graph. That makes the problem so much harder than.. $\endgroup$
    – Goodwin Lu
    Jul 14, 2016 at 20:28

1 Answer 1

1
$\begingroup$

Given any translation (shift) followed by a rotation, you can achieve the same effect using just a rotation, although it will usually be a rotation around a different center. (If you combine the transformations in the other order, rotation then translation, they have the same effect as a mere rotation around yet another center.)

If you can identify the "before" and "after" locations of two points that undergo the same transformation(s), and if you know the coordinates of those points accurately enough, you (usually) can find the center and angle of an equivalent rotation as follows.

Find the perpendicular bisector of the line segment between the "before" and "after" locations of one of the points. The center of the rotation is on this line. Now find the perpendicular bisector of the segment between the "before" and "after" locations of the other point. The intersection of the two bisectors is the center of the rotation.

Now that you have the center of the (combined) rotation, you can determine the angle of rotation by constructing the segments from the center of rotation to the "before" and "after" images of a point and measuring the angles between those segments. If the center of the rotation is the point $(h,k)$ and the angle is $\theta$, the entire transformation then is described by this formula:

$$ \begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \begin{bmatrix} x - h \\ y - k \end{bmatrix} + \begin{bmatrix} h \\ k \end{bmatrix}. $$

If it is really necessary to find one rotation around $(0,0)$ and one translation that have this same effect when one is followed by the other, they can be obtained through a little algebra. (The exact answer depends on whether you want the translation to occur before the rotation or after.)

This does not work when you happen to pick two points such that both pairs of "before" and "after" locations have the same perpendicular bisector. In that case you don't find the center of the rotation, only a line it is on. If the lines are distinct but the angle between them is small, theoretically you can find the center of the rotation but any inaccuracies in the coordinates of the points is likely to be magnified. A better choice is two points whose "motions" are nearly perpendicular to each other.

$\endgroup$
4
  • $\begingroup$ hmmm.... very interesting thought... it seems it may not be possible for a real math formula, rather, I may have to guess and check for the "different center" (which is entirely possible since I must then try every x coordinate and then every y coordinate and their combination; although this would indeed use a ton of memory). I think the biggest problem is the fact that I have 100 points, rather than only say three points. Three points would make it really easy. $\endgroup$
    – Goodwin Lu
    Jul 14, 2016 at 20:21
  • $\begingroup$ The only "guess" in the method proposed in this answer is when you identify a point in the "after" image with the "same" point in the "before" image. Everything else (such as "find the perpendicular bisector" or "find the intersection of the two lines") can be done with exact formulas in coordinate geometry without any guesswork. I can look up references for the formulas if that's the difficulty. $\endgroup$
    – David K
    Jul 15, 2016 at 0:13
  • $\begingroup$ If there are multiple points (not just the one) that are not rotated and translated exactly the same as all the others, that could also cause trouble. Another possible problem is coordinates that are rounded off to too few digits, making the calculations inaccurate; you might need to repeat the procedure several times and "average" the results in that case. $\endgroup$
    – David K
    Jul 15, 2016 at 0:16
  • $\begingroup$ there is only one that is not precisely the same. All other points are rotated and translated by the same amount. $\endgroup$
    – Goodwin Lu
    Jul 15, 2016 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .