Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to calculate distance from different markers in a map and then pick up the least one

I have to get distance from different markers on the map to the current location of the device and the pick up the shortest one. I have the lat and long for the markers and the current location lat and long can be fetched dynamically.

Suppose I have 5 markers on the map, Bangalore (Lat : 12.971599, Long : 77.594563), Delhi (Lat : 28.635308, Long : 77.224960), Mumbai (Lat : 19.075984, Long : 72.877656), Chennai (Lat : 13.052414, Long : 80.250825), Kolkata (Lat : 22.572646, Long : 88.363895).

Now suppose the user is standing somewhere near Hyderabad (Lat : 17.385044, Long : 78.486671). When the user clicks the button, the app should calculate distance from each marker and pick up and return the shortest one, that will be Bangalore here.

There is a way possible to do it with help of local databases. Can anyone help on that please.?

Can anyone suggest me a nice way to do this, or come up with a good code if you please can. Thanx in advance.

like image 624
Akshat Avatar asked Oct 07 '13 06:10

Akshat


People also ask

How do you find the distance between two waypoints?

Distance between two points is the length of the line segment that connects the two points in a plane. The formula to find the distance between the two points is usually given by d=√((x2 – x1)² + (y2 – y1)²). This formula is used to find the distance between any two points on a coordinate plane or x-y plane.

How do you find the shortest distance between two places?

The shortest distance between two points is a straight line. This distance can be calculated by using the distance formula. The distance between two points ( x 1 , y 1 ) and ( x 2 , y 2 ) can be defined as d = ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 .

What is the formula for calculating distance?

Learn how to find the distance between two points by using the distance formula, which is an application of the Pythagorean theorem. We can rewrite the Pythagorean theorem as d=√((x_2-x_1)²+(y_2-y_1)²) to find the distance between any two points.


2 Answers

from your comment I see that you expect a maximum of 70-80 locations. This is not much.

You can simply do a brute force search over all markers and take the minimum.

Iterate over all markers, and search min distance:

    List<Marker> markers = createMarkers(); // returns an ArrayList<Markers> from your data source
    int minIndex = -1;
    double minDist = 1E38; // initialize with a huge value that will be overwritten
    int size = markers.size();
    for (int i = 0; i < size; i++) {
        Marker marker = markers.get(i);
        double curDistance = calcDistance(curLatitude, curLongitude, marker.latitude, marker.longitude);
      if (curDistance < minDist) {
         minDist = curDistance;  // update neares
         minIndex = i;           // store index of nearest marker in minIndex
      }
    }

    if (minIndex >= 0) {
       // now nearest maker found:
       Marker nearestMarker = markers.get(minIndex);
       // TODO do something with nearesr marker
    } else {
      // list of markers was empty
    }

For calcDistance, use the distance calculation method provided by android. (e.g Location.distanceTo() )
For 70-80 markers there is no need to make it faster and much more complex. If you have some thousands points then it is worth to invest in a faster solution (using a spatial index, and an own distance calculation which avoids the sqrt calc).

Just print out the current time in milli seconds at the begin and at the end of the nearest maker search, and you will see, that it is fast enough.

like image 93
AlexWien Avatar answered Nov 14 '22 03:11

AlexWien


If you want to find the shortest one not list the closest and you want the process to scale to a large amount of locations, you can do some filtering before you calculate distances and you can simplify the formula to speed it up as you don't care about actual distances (i.e. remove the multiplication by the radius of the earth).

Filtering algorithm, looping through each location :

  1. Calculate the difference in lat and long.
  2. If both differences are larger then a previously processed pair, discard it.
  3. Calculate distance, keep smallest.

You can further help the algorithm by feeding it with what might be close locations first. For example if you know one of the points is in the same country or state.


Here is some Python code to do that, use it as pseudocode for your solution :

locations = { 
    'Bangalore' : (12.971599, 77.594563), 
    'Delhi' : (28.635308,  77.224960), 
    'Mumbai' : (19.075984,  72.877656), 
    'Chennai' : (13.052414,  80.250825), 
    'Kolkata' : (22.572646,  88.363895)
    }

from math import sin, cos, atan2, sqrt

EARTH_RADIUS = 6373  # km

def distance(a, b):  # pass tuples
    (lat1, lon1) = a
    (lat2, lon2) = b
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = (sin(dlat/2))**2 + cos(lat1) * cos(lat2) * (sin(dlon/2))**2 
    c = 2 * atan2( sqrt(a), sqrt(1-a) ) 
    return EARTH_RADIUS * c


current = (17.385044, 78.486671)  # current lat & lng

closest = None
closest_name = None
for name, cordinates in locations.iteritems():
    d = distance(current, cordinates)
    if closest is None or d < closest:
        closest = d
        closest_name = name
    print "~%dkm (%s)" % (distance(current, cordinates), name)

print "\nClosest location is %s, %d km away." % (closest_name, closest)

Output :

~5700km (Kolkata)
~13219km (Chennai)
~12159km (Bangalore)
~7928km (Delhi)
~10921km (Mumbai)

Closest location is Kolkata, 5700 km away.
like image 35
Emil Davtyan Avatar answered Nov 14 '22 03:11

Emil Davtyan