5
$\begingroup$

I have a math problem for some code I am writing. I don't have much experience with 2D transformations, but I am sure there must be a straight-froward formula for my problem.

I have illustrated it here:

transformation

My goal is to work out the co-ordinates of (Xp2, Yp2).

Shape A is a quadrilateral that exists that can exist anywhere in 2D space. Its four co-ordinates are known. It contains a point (Xp1, Yp1), which are also known.

Shape B is a rectangle with one corner at (0,0). The height and width are variable, but known.

Shape A needs to be transposed to Shape B so that the new position of the point inside can be calculated.

How do I work out the new co-ordinates of (Xp2, Yp2)?

Cheers,

  • 0
    The transformation cannot be linear, because a linear one would map a rectangle to a parallelogram. Therefore there may not be a unique natural transformation that would automatically suggest itself. But don't the texture mapping routines do exactly this type of transformations all the time? Even taking into account the projection from 3D world to the 2D screen (and thus finding a *natural* transformation). Have you looked at the descriptions of those for help/suggestions?2011-09-10
  • 1
    @Jyrki: there is a unique perspective transform that maps 4 points to 4 points, as long as no 3 points are collinear.2011-09-10

1 Answers 1

2

See my answer to "Tranforming 2D outline into 3D plane". The transforms and 4 point to 4 point mapping described there should be just what you need.

  • 0
    I hope that helps. I will be AFK until later tonight.2011-09-10
  • 0
    +1, but curse you. Now I have to spend some time turning a rectangle in 3D-space (ok, in my mind) and trying to convince myself that I can find a projection mapping it to any 4-gon :-)2011-09-11
  • 0
    Don't you need to assume that shape A is convex at least?2011-09-11
  • 1
    @Jyrki: If mapping from a rectangle to a non-convex quadrilateral, one of the points of the rectangle will be behind the observer so that the image on the plane of projection is virtual (a result of dividing by a negative $z$ coordinate).2011-09-11
  • 0
    @Jyrki: the points get mapped as advertised, but the edges may be strange (passing across the horizon, etc.)2011-09-11
  • 0
    Ah! Thanks! My first efforts at 3D-programming did produce similar effects :-). That way I learned the necessity of doing 3D-clipping w.r.t. to the view frustrum (as opposed to trying to simply clip the projection). Unfortunately I failed to make the connection here :-( It's been a while.2011-09-11
  • 0
    @robjohn: Thanks for the reply. The perspective transform appears to be what I am looking for (no three points will be collinear). I just need a little help with punching in the numbers. For each of the 5 points from shape A do I need to embed them in to 3D and create matrix M for them and project them back?2011-09-11
  • 0
    @Martin: You compute the matrix $M_{[x,y]}$ from 4 of the points in the source (the rectangle) and $M_{[u,v]}$ from 4 of the points in the destination (the quadrilateral). Both of these are created as in my answer: compute the $3$ $d_n$ first, then the rows of $M$ are $[d_n x_n, d_n y_n, d_n]$ using the first three points (you used the fourth point to compute $d_n$, so it's in there, too). Then to map the fifth point, imbed it, multiply it (as a row vector) by $M_{[x,y]}^{-1}M_{[u,v]}$, and project it back.2011-09-11
  • 0
    @robjohn: IT WORKED! Thank you so much. I had to dig around in the depths of my brain to remember how to do matrix arithmetic, but it worked!2011-09-15
  • 0
    @Martin: that algorithm has been tested thoroughly in [QuickDraw GX](http://en.wikipedia.org/wiki/QuickDraw_GX). While we usually used the Camera Library to generate perspective matrices, we also used this algorithm (Poly2PolyMap) to generate perspective matrices that didn't originate from 3-D data.2011-09-15