0

I am creating an app that is interested in having a highly accurate estimate of an Android device's location. I am also required to send this data to a proxy server.

My current implementation fetches a GPS location on the device itself and sends that to the proxy. In addition, it sends data required by Google's GeoLocation API such as wifi access points to the server, and the server then makes a call to the API and acquires another Location. Both the GPS Location and Geolocation are on the form 

{
  center: {
    lat: ...,
    lng: ...,
   },
   accuracy: ...
}

This means that I end up with two different estimators for a single location, each with their own center and accuracy. My question is as follows:

Is there a way to combine these two Locations into a single, more accurate location? Ideally I'd like to use some API that takes several objects on the form above and returns a single object with a new center and a lower accuracy value than the provided locations. If there is no such API, it's also fine if someone could help me develop an algorithm that has the desired effect.

Since these location estimate the same true location, combining them somehow should be able to yield a better result. I was not able to find an answer as to how either by googling or by reading several pages of all questions tagged with google-geolocation.

This is a slightly difficult question to categorize, it might turn out to be better suited for the statisticians over at https://stats.stackexchange.com/. If so, let me know and I'll take my question there.

Eduard Itrich
  • 836
  • 1
  • 8
  • 20
finnss
  • 208
  • 2
  • 12
  • This question has been downvoted a lot. I'd love feedback as to why that is so I can improve in the future! – finnss Jul 04 '17 at 11:48
  • Don't know why are people down voting without a reason but nevertheless @finnss can you share the two results to compare what's the difference between two lat/lng and the accuracy?? – sumit Jul 04 '17 at 11:52
  • Sure thing! For the sake of privacy I edited the Lat and Lng values, but the accuracy values represent real fetched data. My Geolocation: `{ accuracy: 102.0, center: { lat: 63.035338900000005, lng: 10.0006738 } }` My GPS Location: `{ accuracy: 30, center: { lat: 63.03509974889457, lng: 10.000376850739121 } }` – finnss Jul 04 '17 at 12:00
  • Generally, downvoting without giving a reason is not at all useful, and should (to my mind) not be allowed in SO. I think your question is well stated and of interest to many developers, e.g. for me. – Reinhard Männer Nov 04 '19 at 19:32
  • Maybe you should drop the android tag. I am an iOS developer, but your question is as well as interessant for me. – Reinhard Männer Nov 04 '19 at 19:56

1 Answers1

2

Basically, your problem breaks down to finding the circle containing the intersection of the two circles given by the Geolocation and the GPS location.

For the sake of simplicity, let's call the latitude of the Geolocation x1, the longitude y1 and the accuracy r1, whereas we denote the latitude of the GPS location x2, the longitude y2 and the accuracy r2. Please note that I'm using Cartesian Coordinates. You'll have to convert your given Polar Coordinates before doing the beneath outlined calculations.

These two circles can

  • be completely seperate and have no common points. We drop this case by making the assumption that the reported locations are correct, i.e. the device isn't located outside of the calculated locations. If you don't want to make this assumption - choose the more accurate location.
  • be contained within another. In this case you simply choose the smaller (i.e more accurate) circle as the optimized location.
  • intersect in exactly one point (Jackpot! - you've got the exact location)
  • intersect in an asymmetric lens which looks like this intersecting circles

What you need to calculate is the midpoint (x3,y3) of the asymmetric lens on the line between [(x1,y1)(x2,y2)] and the radius r3 of the spanning circle. optimized location

As a good ressource I recommend you Paul Bourke's page on this topic which also offers some implementations, e.g. in Python or C. Please don't mix up the points x3 and y3 from the article since I've choosen an alternative naming which fits better to your problem.

Your optimized location is then given by x3 = x1 + a*(x2-x1)/d, y3 = y1 + a*(y2-y1)/d and r3 = sqrt((r1)^2-a^2) where a = ((r1)^2-(r2)^2+d^2)/2*d and d = (sqrt((x2-x1)^2+(y2-y1)^2).

The rest is up to you since I don't know which language you're using. Feel free to comment on this answer if something isn't clear.

EDIT: If you search for circle circle intersection, you will find even more examples, e.g. this question involving Google Maps API

Eduard Itrich
  • 836
  • 1
  • 8
  • 20
  • Thank you! That's much better than what I have. However, isn't this valid only if the probably is evenly distributed within each circle? The map locations are most likely to be in the center of each circle and then has a falling probability towards the edges. So if I'm understanding correctly, they're a 2D representation of something like [this](https://i.stack.imgur.com/Tz6TC.png). The edges of the circles are seemingly arbitrarily chosen; for the GPS circles, it's defined as one standard deviation from the expected value. – finnss Jul 05 '17 at 12:33
  • I know that Google provides a FusedLocation API, so I checked out the Android source code. In the key function, [isBetterThan(Location, Location)](http://androidxref.com/7.1.1_r6/xref/frameworks/base/packages/FusedLocation/src/com/android/location/fused/FusionEngine.java#202), they use a very simple algorithm that just selects whichever location has the best accuracy. The only extra logic is for detecting whether one of the locations are outdated. If that's good enough for Google, is that an argument in favor of this issue being too complicated? I'd still like to find a solution. – finnss Jul 05 '17 at 13:25
  • If you assume that a device is always located somewhere within the reported location (and not outside), then the device will always be somewhere in the intersection of both locations, regardless of the probability distribution among the circle. Hence, the above given calculations will always optimize your location if and only if both circles are intersecting. The function `isBetterThan` you mentioned only distinguishes the better location, but doesn't calculate a better one. You asked for a way to optimize the location given two locations which is done by circle-circle intersection. – Eduard Itrich Jul 05 '17 at 13:51
  • Thank you very much for your help! Like I said though, the circles do **not** guarantee that the true location is somewhere within them. For a GPS Location, there's a 68% chance (one std. deviation) that the true location is within the circle. For a Geolocation, the circle might indicate something else like a 95% certainty. Given that, do your statements and formulas still hold? Is there a way to include the 68% and 95% numbers as weights somehow? – finnss Jul 05 '17 at 14:20
  • Sorry that I didn't catch your point initially. If you want to somehow give the locations more or less weight, you can shift the midpoint `(x_3,y_3)` towards the more reasonable center. Please note that in this case the formulas don't hold anymore. You then need to calculate one of the intersection points of the circles as done on Paul Bourke's page and then get the distance to `(x_3,y_3)`. Another possibility would be to shrink or enlarge the circles by the following [conversion rules](https://en.wikipedia.org/wiki/Circular_error_probable#Conversion_between_CEP.2C_RMS.2C_2DRMS.2C_and_R95). – Eduard Itrich Jul 06 '17 at 06:44
  • Please not that in your 2 drawings, (x1,x2) should read (x1,y1) – Reinhard Männer Nov 04 '19 at 19:52