Re: Triangulation Problem

*Subject*: [mg3015] Re: Triangulation Problem*From*: rusin at washington.math.niu.edu (Dave Rusin)*Date*: 22 Jan 1996 06:32:52 -0600*Approved*: usenet@wri.com*Distribution*: local*Newsgroups*: wri.mathgroup*Organization*: NIU Mathematical Sciences*Sender*: mj at wri.com

In article <4diafm$84a at dragonfly.wri.com>, david hoare <techie at io.org> wrote: > >I am looking for the trigonometric / algebreic formulae one would use >to triangulate an unknown position, knowing 3 fixed points and the >respective distances to the unknown point. (make sence?) >Oh - in 3 dimensional space. So you want to know what point is of distance D1 from point P1, and likewise of distances D2 and D3 from P2 and P3 respectively. Think geometrically! The set of all points meeting the first condition is a sphere of radius D1 centered at P1. The set of points meeting the first two conditions is then the intersection of two such spheres, which is clearly a circle, perpendicular to the line segment joining P1 and P2, and of some radius r, where I can compute r knowing the distance D12 between P1 and P2. (You'll have to draw your own picture since I failed my kidergarten ASCII-art class): if x is the distance from P1 to the center of this circle, and thus D12-x the distance from there to P2, we need r^2+x^2=D1^2 and r^2+(D12-x)^2=D2^2, forcing x = [D12^2+D1^2-D2^2]/(2 D12) and thus r = sqrt(D1^2-x^2) is known. At this point I think it's easiest to parameterize the circle: Let v0 = (P2 - P1)/ D12 be the unit vector from P1 to P2. If v is any vector at all not parallel to v0, then the cross-products v1 = v0 x v and v2 = v1 x v0 are perpendicular to each other and to v0. Scale v1 and v2 to make them also of unit length. Then the circle described in the previous paragraph is the set of points P = r cos(t) v1 + r sin(t) v2 + (P1 + x v0) Now apply your third condition: you want dist(P, P3) = D3. If the vector from P1 to P3 is decomposed in the current coordinate system as a v1+ b v2 + c v0, then that means you need D3^2 = (r cos(t)-a)^2 + (r sin(t)-b)^2 + (x-c)^2. This is a relatively simple trigonometric equation to solve; once the smoke clears it looks like A cos(t) + B sin(t) = C. I usually solve such equations by dividing by sqrt(A^2+B^2). Choosing an angle u so that sin(u) = A/sqrt(A^2+B^2) and cos(u)= B/sqrt(A^2+B^2), we have just the equation sin(t+u) = C/sqrt(A^2+B^2). Take arcsines and subtract u to discover t; plug back into the parameterization of the circle to find your point. Alternatively you can replace the trig of the previous paragraph with some algebra by parameterizing the unit circle as the set of points of the form ( (1-t^2)/(1+t^2), (2t)/(1+t^2) ), instead of the usual (cos(t), sin(t)). I don't think this is particularly easier, unless you have an aversion to trig functions and their inverses. >And actually, the reverse operations would be handy too...ie: given a >known central point, AND 3 other fixed points, how to find the lengths >of the lines required to meet at that first point, in 3D. The lengths of these lines are simply given by the distance formula (Pythagorean theorem). dave