0

I have a list of locations , following this pattern:

[1] = {lat = -40.2452, longitude = -76.2489},
[2] = {lat = -40.2452, longitude = -76.2489},
[3] = {lat = -40.2452, longitude = -76.2489},
[4] = {lat = -40.2452, longitude = -76.2489}

and a localition

location = {lat = -40.2452, longitude = -76.2489}

and I want to calculate Which of the locations this Within the distance.

I found a formula that calculates the distance between two points.

but if this list is big!

is there any faster way?

or you can go through the list in a loop ?

FOR LOCATION IN LISTLOCATION DO
    IF GETDISTANCE(LOCATION, LOCATION2) <= DISTANCE
        SAVE THIS LOCATION
    END
END

These values are a example

Miller Dominguês
  • 31
  • 5
  • If you're worried about performance, and you're on Android, why not put your data into a SQLite database, and query. More in this answer: http://stackoverflow.com/questions/3126830/query-to-get-records-based-on-radius-in-sqlite – Jeremy Gordon Jun 06 '16 at 18:36
  • I know is for example purpose, but all your locations are the same. – Alex S. Diaz Jun 06 '16 at 18:38
  • Your example array has all the same items. If there is a high probability that there will be a lot of duplicate items, removing them before calling `GETDISTANCE(LOCATION, LOCATION2) ` them would increase performance. – damjanh Jun 06 '16 at 18:50
  • I request to a server which are clients next and send my location, and the server does this calculation and returns a list – Miller Dominguês Jun 06 '16 at 18:53
  • these values ​​are an example – Miller Dominguês Jun 06 '16 at 18:58

2 Answers2

1

Basically you have to check each and every point, no other option. The distance formula (Haversine) is indeed slow, since it uses few trigonometric functions. What you actually want is to plot a circle around your point, whose radius R is the distance, and check for each point if it's inside that circle:
enter image description here

The problem is that your point are given as (lat, long) pair, not (x,y) pair, so you can't use "regular" trigonometric methods, like the circle's equation.
Instead, you have to find a square that bounds that circle. Go 90 degrees to the north and south, find the upper and lower longitudes of that square. Do the same to rhe east and west, find the upper and lower latitudes:
enter image description here

Now you can check for each point if it's inside the box, and you can do it easily with simple comparsions: 

if lon > lon1 and lon < lon2
   and lat > lat2 and lat < lat1

which is really computionally cheap.
The only problem is with points that are inside the blue area:
enter image description here

They are inside the square but not inside the circle, so you'll have to use the Haversine formula for them.
If most of your points are not in the square, this method will save you time, because eliminating them is pretty easy.

TDG
  • 5,909
  • 3
  • 30
  • 51
  • If I continue using the same formula , a server could perform the calculation constantly ? – Miller Dominguês Jun 06 '16 at 20:08
  • I request to a server which are clients next and send my location, and the server does this calculation and returns a list – Miller Dominguês Jun 06 '16 at 20:09
  • You've asked for a faster way and I think that my solution is faster than using the Haversine formula for each point. It's up to you to decide which method to use and whether to do it at the server or the client. – TDG Jun 07 '16 at 16:25
  • @nasch These are the points that thedistance between them and the center is greater than R. – TDG Oct 07 '17 at 05:48
  • Ah of course, so you're calculating the distance for every point inside the square, rather than every point in the list. Makes sense, thanks. – nasch Oct 07 '17 at 12:52
0

If you are on Android then you can use the "distanceBetween" method of the Location class. This method has it's implementation in Java (you can do a loop to test the distance between your location and the location list elements), so if you want higher performance you should do it natively (NDK). If you do it natevely you should pass the complete list to the native method and not one by one because the context change between the virtual and the native environment can be costly.

josemgu91
  • 719
  • 4
  • 8