Correction formula for two points

Question

This is painfully simple- sorry for that- but I'm not a math guy and could use some help. Imagine I have a surface that goes from $(0,0)$ to $(100,100)$- a square. On it, I expect to find two points from a previous measurement at $(10,10)$ and $(90,90)$- lets just say they were marked somehow. But someone messed with my surface. The rotated it, translated it, or both- all within the same plane.

Now when I go to look for my expected $(10,10)$ point $1$, I find that it is actually at $(8,13)$. And when I then look for my point $2$, I find it at $(95,80)$ (or something close where the distance between the points has not changed).

What is the formula I need to take any expected $(x,y)$ and apply a correction to yield my true $(x,y)$ position?

This is not a homework problem btw. It's a real world problem.

If you are allowing translations, your transformation looks like $T(\vec{x}) = A\vec{x} + \vec{b}$ where $A$ is 2x2 and $b$ is 2x1, so you have 6 unknowns to find out, but you only gave 2 points (4 equations). You need one more point. — gt6989b, Jun 18 '13 at 15:57
@Nicros -- do you know what an affine map is, or an isomorphism? Do you know how to multiply matrices? Probably not, judging by your question. Looks like a much simpler answer will be needed. — bubba, Jun 18 '13 at 16:42
@bubba I had to look it up, but you are right. But I do think this is the solution, so I will have to get smart on this :) — Nicros, Jun 18 '13 at 16:46
Your square is just shifted and rotated, right? It's not shrunk or enlarged, and it's not distorted in any way? If so, then you only have three unknowns, not 6, so the positions of two points is more than enough to determine the correction. — bubba, Jun 18 '13 at 16:49

score 1 · Answer 1 · answered Jun 18 '13 at 16:11

1

It depends on what structure you have on the function! It seems like you're talking about affine maps, so far. Affine maps are similar to linear maps that are isomorphisms, and can be treated either as linear isomorphisms up to translation, or as linear maps projecting a higher-dimensional space onto the affine space as a subset of projective space. If the origin were fixed, the map's values would be determined by the law $f(x+y)=f(x)+f(y)$. This would mean that if you added many copies of the same vector - tracing out a line - you would be able to add as many copies of the transformed vector to get the transform's value at the vector. So, what you need to calculate all the results of an affine map, i.e. a linear map plus a translation, is its value at a third point, which you can pretend is the origin of lines to the two values you know. Call this point $O$, and the transformation $T$. Then $(T(x)-T(O))+(T(y)-T(O)) = T(x+y)-T(O)$.

answered Jun 18 '13 at 16:11

Loki Clock

2,193

So I had to look up Affine Maps (told you I wasn't a math guy :) ). The problem definitely seems like an affine transformation. I'm not sure about the origin though. This would need to be calculated , which given two lines I can do. However, can you break this down for me a bit more? Like here's my points A1 and A2 for line A (my expected line), B1 and B2 points for my actual line, with point O as the origin (or intersection right?), how exactly do I calculate my actual C point given an expected point? – Nicros Jun 18 '13 at 16:42
1

So, for example, let $O=(0,0), T((0,0))=(2,3)$. Then $T((5,5)+(5,5))=T((5,5))-T(O)+T((5,5))-T(O)+T(O)=2T((5,5))-T(O)$. $\implies T((10,10))+T(O)=2T((5,5)) \implies (8,13)+(2,3)=2T((5,5)) \implies T((5,5))=(\frac{8+2}{2},\frac{13+3}{2}) = (5,8)$. – Loki Clock Jun 18 '13 at 16:43
I'm implementing this in C# as well, if that's interesting. So I would be creating a method like this: public Point GetCorrectedPoint(Point a1, Point a2, Point b1, Point b2, Point origin) – Nicros Jun 18 '13 at 16:44
Thanks! I will give this a go. – Nicros Jun 18 '13 at 16:46
Well, maybe you're a game programmer? Consider how you would rotate the game world around a player whose location is moving. You would translate the game coordinates to the player's origin, rotate, then translate back to your original origin. – Loki Clock Jun 18 '13 at 16:47
1

Nope, I'm an applications guy. This is software that drives a microscope and digitally detects cells on a slide. The problem is we want to automate re-detection, but when the slide is put back on the scope it is never in exactly the same position- so the 'known' points are always off. – Nicros Jun 18 '13 at 16:49
And we're assuming that distance(a1,a2) = distance(b1,b2), right? – bubba Jun 18 '13 at 16:52
@bubba Not at all. Affine maps include squash and skew transformations, as do linear maps. In fact, you can represent rotations by two combined skew transformations. – Loki Clock Jun 18 '13 at 16:53
@bubba Loki is correct, the distances are not always the same- for example when we put that slid on a different scope (we have many) it my have slightly different focus- which means the distance between those points is not always the same. However, I would be really interested in seeing the solution assuming the distance IS the same- as it may not play much of a role at all. – Nicros Jun 18 '13 at 16:58
Uh, stupid question for Loki- in your example, where does (5,5) come from? I'm assuming the (10,10) is my expected point and (8,13) is my actual from my question. – Nicros Jun 18 '13 at 19:27
My example is showing you how to get the image of $(5,5)$ from the information you provided plus the information I added - the third point and its image. This is a practical test value, because if you were to plot $(2,3), (5,8), (8,13)$ you would get a first approximation to the image of the line from $(0,0)$ to $(10,10)$. – Loki Clock Jun 18 '13 at 19:34
Ok- to make sure I understand this- what you describe is my origin at (2,3), and my first expected point (10,10) was transformed to (8,13). I think this is right? So I need to use poins A1 A2 from line 1 and points B1 B2 from line 2 to find my origin. Once I find that, I can use your example with that origin, and only the A1 (expected) and B1 (actual) to calculate an corrected (x,y)- your example was (5,5)? Apologies if I'm being dense, this is not my bag :) – Nicros Jun 18 '13 at 19:43
Your expected origin was $O:=(0,0)$, but was transformed to $(2,3)$. Yes, you can use two points on each line, find their intersection, and use that as the origin. So I assumed $O$ was their intersection, i.e. that $A1=B1=O$. The images of those lines will instead intersect at $T(O)$. You can use just the expected value of a point $p$ and the actual values of $A2, B2, O$ to calculate the actual value $T(p)$ of p. – Loki Clock Jun 18 '13 at 19:50

bubba · Accepted Answer · 2013-06-20T04:00:07.227

Here is some C# code:

using System;
using System.Windows;

class Mapper
{
   public static Point MapPoint(Point a1, Point a2, Point b1, Point b2, Point p)
   {
      Vector u = a2 - a1;         // Vector along source line a1-a2
      Vector v = b2 - b1;         // Vector along destination line b1-b2

      Point am = a1 + 0.5*u;      // Mid-point of line a1-a2
      Point bm = b1 + 0.5*v;      // Mid-point of line b1-b2

      double factor = 1 / (u.Length * v.Length);
      double cosA = (u*v) * factor;
      double sinA = Vector.CrossProduct(u,v) * factor;

      double x = (p - am).X * cosA - (p - am).Y * sinA + bm.X;
      double y = (p - am).X * sinA + (p - am).Y * cosA + bm.Y;

      return new Point(x,y);
   }

   static void Main(string[] args)
   {
      Point a1 = new Point(2,1);    Point a2 = new Point(8,5);   Point am = new Point(5,3);
      Point b1 = new Point(1,3);    Point b2 = new Point(5,9);   Point bm = new Point(3,6);

      Point p, q;
      p = a1;
      q = MapPoint(a1, a2, b1, b2, p);  
      Console.WriteLine("a1 maps to: " + q.ToString());  // q should = b1

      p = a2;  
      q = MapPoint(a1, a2, b1, b2, p);  
      Console.WriteLine("a2 maps to: " + q.ToString());  // q should = b2

      p = am;  
      q = MapPoint(a1, a2, b1, b2, p);  
      Console.WriteLine("am maps to: " + q.ToString());  // q should = bm

      Console.ReadLine();
   }
}

It uses the Point and Vector structures from System.Windows (in the WindowsBase assembly).

The important part is the MapPoint function. It maps an input point $p$ to an output point that is returned by the function. The mapping is defined by four points $a_1$, $a_2$, $b_1$ and $b_2$. The idea is that the "source" points $a_1$ and $a_2$ are mapped (roughly) to the destination points $b_1$ and $b_2$ respectively. This mapping will only be exact if the distances $a_1a_2$ and $b_1b_2$ are equal. In fact, what actually happens is that the mid-point of $a_1a_2$ is mapped to the mid-point of $b_1b_2$.

The test code in the Main function shows that things are working correctly. The mid-point $a_m$ gets mapped to $b_m$, as expected. Also, in this case, $a_1$ gets mapped to $b_1$ and $a_2$ gets mapped to $b_2$, since the distances distances $a_1a_2$ and $b_1b_2$ are equal.

Thank you! I almost got there with Loki, but I couldnt get my values plugged into what he provided. — Nicros, Jun 20 '13 at 00:34
No problem. BTW, it occured to me that by adding a simple scaling factor, we could ensure that the two source points always get mapped to the two destination points, regardless of the inter-point distances. Ask again if this matters to you and you can't figure out how to do it. — bubba, Jun 20 '13 at 00:43

Correction formula for two points

2 Answers2