ENIGMA Forums
Outsourcing saves money => Issues Help Desk => Topic started 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).
-
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.
-
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...
-
I was thinking the math would simplify. In my formula,
[snip]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))[/snip]
x1=x4, x2=x3, y1=y2, y3 = y4. So we can rewrite it as this:
[snip]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))[/snip]
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):
[snip]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))[/snip]
Square all terms:
[snip]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))[/snip]
Looking kinder. Now, we treat W as 1 and H as 1. We can transform that later, too.
[snip]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))[/snip]
Multiply everything out:
[snip]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))[/snip]
More:
[snip]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[/snip]
Now subtract x*x and y*y from everything:
[snip]0 = (B*B-1)*x*x + (B*B-1)*y*y - 2*B*B*x - B*B[/snip]
[snip]0 = (C*C-1)*x*x + (C*C-1)*y*y - 2*C*C*x - 2*C*C*y + 2*C*C[/snip]
[snip]0 = (D*D-1)*x*x + (D*D-1)*y*y - 2*D*D*y + D*D[/snip]
I'll revisit those later to figure out how to solve them.
-
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).
-
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.
-
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.
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?
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.