View Question
Q: 2D transforms on a fixed triangle to make it's corners touch arbitrary points ( No Answer,   1 Comment )
 Question
 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, t2rotation. 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 --------- Requirement: 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. Bonuses: 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.```
 ```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.```