Google Answers Logo
View Question
Q: Backwards 2D transform algorithm using geometry, trigonometry, pseudocode ( No Answer,   0 Comments )
Subject: Backwards 2D transform algorithm using geometry, trigonometry, pseudocode
Category: Computers > Algorithms
Asked by: purpleprogrammer-ga
List Price: $100.00
Posted: 09 Sep 2006 05:25 PDT
Expires: 16 Sep 2006 19:04 PDT
Question ID: 763631
I have two points, [+1,0] and [0,+1].  These points will (both
together) have two to-be-determined transforms applied to them, with
no change of position: t1xscale, t1yscale, t1rotation, t2xscale,
t2yscale, t2rotation.  Both transforms are applied to both

All scale and rotation is about the origin of [0,0].

Create an algorithm, when given post-transform coordinates [x1, y1]
and [x2, y2], determines the two transforms: t1xscale, t1yscale,
t1rotation, t2xscale, t2yscale, t2rotation.

If the two input coordinates were to be swapped, the two output
coordinates should swap.

I believe this can be solved with t1rotation fixed at any non-0 degree
-- 45 degrees being most convenient, and one of the scales (such as
t2xscale) fixed at 1.


Here it all is backwards -- using the given transforms (t1xscale,
t1yscale, t1rotation, t2xscale, t2yscale, t2rotation) to convert
points ([+1,0] or [0,+1]) to a transformed point ([x1, y1] and [x2,
y2]).  This is probably the best place to start solving the problem by
reversing this algorithm.  This is verbose for uniformity and
understandibility; transform 1 could be significantly reduced.

// Transform 1, point [0, +1]
x1a = 0 * t1xscale // Scale
y1a = +1 * t1yscale
rtemp1a = atan2(y1a, x1a) + t1rotation // Get ang/distance, add rotation
dtemp1a = sqrt(x1a^2 + y1a^2)
x1b = cos(rtemp1a) * dtemp1a // Turn ang/distance back to coordinates.
y1b = sin(rtemp1a) * dtemp1a

// Transform 2
x1c = x1b * t2xscale
y1c = y1b * t2yscale
rtemp1b = atan2(y1c, x1c) + t2rotation
dtemp1b = sqrt(x1c^2 + y1c^2)
x1 = cos(rtemp1b) * dtemp1b
y1 = sin(rtemp1b) * dtemp1b

// Transform 1, point [+1, 0]
x2a = +1 * t1xscale
y2a = 0 * t1yscale
rtemp2a = atan2(y2a, x2a) + t1rotation
dtemp2a = sqrt(x2a^2 + y2a^2)
x2b = cos(rtemp2a) * dtemp2a
y2b = sin(rtemp2a) * dtemp2a

// Transform 2
x2c = x2b * t2xscale
y2c = y2b * t2yscale
rtemp2b = atan2(y2c, x2c) + t2rotation
dtemp2b = sqrt(x2c^2 + y2c^2)
x2 = cos(rtemp2b) * dtemp2b
y2 = sin(rtemp2b) * dtemp2b


Your function will be given x1, y1, x2, y2, and return answers for
t1xscale, t1yscale, t1rotation, t2xscale, t2yscale, t2rotation.  The
answer is proven 'correct' if and only if the above algorithm, given
your function's answers, returns your function's inputs.

The algorithm should avoid extremes; if the input points are "close
to" the output points, the scale values should be near 100% -- (rather
than, for example, 10% or 1000%!)

For speed, I would prefer an optimized algorithm; minimal calls to
exponent, sqrt(), atan2(), cos() and sin().  I do not need to
understand the reasoning behind the math, but the format of the answer
should be similar to the pseudocode I've provided -- with if/loop
statements if necessary.

This has no bearing on request, but if you're curious, this is to take
a textured 2D right triangle (points [0,0], [+1, 0], [0, +1]) and
transform it into an arbitrary triangle.


Here is where I am in the puzzle so far...  The following half-done
algorithm requres that y1 and y2 are equal (paralell with the y axis),
but I can "fix that" by rotating the input coordinates about [0,0]
until y1=y2 (that would be atan2(y2-y1, x2-x1)), and then subtracting
that rotation from the resulting t2rotation.

A great deal of this was magical brain power and trial-and-error, so I
don't think I can explain it well.  The function labeled "f???" is the
one component that I have not yet determined; I have "guessed" at a
polynomial for it, and it works well, but it is not accurate enough.

 ** In this implementation, I do know that t2yscale is some
 **  function of the angle from [0,0] to the half-way point
 **  between the two input points.
 ** The /2 here is to get the half-way point;
 **  -- it's for understandability only, since it doesn't
 **  affect the output of atan2.
t2yscale = f???(atan2((y1+y2)/2, (x1+x2)/2))

 ** These two are fixed at 100% and 45 degrees
t2xscale = 1
t1rotation = PI/4

 ** hypotenuse length
hyplen = ((x1-x2)^2 + (y1-y2)^2)^0.5

 ** ("scale length"?)
scalelen = sqrt(t2xscale^2 + t2yscale^2);

t1xscale = hyplen/scalelen;

 ** ("aspect angle"?)
t2rotation = atan2(t2yscale, t2xscale);

t1yscale = y1 * scalelen / t2yscale;

Clarification of Question by purpleprogrammer-ga on 09 Sep 2006 08:48 PDT
I've just discovered that the half-done code I provided -- my "work in
progress" for this algorithm isn't perfect.  It is probably off by 45
deges, and maybe flipped on the x or y axis.  It's a good rough idea,
but will require some tweaking.

Regardless, I've rearranged and reduced the formula a bit, and come up with this:

(Basic formulas for the algorithm to come)
t = sqrt(2)/2
rotatex(x,y,r) = cos(atan(y/x) + r) * sqrt(y^2+x^2)
rotatey(x,y,r) = sin(atan(y/x) + r) * sqrt(y^2+x^2)

Here is the forward transform again -- Identitcal to the original as
far as results, but optimized.
x1c = -t * t1yscale
y1c = t * t1yscale * t2yscale
x1 = rotatex(x1c, y1c, t2rotation)
y1 = rotatey(x1c, y1c, t2rotation)
x2c = t * t1xscale
y2c = t * t1xscale * t2yscale
x2 = rotatex(x2c, y2c, t2rotation)
y2 = rotatey(x2c, y2c, t2rotation)

Rather than reversing the formula by resorting to asin, acos, tan,
etc, you can reverse a rotation by using a negative rotation; so here
is the un-transform, half solved:

t * t1xscale * t2yscale = rotatey(x2, y2, -t2rotation)
t * t1xscale = rotatex(x2, y2, -t2rotation)
t * t1yscale * t2yscale = rotatey(x1, y1, -t2rotation)
-t * t1yscale = rotatex(x1, y1, -t2rotation)

I don't know where to take it from here -- to solve for the remaining
unsolved variables: t1xscale, t1yscale, t2yscale, t2rotation. 
(t2xscale = 1, t2rotation = 45 degrees)

Good luck!

Clarification of Question by purpleprogrammer-ga on 16 Sep 2006 19:03 PDT
Ha! Solved it!


t2xscale = 1
t1rotation = PI/4

t = sqrt(2)/2
a1 = atan2(y1,x1)
a2 = atan2(y2,x2)
t2rotation = (a1 + a2) / 2
d1 = sqrt(y1*y1 + x1*x1)
rx1 = cos(a1 - t2rotation) * d1
t1yscale = -rx1/t
t2yscale = -(sin(a1 - t2rotation) * d1)/rx1
t1xscale = cos(a2 - t2rotation) * sqrt(y2*y2 + x2*x2)/t
There is no answer at this time.

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy