From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: navigation system algebra/geometry problem Date: 21 Jan 1998 16:50:23 GMT In article <34c03610.23074275@news.interlog.com>, Matt Thompson wrote: >The problem is a navigation system where very limited environmental >information can be ascertained. There are three signal sources located >at A(0,0), B(Yb,0) and C(0,Xc), and a receiver at R(Xr,Yr). The >positions of A, B and C are known (ie Yb and Xc are known). The >absolute distances between the three sources and the receiver are not >known, but the differences between the distances is known. For >example, if the distance from A to R is Lar, B to R is Lbr, and C to R >is Lcr, then Labr = Lbr - Lar and Lacr = Lcr - Lar are known. The set of points whose distances to two fixed points differ by a constant form a hyperbola; with points A, B, and C fixed and Labr and Lacr given, you are looking for R to be at the intersection of two hyperbolae. There will be several such points, in general, and their coordinates can be found as roots to polynomial equations. Here is the result from Maple, using your notation (edited for brevity): > readlib(eliminate): > e1:={Lar^2=Xr^2+Yr^2, Lbr^2=(Xr-Yb)^2+ Yr^2, > Lcr^2=Xr^2+(Yr-Xc)^2, Labr=Lbr-Lar, Lacr = Lcr - Lar}: > eliminate(e1,{Lar,Lbr,Lcr,Yr}); [{ , 2 2 2 2 Lacr Labr + Xc Labr - Labr Lacr - Yb Lacr + 2 Yb Xr Lacr Yr = 1/2 ------------------------------------------------------------}, Labr Xc { Labr ( ) } ] > poly:="[2][1]/Labr: > factor(taylor(poly,Xr,6)); 2 2 (Xc - Lacr) (Xc + Lacr) (- Lacr Labr - Yb + Labr Xc + Labr ) 2 2 (- Lacr Labr - Yb - Labr Xc + Labr ) 2 2 + 4 Yb (Xc - Lacr) (Xc + Lacr) (- Yb + Labr - Lacr Labr) Xr 2 2 2 2 2 2 2 + (- 4 Xc Labr + 4 Xc Yb - 4 Yb Lacr ) Xr This poly is the quadratic polynomial you must solve for Xr. Depending on the scale of the various quantities and the kind of program primitives available to you, you can solve for Xr in several ways. The traditional quadratic formula for the roots of course involves the square root of the discriminant, which is > factor(discrim(poly,Xr)); 16 (Xc - Lacr) (Xc + Lacr) (Labr - Yb) (Labr + Yb) 2 2 2 2 2 2 (Labr - 2 Lacr Labr - Xc + Lacr - Yb ) Xc Labr dave ============================================================================== Newsgroups: sci.math From: eclrh@sun.leeds.ac.uk (Robert Hill) Subject: Re: navigation system algebra/geometry problem Date: Thu, 22 Jan 1998 11:27:38 +0000 (GMT) In article <1998Jan21.184553.24490@leeds.ac.uk>, I wrote: > In article <6a590g$ns6$1@gannett.math.niu.edu>, > rusin@vesuvius.math.niu.edu (Dave Rusin) writes: > > > In article <34c03610.23074275@news.interlog.com>, > > Matt Thompson wrote: > > > > >The problem is a navigation system where very limited environmental > > >information can be ascertained. There are three signal sources located > > >at A(0,0), B(Yb,0) and C(0,Xc), and a receiver at R(Xr,Yr). The > > >positions of A, B and C are known (ie Yb and Xc are known). The > > >absolute distances between the three sources and the receiver are not > > >known, but the differences between the distances is known. For > > >example, if the distance from A to R is Lar, B to R is Lbr, and C to R > > >is Lcr, then Labr = Lbr - Lar and Lacr = Lcr - Lar are known. > > > > The set of points whose distances to two fixed points differ by a > > constant form a hyperbola; with points A, B, and C fixed and > > Labr and Lacr given, you are looking for R to be at the > > intersection of two hyperbolae. There will be several such points, in > > general, and their coordinates can be found as roots to > > polynomial equations. > > There can be up to 4 points which lie on both hyperbolae > [...]. > > I at first thought that all 4 points are equally good answers to the > problem, but then I realised that in some cases this is not so. > > Knowing the difference of distances AR - CR, we know not only > a hyperbola on which R must lie, but also which branch of the hyperbola. > > [...] > In some cases the knowledge of the branch enables the ambiguity about R > to be removed. but in others there there is still a 2- or 4-way ambiguity. I am now fairly sure that no more than a 2-way ambiguity can remain if we confine attention to the correct branches of the two hyperbolae. I have also convinced myself that the solution is guaranteed to be unique if, as the original poster suggested, we ignore positions outside the rectangle which has the transmitters as three of its vertices. -- Robert Hill University Computing Service, Leeds University, England "Though all my wares be trash, the heart is true." - John Dowland, Fine Knacks for Ladies (1600)