Preserved Topic: Need help with a math problem. (Page 1 of 1)

Hey folks, I wasn't really sure where to post this one as it's not really confined to a problem with a particular programming language so...

First up, to make things *easier* I've sketched up this diagram to help explain what I'm trying to solve:



The above image shows a standard coordinate system (0,0 in top left). The size of the screen/area in question defined by four purple points (a1,b1,c1,d1), which are know locations. There's a quadrilateral inside this area defined by another four purple points (a2,b2,c2,d2), these are also known locations. The red dot (p) is what I'm trying to solve for.

The location of point p is relative to the main coordinate space, but I want to figure out it's location relative to the coordinate space inside the quadrilateral - assuming the quad has it's own coordinate space starting at it's top left most point. Actually, if I can get the vector (direction and length) of either line dx or dy, I should be able to take if form there. But seeing as there are no parralels I've got no clue as to how I'd approach this.

It's safe to assume I can find the angle or length for pretty much any line except for anything that would be relative to the quad's coordinate space, obviously, otherwise I wouldn't need to ask this question .

In case it makes no sense why I'd want to be doing this, what I'm essentially trying to do is use the quad values to remap any points that fall inside the quad back to the dimensions of its bounding box. I only have the normal coordinates for those points, so this is kind of an inverse distortion. Knowing the relative position of the point inside the quad means I can remap the point to any other quad, including its own bounding box. In a visual sense, I?m attempting to end up with something like this:

Edit: wrong pic



Any takers will be showered with, um, something pretty and nice smelling... I'm seriously stumped with this one...

(Edited by Cameron on 10-27-2004 08:24)

Cameron: pictures still not showing up.

They are for me

I've spent the last ten minutes staring at that. I understand (Im pretty sure) what your after. My brain just can't handle it.
I think it first needs to be broken into steps: resize, vertical distort <-effect each other-> horizontal distort (and rotate maybe). In each step focusing only on the x or y at a time. Oh man, just writing that made my head hurt. I have a friend coming over in an hour or two to help with some network cable, he's a Maths genius I'll force him to have a look at it.

The maths your using to obtain the second corner points, would it not be like scaling them down proportionally?

Say p is at (px, py) in the main coordinate space (these values are known). Say that (px', py') is its position relative to the inner square (px', py' are between 0 (upper left) and 1 (lower right)). These are the values we're solving for.

We have two unknowns, so what we're going to do is find two equations that we can express them with.

To get these equations, look at how (px,py) is defined according to your picture. To relate (px,py) to (px',py') (assuming that we knew what (px',py') is), we must first find the upper and lower intersection of the vertical red line with the two green lines that it touches (these points will be px' of the way between a2 and b2 or d2 and c2) - we'll call these points "A" on top and "B" on bottom - and then find the intersection of the two red lines (this point is py' of the way between A and B).

So this brings us to two equations, one involving the value of px and one involving the value of py. For now I'm going to use the coordinates of A and B for simplicity; later we'll plug in their values (which are dependant on px'):

px = Ax + (Bx-Ax)*py'
py = Ay + (By-Ay)*py'

This is because p is py' of the way between A and B.


Notice that
A = a2 + (b2-a2) * px'
(because A is px' of the way between a and b)
so
Ax = a2x + (b2x-a2x) * px'
Ay = a2y + (b2y-a2y) * px'

and

B = d2 + (c2-d2) * px'
(because B is px' of the way between d and c)
so
Bx = d2x + (c2x-d2x) * px'
By = d2y + (c2y-d2y) * px'

So lets plug these values in to our original equations:

px = (a2x + (b2x-a2x) * px') + ((d2x + (c2x-d2x) * px') - (a2x + (b2x-a2x) * px'))*py'
py = (a2y + (b2y-a2y) * px') + ((d2y + (c2y-d2y) * px') - (a2y + (b2y-a2y) * px'))*py'

So now we have two unknowns (px', py') in two equations. They can be solved for, but right now I have to take a shower and get to class so I'll leave that as an exercise for the reader. =) (Or, maybe I'll come back and solve them later.)

Once px' and py' are obtained, to get the corresponding point relative to a1,b1,c1,d1, just do:

x = a1x + (b1x - a1x)*px'
y = a1y + (d1y - a1y)*py'


 

Holy crap... And I'd just come up with some whacked way of measuring angles from the quad corners to the unknown point, then their relative percentage of the total quad corner, which would be the same percentage of the right angles when transformed back into a rectangle, then re-plotting those lines and finding the intersection being the transformed point, but that's a bucket load of arc tangent, sin and cosign functions compared to yours which is just multiplications. I really need to stop thinking like a drafter.

Thanks slime, you're a life saver (yet again).

Alrighty then...

*wanders off to grab more coffee*

It's going to take a few cups to dissect you're post... (as per usual).

Yeah..., I was gonna solve it but I heard lightning and rain so I turned the PC off.

So then, I used my slide rule and pen, but when I got back online the solution was already posted...

Ooops, more rain and lightning... gotta go!

______________
Is This Thing On?

Webbing; the stuff that sticks to your face.

Actually, even with those equations I still can't seem to get px' or py', no matter how I try and arrange things. I've started using my slow arse angels method for now, but if you've got the time I'd really like to know how you'd solve this one. I've figured out how to transform a point into the space of the inner square. Actually, I started with this a few days ago with a method very similar to yours (not quite as elegant thought), and quickly realized I was doing things the wrong way around.

It was when I tried reversing the problem that I ran into a brick wall of not having any way to get a handle on the offsets. I thought perhaps there was some way in which you constructed those equations that would identify some kind of linear algebra solve for them, but if there is I'm just too stupid to see it.

quote:

---

Actually, even with those equations I still can't seem to get px' or py', no matter how I try and arrange things.

---

It's not easy. I'll do it through substitution. Starting with the two equations from above:

px = (a2x + (b2x-a2x) * px') + ((d2x + (c2x-d2x) * px') - (a2x + (b2x-a2x) * px'))*py'
py = (a2y + (b2y-a2y) * px') + ((d2y + (c2y-d2y) * px') - (a2y + (b2y-a2y) * px'))*py'

(I'm going to consolidate these into a single equation by dropping the x and y subscripts from points. Keep in mind that p, a2, b2, c2, d2 are all vectors with x and y parts, so we really have two equations here which just look very much alike.)

I multiply out some of it:

p = a2 + (b2-a2)*px' + (d2 -a2 + (c2-d2 + b2-a2)*px')*py'

0 = a2 - p + (b2-a2)*px' + (d2-a2)*py' + (c2-d2+b2-a2)*px'*py'

Let's declare some variables for convenience (note that these variables are all vectors; that is, A is really (Ax,Ay)):
A = a2-p
B = (b2-a2)
C = (d2-a2)
D = (c2-d2+b2-a2)

and we have

0 = A + B*px' + C*py' + D*px'*py'

solving for px':

px'*(B + D*py') = -A - C*py'
px' = (-A - C*py') / (B + D*py')

using the x-coordinate version (subscripting all the points with x's) and substituting into the y-coordinate version, we get

0 = Ay + By*(-Ax - Cx*py') / (Bx + Dx*py') + Cy*py' + Dy*(-Ax - Cx*py') / (Bx + Dx*py')*py'

Now we solve for py':

(first multiply both sides by (Bx + Dx*py'))

0 = Ay*Bx + Ay*Dx*py' - By*Ax - By*Cx*Py' + Cy*py' - Dy*Ax*py' - Dy*Cx*py'^2
0 = (Ay*Bx - By*Ax) + py'*(Ay*Dx - By*Cx + Cy - Dy*Ax) + Py'^2*(-Dy*Cx)

This is a quadratic equation, so let's declare some more variables for convenience:

P = (-Dy*Cx)
Q = (Ay*Dx - By*Cx + Cy - Dy*Ax)
R = (Ay*Bx - By*Ax)

and we have

0 = py'^2*P * py'*Q + R

so by the quadratic formula,

py' = (-Q +/- sqrt(Q*Q - 4*P*R)) / (2*P)

This requires Q*Q - 4*P*R to be greater than or equal to zero. It's possible that this will always be equal to zero, meaning we'll always have exactly one solution. I think it would be unlikely that it would be less than zero: that would correspond to a value of p which doesn't have a px' and py' that make sense.

Now, normally when there's a quadratic equation for a geometrical problem, it means there are two solutions: one which is the one you're probably expecting, and another which you maybe didn't expect, yet still satisfies the original equations. One of these results may be useless for your purposes, and you'll have to check both to see which one you want. It may always be the same one (the + or the -).

I'm worried though, because I didn't expect this problem to have multiple solutions, and I don't see how there could be two pairs of (px',py') values that satisfy the original equations. It's possible I did some of the math wrong. This needs to be investigated (by plugging in some values and seeing what kind of results we get) to understand better what's going on.

In any case, once you have a value for py', you can get the value for px' by plugging py' into the equation from above:

px' = (-Ax - Cx*py') / (Bx + Dx*py')

So, calculate the values of Ax,Ay,Bx,By,Cx,Cy,Dx,Dy, then the values of P,Q,R, then the two values of py' and the corresponding values of px', and then proceed as in my earlier post.


 

Um... *pop* goes my brain...

It'll take me a few days to digest all of this, and as I need to exhibit part of the work this problem involves tomorrow I'll stick with the trig solution I currently have despite it being a little inaccurate and requiring 4 atan2() calls per point. But I'll defiantly re-visit this on the weekend as I doubt I'll be loosing my access to the two Dual 3ghz P4 machines I have access to at the moment. That and It's high time I start forming a decent understanding of algebra and stop pilfering other peoples algorithms every time I hit a brick wall.

I'll post back here once I've started plugging numbers into these equations.

Thanks again slime, I really appreciate the help and the time you've put into this.

Reading this makes me feel like I'm playing chess with a deck of Uno cards.

Yay for Trigonometry.

Cameron: it's not really too complicated, but don't take it all in at once. Go through it one step at a time. Understand that step, then move on, little by little. It'll come to you in no time. And if you *really* don't get it... just do the calculations for A, B, C, D, P, Q, R, py', and then px', in that order, and pop -- you'll have the right answer (assuming that the quadratic only gives one answer of py'...)

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

quote:

---

It'll take me a few days to digest all of this

---

That's fine. I really made little to no effort to make my posts easy to understand; it's heavy math that you can understand fully - you just have to go through it step by step, and not move on until you understand the step you're reading. If you have any questions, please ask.

By the way, I figured out today why I got a quadratic equation. Since you're dealing with non-parallel borders to the region in question, it's actually possible for there to be multiple values of px' and py' that solve the equations (it's a little difficult to explain how this happens geometrically without pictures). Typically, these will be way outside the desired region of 0 to 1. (For instance, you may get the solution px' = 0.5, py' = 0.4, coupled with the solution px' = 10, py' = -20.) The thing to do is to throw away the value for py' which is less than zero or greater than one.

So, again, if there's anything I said that you can't understand even after thinking about it for a while, just ask me.

The procedure I presented may not be the only way (and may not be the simplest way) to solve this problem; it's just the way that came to my mind most easily.


 

Slime, I always knew you were one of the geniuses around but .. FUCK ... jaw doesn't drop , jaw digs its on way to china !

"Reading this makes me feel like I'm playing chess with a deck of Uno cards." - yup.

Whoa !! Holy mathmatica Slimeman.

:::tao::: ::cell::

/starts reading thread

/brain melts

/curls up in cornerwhimpering with blanket and puppy dog

_____________________

le coeur du feu
Qui sème le vent récolte la tempête!