Google Answers Logo
View Question
Q: 2D transforms on a fixed triangle to make it's corners touch arbitrary points ( No Answer,   1 Comment )
Subject: 2D transforms on a fixed triangle to make it's corners touch arbitrary points
Category: Computers > Algorithms
Asked by: purpleprogrammer-ga
List Price: $120.00
Posted: 29 Aug 2006 11:11 PDT
Expires: 09 Sep 2006 04:56 PDT
Question ID: 760528
I have a right isosceles triangle with the "right" corner at the
origin [0,0].  The other two

corners are at [+1,0] and [0,+1].

This triangle has two to-be-determined transforms applied to it, with
no translation (no change

of position): t1xscale, t1yscale, t1rotation, t2xscale, t2yscale, t2rotation.

All scale and rotation is about the origin, so the "right-angle"
corner will always be at [0,0],

no matter the transform.

Given 2 coordinates, create algebraic/algorithmic expressions to
define the two transforms such

that each end of the hypotenuse lands on each coordinate.

Given [x1, y1] and [x2, y2], solve for: t1xscale, t1yscale,
t1rotation, t2xscale, t2yscale,


If the two input coordinates were to be swapped, the traingle's two
output corners should swap,

even though this would not change the resulting "shape".

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 triangle points ([+1,0] or
[0,+1]) to a transformed

point ([x1, y1] and [x2, y2]).  Ignoring the above algorithm, this is
probably the best place to

start solving the problem by reversing this algorithm.

// 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 resulting 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.

I would prefer to avoid extremes; an output triangle similar in size
to the input triangle

should have scales that are 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().


Here is where I am in the puzzle so far...  This 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 that is y1=y2 (by a number of degrees equal to
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... and of course, it still has one unknown function.

 ** In this implementation,
 ** I do know that this t2yscale is some function of the
 ** angle from [0,0] to the center of the target hypotenuse
 ** This unknown function is the main failure of this algorithm.
 ** I plotted what "looked right" by hand, and created a polynomal
 ** approximation, which worked, but I need this to be perfectly accurate.
 ** The /2 here is to get the half-way point on the hypotenuse -- it's
 ** for understandability but needs to be removed, since atan2 doesn't care.
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 = ((t2xscale^2 + t2yscale^2)^0.5);

t1xscale = hyplen/scalelen;

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

t1yscale = y1 * scalelen / t2yscale;

Clarification of Question by purpleprogrammer-ga on 04 Sep 2006 14:22 PDT
I've upped the price from $80 to $120, but I cannot go higher.  The
"answer" to this must use pseudocode in a similar format and detail as
the code I've provided here -- since it's being used by a computer
rather than a mathemetician.  Thanks.
There is no answer at this time.

Subject: Re: 2D transforms on a fixed triangle to make it's corners touch arbitrary points
From: philnj-ga on 30 Aug 2006 13:54 PDT
Here is what I have so far:
.  the first rotation t2rotate gets the two points such that y1 = y2 as you say
.  The first scale (t2yscale) is chosen such that  the angle from [x1,
y1] to [0,0] to [x2, y2] is pi/2.  This is the function you are having
trouble with.  t2xscale is 1.
.  The second rotation is pi/4 (clockwise)
.  The second scalings are 1/x2 and 1/y1, to normalize the points.

You are definitely on the right track.  Let me work on this overnight,
and I'll see what I come up with.

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