Dot product 3-dimensions
steve_...@hotmail.com
coordinates. I have the distances from all 5 known points to 1 unknown
point.
How can I determine the (x,y,z) coordinates of the unknown point. I
believe I need to use the dot product, but can't seem to form the
steps to do so. Thanks for any help.
Steve
LC Killingbeck
@g47g2000cwa.googlegroups.com:
Why do you think you need to use the dot product? This is just an
"intersection of spheres" problem. Take each known point, and enclose
it in a sphere with the known radius (distance) to the unknown point.
Now start doing sphere intersection. Two spheres intersect in a
circle. A third sphere intersects this circle in two points. A
4th sphere will isolate to a single one of these points. Your 5th
point is superfluous - usually! There are special degenerate cases
of the approach (left as an exercise in spacial visualization), but
see how far you get. Warning: It's been at least 35 years since I
did this algebra, but recall that it gets very messy, very fast!
I expect that somewhere on the internet, there is a site with all of
the gory derivation, or at least the results. In practice, I suspect
that numerical techniques are going to be preferred to an analytic
solution.
Have "fun" with the algebra! Try it first in 2 dimensions (a plane)
with three points, and circles instead of spheres. 2 circles
intersect in two points. The 3rd circle distinguishes which point.
Again, look for the degenerate cases where 3 points are inadequate.
Lynn Killingbeck
David Moran
<steve_...@hotmail.com> wrote in message
news:1137105861....@g47g2000cwa.googlegroups.com...
I don't know for sure if this will work, but here's my idea.
Let's call the unknown point (xu,yu,zu) and three of the known points
(x1,y1,z1), (x2,y2,z2), and (x3,y3,z3). We also know in three dimensions,
the distance formula is D=sqrt((x1 - x2) ^ 2 + (y1 - y2) ^2 + (z1 - z2) ^ 2)
for the first two points. If you could set three of these equations up and
then square both sides on each equation to get rid of the sqrt, you'd get a
system of three equations in three variables. Surely there's an easier way
because that'd be pretty tough to solve analytically.
Dave
Ray Koopman
Minimize
((x - x1)^2 + (y - y1)^2 + (z - z1)^1 - d1^2)^2 +
((x - x2)^2 + (y - y2)^2 + (z - z2)^1 - d2^2)^2 +
((x - x3)^2 + (y - y3)^2 + (z - z3)^1 - d3^2)^2 +
((x - x4)^2 + (y - y4)^2 + (z - z4)^1 - d4^2)^2 +
((x - x5)^2 + (y - y5)^2 + (z - z5)^1 - d5^2)^2
numerically w.r.t. x,y,z.
steve_...@hotmail.com
Thanks for your idea. Is the (z-z)^1 suppose to be (z-z)^2?
Are you suggesting the same solution as the previous comment? (i.e.
solve 3 equations and 3 unknowns?)
Ray Koopman
> Thanks for your idea. Is the (z-z)^1 suppose to be (z-z)^2?
Yes, that was a typo.
> Are you suggesting the same solution as the previous comment? (i.e.
> solve 3 equations and 3 unknowns?)
If there are measurement (or other) errors in the locations of the
known points or in their distances from the unknown point then it
is possible that no solution exists. Recasting the problem as a
minimization guarantees a solution. Three points should suffice,
but in the presence of error it might be safer to use all the points.
steve_...@hotmail.com
so there will be meaurement errors in each distance. This is a
surveying instrument where the coordinates of the known points are
established and measurments taken to the unknown. A min of 3 ranges
must be observed and I believe the 4th and 5th will add redundancy, and
can do a least-squares solution. But for now, I'm looking at solving
the unknown using a minimum number of control points.
Dave Rusin
<steve_...@hotmail.com> wrote:
>In 3-dimensions, I have (for example) 5 points with known (z,y,z)
>coordinates. I have the distances from all 5 known points to 1 unknown
>point.
>
>How can I determine the (x,y,z) coordinates of the unknown point.
Are the distances exact? If so, you have redundant information.
Write down the equations specifying that P=(x,y,z) is of distance
d_i from Q_i = (x_i, y_i, z_i). Subtract equations in pairs and
you obtain equations which are linear in x,y,z . Solve using
your favorite method for systems of linear equations.
You could also transfer the distance information to information about
the dot products of the vectors between points; this then amounts to
a Cholesky factorization of a symmetric matrix.
But what if the distances are not exact? As soon as you specify a
fourth distance, you will probably find the equations to be inconsistent,
and the fifth equation will probably give another contradiction.
At that point you have to come up with a rubric for deciding that one
answer is "better" than another, given that all of them will be
(slightly) wrong. Some sort of weighted average of (squares of) errors
is a typical choice, and you can pick the "best" x,y,z by this
criterion by applying a minimizing technique such as the ones
given in a multivariate calculus course.
(There's even a hybrid approach linking the last two paragraphs:
use something like the Cholesky factorization to get a perfect
isometric embedding into R^4, then project down to the nearest
copy of R^3 passing by the points.)
This is a very extensively studied problem. Google "triangulation".
dave
Ray Koopman
The distances of the unknown point from three given points are not
sufficient to specify which side of the plane determined by those
three points the unknown point is on. Four non-coplanar points are
necessary. Sorry, my mistake.
steve_...@hotmail.com
minimum of 4.
steve_...@hotmail.com
Can you elaborate some on what you mean by "minimize"
Ray Koopman
> Ray Koopman wrote:
> > steve_...@hotmail.com wrote:
> > > In 3-dimensions, I have (for example) 5 points with known (z,y,z)
> > > coordinates. I have the distances from all 5 known points to 1 unknown
> > > point.
> > >
> > > How can I determine the (x,y,z) coordinates of the unknown point. I
> > > believe I need to use the dot product, but can't seem to form the
> > > steps to do so. Thanks for any help.
> > >
> > > Steve
> >
> > Minimize
> >
> > ((x - x2)^2 + (y - y2)^2 + (z - z2)^2 - d2^2)^2 +
> > ((x - x3)^2 + (y - y3)^2 + (z - z3)^2 - d3^2)^2 +
> > ((x - x4)^2 + (y - y4)^2 + (z - z4)^2 - d4^2)^2 +
> > ((x - x5)^2 + (y - y5)^2 + (z - z5)^2 - d5^2)^2
> >
> > numerically w.r.t. x,y,z.
>
> Can you elaborate some on what you mean by "minimize"
Call the expression that I gave f(x,y,z), treating it as a function
of x,y,z given the measured values of the xi,yi,zi,di. f is the sum
of five terms. Each term is the square of the difference between the
squares of two distances: the theoretical distance and the measured
distance of the unknown point from point i. Other functions will work;
this one is the simplest.
Find the values of x,y,z that make f as small as possible. If the
measured values are accurate then it will be possible to make f = 0,
but this is unlikely. More likely the minimum f will be some small
positive number. In any case, the x,y,z that minimize f are your
best estimate of the coordinates of the unknown point.
steve_...@hotmail.com
Ray,
Sounds like a good plan, but I have no idea on how to start to
"minimize"
Ray Koopman
> Sounds like a good plan, but I have no idea on how to start to
> "minimize"
If you don't know what minimization is all about then it's probably
best for you to use a packaged routine rather than trying to write
one yourself. Poke around http://plato.la.asu.edu/guide.html ,
which will point you to books and tutorials as well as software.