ENIGMA Forums

Outsourcing saves money => Issues Help Desk => Topic started by: TheExDeus on June 28, 2012, 08:49:17 AM

Title: Simple Transformations
Post by: TheExDeus on June 28, 2012, 08:49:17 AM
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:
(http://img19.imageshack.us/img19/8011/transform.png)
(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).
Title: Re: Simple Transformations
Post by: Josh @ Dreamland on June 28, 2012, 11:44:19 AM
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.
Title: Re: Simple Transformations
Post by: TheExDeus on June 28, 2012, 01:02:42 PM
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...
Title: Re: Simple Transformations
Post by: Josh @ Dreamland on June 29, 2012, 01:55:58 PM
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.
Title: Re: Simple Transformations
Post by: TheExDeus on June 29, 2012, 03:20:04 PM
Here is how I did it:
(http://img833.imageshack.us/img833/1641/transjo.png)
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 (http://paulbourke.net/geometry/lineline2d/) 4 times. The 640x480 could be anything, I just needed it for that size.

You can download an example exe here (https://dl.dropbox.com/u/21117924/transform.exe). 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 (https://dl.dropbox.com/u/21117924/transform_test.gmk).
Title: Re: Simple Transformations
Post by: Josh @ Dreamland on June 29, 2012, 10:21:59 PM
If I'm not mistaken, that measure's a little imprecise. It wouldn't really matter unless you had something like this:

(http://dl.dropbox.com/u/1052740/fuckup.svg)

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.

Title: Re: Simple Transformations
Post by: TheExDeus on June 30, 2012, 06:12:35 AM
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.