I am looking for a method to determine my exact position and
orientation in 3D space based on angle, elevation and range to a set
of known points. Some quick searching shows that this seems to be
called "spatial resection." What I am looking for is a series of
step-by-step instructions to perform this that can be passed to a
programmer to implement. Excel spreadsheets are a great way to
demonstrate this, but are not required as long as there is an adequate
walkthrough that I can reproduce. If it is at all possible to keep the
math to basic trig functions and simple matrix transforms, please do
so ? pretty much anything in Excel is fair game.

A sample of what I need to know:

I have 6 known points in 3d space. I can determine an angle,
elevation, and range to every one of those points. I am not sure of my
position, and I am not sure of my orientation (i.e. I am unsure which
way is north, 0 or up). I would also like to know a confidence on that
position ? some additional simple searching revealed that there is a
"least squares method" of determining confidence, but any reliable
method is acceptable.

Some sample data:

I have 6 points with known 3d (x,y,z) locations (A-F)
A: (-5.8311,-2.9535,0.9356)
B: (-4.5664,-4.1200,0.7690)
C: (-4.2774,-3.9950,-0.8312)
D: (-0.9403,-3.9162,-0.8276)
E: (0.5229,-4.0035,0.8581)
F: (0.9988,-3.8776,-0.8251)

I have an unknown point from which I determine my angle, elevation and
range to the above points. Angle begins with 0 at the local "north"
and increases clockwise. At the unknown point, the local "north" may
not be in the same orientation as points A-F. I need to determine what
the orientation is, and by how many degrees it needs to be changed so
it is back in the same orientation as the surveyed points. Elevation
begins with 0 being straight "up" and 180 being "down."  Range units
are the same units used in the coordinate system (meters, if it
matters)

From my unknown position, my (angle, elevation, range) to points A-F are:
A: (79.4658,81.3344,6.0447)
B: (96.1967,82.5461,5.7346)
C: (97.4889,99.0231,5.4636)
D: (135.4403,102.3247,4.0018)
E: (156.1425,78.6381,4.2284)
F: (162.8964,101.4897,4.2715)

What I need to know is: 
1.	What is my current position (x,y,z)?
2.	What is my current orientation (how many degrees off is my local
angle and elevation from that of the surveyed points?)
3.	What is the confidence that I am at that position or what is the
range of positions I could be in?
3a.	Depending on the number of points necessary to perform the
resection (I?m guessing 3 here) I can run through all combinations of
3 points and get a set of potential positions (hopefully they will all
be very close to each other). I?m assuming I should simply take the
weighted center of these points and make my position that point +/-
whatever the greatest range from the center is. If this is the case,
please let me know. If there is a better method of determining this,
please show an example.

Please let me know if you would like any further clarification, or if
I need to provide additional data.

---

Clarification of Question by q3man-ga on 21 Oct 2006 11:13 PDT

ansel001-ga:

Yes, the angle/elevation/range can be considered spherical
coordinates, and you description of them is accurate.

The problem I'm having with the translation is that the angle
measurements from the unknown point are not necessarily in the same
coordinate system as my reference points (i.e. my angle 0 is "north"
in the reference points, my angle 0 in the unknown points could be
"east." The angles within each reference frame are consistent between
each other, but not consistent between frames.

Also, range is distance and all angles are in degrees. 

berkeleychocolate-ga:

Your description seems accurate (and was infact the method I was
planning to take if I could determine my orientation). The difficulty
that I am having is that I am not sure of my position OR orientation
in the unknown position X.

---

Clarification of Question by q3man-ga on 25 Oct 2006 10:51 PDT

I've done some more research, and it seems that what I'm looking for
is called 'trilateration' or 'multilateration' (there are some good
wikipedia articles on both). I need to use the distance data from the
points to determine my 3d position, then determine what the angles to
those points should be and subtract that from what the angles actually
are.

If anyone could walk through a trilateration or multilateration from
the above data, it would be enough for a solution.

---

Request for Question Clarification by hedgie-ga on 29 Oct 2006 12:52 PST

Hi q3

     I read the question twice, the comments and wikipedia articles once,
and my conclusion is that problem is simple - once it is well described.

As stated, using undefined terms, the formulation needs  work.

I am willing to work with you better formulation and then solution, provided

 you will cooperate (respond promptly to RFCs)
 and that solution will be worked out in the post answer RFC dialog.

Please ask if the GA jargon I am using is not clear. 

Ypu may want to look at some of my old answers to decide if you want to 
work with me - on the best effort basis - on your problem

Some old answers:

http://answers.google.com/answers/threadview?id=449830
http://answers.google.com/answers/threadview?id=710220
http://answers.google.com/answers/threadview?id=706840

I also would expect you to rate the answer once  we are finished.


Hedgie

---

Request for Question Clarification by hedgie-ga on 29 Oct 2006 22:03 PST

Also,

 you would have to the actual calculation yourself, once we figure out how.

It sounds like you are talking about spherical coordinates.  A point
in 3 space can be determined by giving, the distance from the origin
and two angle measurements.  The first angle measurement is the angle
from the positive x axis toward the positive y axis.  The second angle
measurement is the angle from the positive z axis  towards the xy
plane.

If you create a translation, you can put your unknown point at the
origin of the new set of coordinates.  It only takes four non-coplanar
points with the distance and two angle measurements from the unknown
point to uniquely determine it.

I assume that by "range" you mean distance.  And that "angle" refers
to the first angle measurement I mentioned and "elevation" refers to
the second.  I also assume your angle measurements are in degrees, not
radians.

Please let me know if I have interpreted your quesiton correctly.

This is how I understand the question: The first information given is
coordinates of N points: A1 thru AN. The second information given is
the vector distances D1 thru DN from an unknown center X to each Ai
measured in spherical coordinates (rho, theta, phi). These can easily
be converted to rectangular coordinates.

It is probably better to convert everything to spherical coordinates
since if the measurements were rho, theta and phi then this is where
the independence of the measurements lie.

So X is overdetermined as Ai + Di for each i=1 thru N. Say Xi = Ai +
Di. One must assume there is an error in each measurement. Assuming
the measurements are independent and all with the same normal
distribution of error for rho (and for theta and for phi), the best
guess for X is its mean and the best guess for the error is the
standard deviation of the Xi's done separately for each spherical
coordinate.

best guess for X is Xbar = (sum of Xi's)/N and
best guess for the error sigma is s = sqrt( sum of (Xi - Xbar)^2 /(N-1) ), where

each of the three coordinates' errors should be done separately. Then
the confidence interval for X is simply Xbar +/- 1.96 * s (1.96 is
used for 95% confidence).

I have your answer.

I do not know how you want your response.  I have an EXCEL spreadsheet
that does it.  I could also explain the geometry if you wish.

Maybe you just want the answers?

either way,  I have from your example data:

Elevation: 6 possibilities, ranging from 0.024861324 to 0.026590482
with an average of 0.025501976 and a standard deviation of 0.000641306

Orientation: 30 answers, ranging from  -132.6594308 to -140.8950251
with an average of -139.5125062 and a standard deviation of
1.893133635

X position: 30 answers, ranging from  -1.13030109 to -0.532831892 with
an average of -0.651004959 and a standard deviation of 0.135038228

Y position: 30 answers, ranging from  -8.711172121 to -5.863268573
 with an average of -7.706949961 and a standard deviation of 0.826416746

Find excel sheet at www.ee.ualberta.ca/~hillyer/FTP/GoogleAnswers.xls

inventorbob, 

I am unable to access the spreadsheet you posted. I'm getting the following error:

Access forbidden!

You don't have permission to access the requested object. It is either
read-protected or not readable by the server.

I have decided to withdraw my answer, when ACR dialog denegerated to 
exchanges like :

Clarification of Answer by hedgie-ga on 09 Nov 2006 17:19 PST 
q3man-ga!

When I respond to a question, I like to finish 
and get to the point when customer says

---------------^^
Request for Answer Clarification by mxnmatch-ga on 22 Sep 2003 00:04 PDT 
I've got it working! Thanks for all your help! 

.......vv


>>I cannot do that, when customer does not cooeperates 

>>and starts introducing new, confused and inpractical notation such as:

(Xk-((Xu-Xt)*XrX*XrY*XrZ))+(Yk-((Yu-Yt)*YrX*YrY*YrZ))+(Zk-((Zu-Zt)*ZrX*ZrY*ZrZ))==0

I'm sorry if what I wrote was confusing for you.
Please try to understand that   
>>P.o = |x,y| = |a,b| + | r11, r12; r21, r22| *  |X,Y| 
is possibly just as confusing to me. I'm attempting to solve a problem
that is admittedly beyond my mathematical abilities. Although useful,
I'm not seeking a lesson in 3d geometry. I need a algorithm to solve a
specific single-case problem.


Main problem here was not lack of capabilities, but askers negative attitude.
I hope that some GAR will find more patience in dealing with this simple
geometry problem.

I have corrected the permissions on the file.  You may try again.

http://www.ee.ualberta.ca/~hillyer/FTP/

choose

GoogelAnswers.xls