# ENIGMA Development Environment

 Pages: 1 Author Topic: Simple Transformations  (Read 1918 times) TheExDeus Posted on: June 28, 2012, 08:49:17 AM  Joined: Apr 2008
Posts: 1872 Hi. Not really connected to ENIGMA, but still thought I might ask here. In one of my projects I need to transform from a convex quadrilateral to a rectangle. I though of just using bilinear interpolation, but got stuck at some basic ideas - mainly that the points for the convex quadrilateral with the point P has the origin still at the top left and so x0,y0 isn't 0,0 as it is in rectangle case. Here is a picture: (note x0,y0, x1,y1... and so on are of course different for both the quadrilateral and the rectangle, I just named them the same)
As the transformation would be linear then the math isn't that hard, but I am tired now and if someone can figure it out in the next few hours while I am away, then that person gets a cookie (a virtual one). Logged Josh @ Dreamland Reply #1 Posted on: June 28, 2012, 11:44:19 AM Prince of all Goldfish Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2949  Kind of a neat problem. My first thought would be to represent the point in terms of four distances.
A*sqrt(sqr(x-x1) + sqr(y-y1)) = B*sqrt(sqr(x-x2) + sqr(y-y2)) = C*sqrt(sqr(x-x3) + sqr(y-y3)) = D*sqrt(sqr(x-x4) + sqr(y-y4)).

So to get the transformation, you'd use A=1 to solve for B, C, and D, then swap out the x1..x4,y1..y4 pairs and solve back for x,y. That part's a real pain in the ass. Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire TheExDeus Reply #2 Posted on: June 28, 2012, 01:02:42 PM  Joined: Apr 2008
Posts: 1872 Quote
My first thought would be to represent the point in terms of four distances.
Ok, so the distances from the four corners of the quadrilateral. But wouldn't that mean that I have to recalculate A,B,C,D all the time? I will try something along those lines.

What's stupid is that I can't find the answer on the net, because I don't know how you would describe it. Its some kind of projection or interpolation problem... Logged Josh @ Dreamland Reply #3 Posted on: June 29, 2012, 01:55:58 PM Prince of all Goldfish Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2949  I was thinking the math would simplify. In my formula,
A*sqrt(sqr(x-x1) + sqr(y-y1)) = B*sqrt(sqr(x-x2) + sqr(y-y2)) = C*sqrt(sqr(x-x3) + sqr(y-y3)) = D*sqrt(sqr(x-x4) + sqr(y-y4))

x1=x4, x2=x3, y1=y2, y3 = y4. So we can rewrite it as this:
sqrt(sqr(x-x1) + sqr(y-y1)) = B*sqrt(sqr(x-x2) + sqr(y-y1)) = C*sqrt(sqr(x-x2) + sqr(y-y3)) = D*sqrt(sqr(x-x1) + sqr(y-y3))

But that's not really making the math any easier; we still have a thousand variables. So, use x1 = y1 = 0, and shift x2 and y3 appropriately (we'll shift the result back later):
sqrt(sqr(x) + sqr(y)) = B*sqrt(sqr(x-W) + sqr(y)) = C*sqrt(sqr(x-W) + sqr(y-H)) = D*sqrt(sqr(x) + sqr(y-H))

Square all terms:
sqr(x) + sqr(y) = B*B*(sqr(x-W) + sqr(y)) = C*C*(sqr(x-W) + sqr(y-H)) = D*D*(sqr(x) + sqr(y-H))

Looking kinder. Now, we treat W as 1 and H as 1. We can transform that later, too.
sqr(x) + sqr(y) = B*B*(sqr(x-1) + sqr(y)) = C*C*(sqr(x-1) + sqr(y-1)) = D*D*(sqr(x) + sqr(y-1))

Multiply everything out:
x*x + y*y = B*B*((x*x - 2*x - 1) + y*y) = C*C*((x*x - 2*x + 1) + (y*y - 2*y + 1)) = D*D*(x*x + (y*y - 2*y + 1))

More:
x*x + y*y = B*B*x*x + B*B*y*y - 2*B*B*x - B*B = C*C*x*x + C*C*y*y - 2*C*C*x - 2*C*C*y + 2*C*C = D*D*x*x + D*D*y*y - 2*D*D*y + D*D

Now subtract x*x and y*y from everything:
0 = (B*B-1)*x*x + (B*B-1)*y*y - 2*B*B*x - B*B
0 = (C*C-1)*x*x + (C*C-1)*y*y - 2*C*C*x - 2*C*C*y + 2*C*C
0 = (D*D-1)*x*x + (D*D-1)*y*y - 2*D*D*y + D*D

I'll revisit those later to figure out how to solve them. Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire TheExDeus Reply #4 Posted on: June 29, 2012, 03:20:04 PM  Joined: Apr 2008
Posts: 1872 Here is how I did it: Basically I need to get the distance from the sides to the point (which is computationally quite expensive), but it works. Now I am thinking if there is any better or faster way. Now I basically do this 4 times. The 640x480 could be anything, I just needed it for that size.

You can download an example exe here. When run, press 4 to get the final working version. If you can't run the executable, then I guess I can give the gmk. Logged Josh @ Dreamland Reply #5 Posted on: June 29, 2012, 10:21:59 PM Prince of all Goldfish Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2949  If I'm not mistaken, that measure's a little imprecise. It wouldn't really matter unless you had something like this: Taking a distance from corners instead will fix that. You don't need to use the sqrt function, since all you are interested in is proportions. Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire TheExDeus Reply #6 Posted on: June 30, 2012, 06:12:35 AM  Joined: Apr 2008
Posts: 1872 Quote
If I'm not mistaken, that measure's a little imprecise. It wouldn't really matter unless you had something like this
No, it still works then as well. Of course its "jittery" because then its so stretched out, that a few pixels in the quadrilateral moves the point in the rectangle a lot more. But its still how it should be. Of course in my case it wouldn't be in a shape like that, as I would have parallelograms and such.

Quote
Taking a distance from corners
I tried that, but not sure what you mean. Basically the exact same thing I do here, but the distances are from corners?

Quote
You don't need to use the sqrt function, since all you are interested in is proportions.
True. I will try to remake the whole thing in a script and optimize it on the way.

edit: Still don't get it. What ratio should I take? I can't take one distance from the corner and the distance from the opposite corner and just get ratio from them. But taking corner distance would be a lot faster, so if it is possible then I would love to figure this out. As I would not need to calculate intersection point of two lines four times.
 « Last Edit: June 30, 2012, 06:27:48 AM by HaRRiKiRi » Logged
 Pages: 1