Re: [Algorithms] decompose onto non-orthogonal vectors

[Scott J. S. <sjs...@um...>]

Okay, let me try and explain this as simply as possible.  You want to find
scalars u,v such that u*a + v*b = p.  Since these are 3-dimensional
vectors, you have 3 equations and 2 unknowns:

u*a1 + v*b1 = p1
u*a2 + v*b2 = p2
u*a3 + v*b3 = p3

where p1,p2,p3 are the coordinates of the point p, likewise for a1,a2,a3
and a, and b1,b2,b3 and b.

How do you solve a system of 3 linear equations with 2 unknowns?  If you
don't know Gaussian elimination, this can be done with some simple
algebraic rules and substituion.

If you know your constant values (a, b, p) now, it's very simple to just
do the necessary substitutions by hand.

On the other hand, if the values are determined at run-time, coding the
algebra isn't as easy, unless you use gaussian elimination, since gaussian
elimination is essentially an algorithm for solving linear equations.  The
problem with "coding" algebra is that there are a lot of special cases.

So I'll present you with one sample, "stupid" solution that will work,
assuming that a1 is non-zero.  Simply vary the approach if a1 is zero, and
choose the starting equation using any element of a that is non-zero (at
least one of them must be non zero, or else you reduce to a much simpler
equation, since the point is along b).

This is a dumb approach, and simply meant for a sample illustration of a
possible, yet ugly way, to solve a system like this.  It also assumes a
solution exists:


Start with equation 1.  Solve for u in terms of v.  This gives:

u = (p1 - v*b1)/a1

plug this value of u into equation 2.

This gives you:
a2* (p1 -v*b1)/a1  + v*b2 = p2

now factor out v:

v[ a2* (p1-v*b1)/a1 + b2 ] = p2

divide p2 by that big thing in brackets, so you have v by itself.

Now you have v expressed entirely in terms of known values, so you know
the value of v.  with this, it is trivial to find the value of u, just
plug back into the first equation.  By plugging the vales of u and v you
have determined into the third equation, you can see if in fact there is a
real solution. If you end up getting something like 0=1 for the third
equation upon substiting your discovered values of u and v, no solution
exists.

Note to Ron: obviously, this isn't rigorous at all, but the goal 
was merely give an impression of how the solution can be obtained.

You'd really want to use gaussian elimination for anything like this,
since all of the special cases (is a1 0? start with a different equation, 
is a1,a2,a3 all 0?  just reduce to one equation, etc.) are neatly
handled by it. In fact, I like to think of gaussian elimination as a
mathematical "encapsulation" for solving systems of linear equations, it
automatically takes care of the details for you.

Try doing a search on the net for guassian elimination, you will
definitely come across some hits.  I believe I learned it my sophomore
year of high school, algebra II class, so it's certainly not anything
remotely unusual.


Hope this helps.



--
Scott Shumaker
sjs...@um...

On Fri, 14 Jul 2000, Discoe, Ben wrote:

> 
> I thought it would be a simple problem, but all usual sources failed to
> answer, so perhaps it will be obvious to someone on this list.
> 
> Given a point p and two unit vectors a and b like this:
> 
>       b
>      /
>    v/----p
>    /    /
>   /    /
>  /    /
> ---------a
>     u
> 
> how to you get scalars (u,v) such that u*a + v*b = p?
> Ie. decompose p onto a and b.
> 
> I promise i consulted an academic, a linear algebra textbook and the WWW
> (all failed) before resorting the list :)
> 
> Thanks,
> Ben
> http://vterrain.org/
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>