Thread: Transformation between two non-aligned 2-dimensional spaces

I have a quadrilateral that has known corner coordinates in two non-aligned 2-dimensional spaces (xy and pq). I have a point within the quadrilateral known in one space. How do I find it's coordinates in the other space?

Note that the spaces may not have coincident origin, sheer or rotation, and may be flipped and linearly distorted (that is the grid lines on one of the spaces may widen with respect to the other, but in a linear way).

I have tried a number of forms of interpolation only to find differing answers in the proof, and suspect the solution lies in creating a transformation matrix from the known points, which is beyond my current matrix math.

Here's my test case (note that pq of the quadrilateral may not be rectilinear as in this simplified test case):

Quadrilateral: ABCD
* A xy: (5,11), pq: (1,1)
* B xy: (10,5), pq: (0,1)
* C xy: (4,2), pq: (0,0)
* D xy: (1,7), pq: (1,0)

Point: M
* M xy: (3,6), pq: (?,?)



Using simple interpolation I soon found that I got different results depending on which line intersections I used as the linear distortion came into effect.

The second interpolation solution I tried was creating two bisectors of the quadrilateral passing through M that bisect AB, AD at the same ratio (r and 1-r) and BC, DC (s and 1-s), but I've not found a solution where I can determine both r and s.

Any experience in this area would be appreciated.

= Martin =

I have done some research myself and discovered that Gaussian Elimination may provide a solution. I'll post my findings if it proves successful.

Using x' = c1.x + c2.y + c3.xy + c4 and y' = c5.x + c6.y + c7.xy + c8 I can deduce c1..c8 using Gaussian Elimination.

Using the original 4 points yields the correct answer, as does any other point if the transformation is just rotate, scale and translate. But as soon as I get stretching of the original shape I begin to get errors up to 6% - I suspect because the equations cannot support that transformation.

I've looked at projective transformations, but can't find out how to create the required 3x3 matrix from a known set of points. Well, at least in a language I can understand. This guy: http://www.mpi-inf.mpg.de/department...amgeo-0305.pdf explains it but implementing a solution from his notation is beyond me.

If I can't get any further with the above, then I'll move to a simple iterative solution that attempts to find 'r' and 's' in the original diagram by trial and error...

The iterative approach has provided and answer to the solution using 'r' and 's' (see the original diagram).

I now try binary chopped values of 'r' and 's' until the line EG and FH pass through M, using the line's distance from M to decide which direction to chop (an enhancement for less iterations would be to use the line's distance to precompute the next value of 'r' to try...)

Given r and s I can deduce the (p,q) of M from ABCD.

This is likely to be slow in real time, so any assistance on a non-iterative solution will enhance performance.