0

I need to compare a lat-long value with the list of lat-longs and get the nearest value for that given value .For example if I have latitude = 13.820000 and longitude = 47.887777, and I also have a list contains number of lat-longs like [[13.41111,47.11111],[12.42332,53.3345],[14.23423,16.23423]]. In that I need to get the nearest lat-long value from the list for given value.

Dici
  • 25,226
  • 7
  • 41
  • 82
Vicky
  • 1,412
  • 4
  • 18
  • 30
  • http://www.movable-type.co.uk/scripts/latlong.html. You did not research **at all** – Dici Dec 15 '15 at 12:55
  • Are you having a specific problem? Have you tried anything yet? – gmiley Dec 15 '15 at 12:58
  • Calculating the distance between two points is an easy problem and has been asked before. I assume you know how to write a loop to iterate over your List and find the smallest value. – rghome Dec 15 '15 at 13:02
  • I need to calculate not only the distance between coordinates, that distance must be the shortest route by the road. Can i have a function to calculate the distance by the shortest root in roadway – Vicky Dec 16 '15 at 06:59

1 Answers1

1

First of all you need a function to calculate the distance between two geo points. See this. Then you have to define your strategy for searching the nearest neighbour which is the technical name of your problem. You have several approaches:

  1. The easiest is the naive O(N). Compare your location with all the entries in the list and keep the minimum.
  2. Insert once your list in a container structure like kd-tree or grids and find the closest number in the nearby buckets. Amortized O(1)

The choice really depends on what your purpose is and what kind of efficiency you need.

Community
  • 1
  • 1
Simone Zandara
  • 9,401
  • 2
  • 19
  • 26
  • What kind of sort would you use for a list of (bi-dimesional) coordinates ? Option 2 is the best, but I don't think the question is that smart. He's just asking about the basic formula for distance between GPS coordinates, not about performance. Your answer is "better" than the question. – Dici Dec 15 '15 at 14:02
  • mm actually you are right, that would only work on single dimension. I will update the answer. – Simone Zandara Dec 15 '15 at 14:13
  • Haha, it's funny because I made this mistake in an interview, and the interviewer told me it would probably not work, which is right. The second point is excellent however. – Dici Dec 15 '15 at 14:15
  • I should know that since I worked with it, but loooong time ago :) – Simone Zandara Dec 15 '15 at 14:18
  • Thanks for the answer.The distance calculation in that link calculates miles between two lat-long.But i need to calculate distance matrix for that two lat-longs and find the shortest route also. Can i have java function to calculate the shortest route distance – Vicky Dec 16 '15 at 06:52