0

I am given coordinates for my location (55.1858, -162.7211). I would like to find the city I am at (or near) if it exists in my dataset. The dataset (tens of thousands of coordinates) has all cities that I am interested in, and one or more coordinates corresponding to that city (depending on the size of the city):

Cold Bay, Alaska, 55.1858,-162.7211
False Pass, Alaska,54.8542,-163.4113
King Cove, Alaska, 55.0628,-162.3056
...

What's the best algorithm (preferably in JavaScript) to find the city that I am in (Without using any APIs, Google Maps etc..)?

I had a few ideas, but they're probably not the best as they're all brute force methods:

  1. Draw a radius around my coordinates of a certain distance and then loop through the dataset to find if any of the existing coordinates are in this radius. If one or more are, then loops through them and see which I am closest to via their distance.
  2. Somehow, start to round my coordinates at the furthest decimal place and check after each rounding if this new set of rounded coordinates exists in the dataset.

I feel like these are really bad ideas and would love some guidance or recommendations on good algorithms for this type of searching.

now_world
  • 940
  • 7
  • 21
  • 56
  • why not just calculate the distance to all coordinates you have - that's not "brute force", that's maths - unless you have in the order of hundreds of thousands of coordinates, then just measuring every distance is not going to be a problem – Bravo Nov 03 '19 at 00:22
  • Is that efficient though? That'd mean looping through tens of thousands of coordinates – now_world Nov 03 '19 at 00:24
  • oh, so you have 10s of thousands... have you tried that to see how long it takes? – Bravo Nov 03 '19 at 00:25
  • I have not. If it's the best way, then I'll just have to do it. But this will eventually run on user's browsers and I would like to find the best way to do this since it impact's the user's experience directly – now_world Nov 03 '19 at 00:26
  • not saying it's the best way - if you have an efficient way of performing your first suggestion, then that may well be the best way - but how do you determine if a location is within a particular radius without iterating through every location anyway? and if you choose a radius that's too small, you'll need to repeat with a bigger radius – Bravo Nov 03 '19 at 00:30
  • @LightnessRaceswithMonica - why would you do a binary search? you calculate the distance to each location, and keep the smallest one as you iterate – Bravo Nov 03 '19 at 00:31
  • @Bravo Yep, you're right. I'd have to loop through each coordinate any way. – now_world Nov 03 '19 at 00:31
  • @Bravo That's an O(n) operation and requires a ton of memory.... why would you _not_ do a binary search? – Lightness Races in Orbit Nov 03 '19 at 00:32
  • Just don't implement this yourself, and not in JS. Use a [spatial database](https://en.wikipedia.org/wiki/Spatial_database) instead. – Bergi Nov 03 '19 at 00:34
  • @orangeMint "*this will eventually run on user's browsers*" - then why is the question tagged [[tag:node.js]]? And no, processing a data set of tens of thousands is not a good idea on the client side. – Bergi Nov 03 '19 at 00:35
  • @Bergi it will only run on the user's browser if possible. By possible I mean, after I test and get a fast enough result that I'm happy with then it will. If not, then I won't be able to implement this feature. – now_world Nov 03 '19 at 00:37
  • 1
    @orangeMint It should be possible for a few thousands entries, depending on the memory and processing power of the client device. Research the [spatial search algorithms](https://en.wikipedia.org/wiki/Spatial_index#Spatial_index) that geodatabases use for this task. And don't forget to define a proper distance metric, which isn't easy with spherical coordinates in itself. – Bergi Nov 03 '19 at 00:43
  • @LightnessRaceswithMonica - I'd love to know how you binary search a collection of 10 thousand locations given a random location that is close to but not equal to one of those locations that are described in two dimensions, not one - and find the shortest distance – Bravo Nov 03 '19 at 01:20
  • @LightnessRaceswithMonica `That's an O(n) operation and requires a ton of memory` - if you have all 10s of thousands of coordinates to do a binary search, how would that reduce the amount of memory required? – Bravo Nov 03 '19 at 01:27

0 Answers0