Find average location and remove other locations:

Question

Let's say that I am collecting users location data every 20 minutes. At the end of the day I have an ArrayList of objects that contain lat and long fields and other data.

I have two problems that I am facing and trying to figure out:

1. Some of the locations are taken from inside of a building so they are not very accurate and could be spread around the actual location where the user was at the time.

2. Some of the locations are taken at different times but from the same location, as the user didn't moved.

What I want to achieve is to find all the locations that are near one another: lets say 70 meters, find the average location of all those locations and replace them only with this one average location.

So I am coming to the two important questions:

1. What would be the best way to find all near locations < 70 meter distance (Take in mind that the array contains valid changes in location. So I have to find the groups of near ones and leave the others intact).

2. Is there a method or a way to find the average location of many near ones?

Answer 1

Regarding near positions I previously answered a similar question here: Android Maps v2 - animate camera to include most markers

Specifically I think you would be able to use this piece of code:

private List<Marker> getSurroundingMarkers(List<Marker> markers,
        LatLng origin, int maxDistanceMeters) {
    List<Marker> surroundingMarkers = surroundingMarkers = new ArrayList<Marker>();
    if (markers == null) return surroundingMarkers ;


        for (Marker marker : markers) {

            double dist = distBetween(origin, marker.getPosition());

            if (dist < maxDistanceMeters) {
                surroundingMarkers.add(marker);
            }
        }


    return surroundingMarkers;
}

private float distBetween(LatLng pos1, LatLng pos2) {
    return distBetween(pos1.latitude, pos1.longitude, pos2.latitude,
            pos2.longitude);
}

/** distance in meters **/
private float distBetween(double lat1, double lng1, double lat2, double lng2) {
    double earthRadius = 3958.75;
    double dLat = Math.toRadians(lat2 - lat1);
    double dLng = Math.toRadians(lng2 - lng1);
    double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)
            + Math.cos(Math.toRadians(lat1))
            * Math.cos(Math.toRadians(lat2)) * Math.sin(dLng / 2)
            * Math.sin(dLng / 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    double dist = earthRadius * c;

    int meterConversion = 1609;

    return (float) (dist * meterConversion);
}

Possibly rewriting the Marker part to use LatLng instead.

regarding the averaging, it should be a simple matter of (say you have n LatLng's):

lat_avg = (lat1+lat2+...+latn)/n 
lng_avg = (lng1+lng2+...+lngn)/n 

latlng_avg = new LatLng(lat_avg, lat_lng)

Answer 2

I' not sure how you're getting the user's location - whether your using a traditional LocationManager or play services. I've always modeled my location getting on this approach documented on the android developers blog. If you're flexible in switching between location gathering methods, whether the person is inside or outside should not matter that much. You should be getting the best possible location at any given time.

Assuming you're getting locations on a sufficient time schedule (I don't know when you're checking for updates but since you want everything inside a 70m radius I'm assuming its on a time schedule and not distance change) the basic way to find the average point is:

(1) Convert each lat/long pair into a unit-length 3D vector. (2) Sum each of those vectors (3) Normalise the resulting vector (4) Convert back to spherical coordinates

That approach is documented here as well as in a much earlier SO post on calculating the average of a set of angles

The example code is pretty easy to follow - just plug in the lat long values you get from your location grab and you should be ok.

Answer 3

Well for markers that come from the same location I have created the following method:

public ArrayList<MyLocation> removeSameLocationMarkers(List<ParseObject> objects, int maxDistanceMeters) 
{
    boolean isLocationExist;
    ArrayList<MyLocation> acceptedLocations = new ArrayList<MyLocation>();

    if (objects == null) return acceptedLocations;

    for (ParseObject location1 : objects) 
    {
        isLocationExist = false;
        for (MyLocation location2 : acceptedLocations) 
        {
            if (!location1.equals(location2)) 
            {
                float distance = distBetween(location1.getDouble("latitude"), location1.getDouble("longitude"), location2.getLatitude(), location2.getLongitude());
                if (distance < maxDistanceMeters) 
                {
                    location2.addTimeToLocation(location1.getString("time"));
                    isLocationExist = true;
                }
            }
        }
        if (!isLocationExist)
        {
            Location newLocation = new Location("");
            newLocation.setLatitude(location1.getDouble("latitude"));
            newLocation.setLongitude(location1.getDouble("longitude"));
            String provider = location1.getString("provider");
            if (provider != null)
            {
                newLocation.setProvider(provider);
            }
            MyLocation newMyLocation = new MyLocation(newLocation);
            newMyLocation.addTimeToLocation(location1.getString("time"));
            acceptedLocations.add(newMyLocation);
        }
    }

    return acceptedLocations;
}