View Question
Q: Determining 3D position and orientation via spatial resection ( No Answer,   7 Comments )
 Question
 Subject: Determining 3D position and orientation via spatial resection Category: Science > Math Asked by: q3man-ga List Price: \$50.00 Posted: 20 Oct 2006 12:37 PDT Expires: 19 Nov 2006 11:37 PST Question ID: 775421
 ```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.```
 There is no answer at this time.

 Subject: Re: Determining 3D position and orientation via spatial resection From: ansel001-ga on 20 Oct 2006 18:10 PDT
 ```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.```
 Subject: Re: Determining 3D position and orientation via spatial resection From: berkeleychocolate-ga on 20 Oct 2006 18:46 PDT
 ```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).```
 Subject: Re: Determining 3D position and orientation via spatial resection From: inventorbob-ga on 30 Oct 2006 12:22 PST
 ```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```
 Subject: Re: Determining 3D position and orientation via spatial resection From: inventorbob-ga on 30 Oct 2006 12:27 PST
 `Find excel sheet at www.ee.ualberta.ca/~hillyer/FTP/GoogleAnswers.xls`
 Subject: Re: Determining 3D position and orientation via spatial resection From: q3man-ga on 02 Nov 2006 09:04 PST
 ```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.```
 Subject: Re: Determining 3D position and orientation via spatial resection From: hedgie-ga on 18 Nov 2006 05:36 PST
 ```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.```
 Subject: Re: Determining 3D position and orientation via spatial resection From: inventorbob-ga on 28 Nov 2006 09:37 PST
 ```I have corrected the permissions on the file. You may try again. http://www.ee.ualberta.ca/~hillyer/FTP/ choose GoogelAnswers.xls```