Algorithmic decision to find the nearest city based on lat / lon

Question

Please note that there are other similar questions, but 1) I do not want to rely on an online service, 2) I am looking for a clean algorithmic solution.

I have a database of cities and their latitudes / longitudes. I am looking for a way that, given an arbitrary lat / lon, finds the nearest city.

The solutions I can think of so far are:

• The obvious solution for brute force, of course, is to calculate all possible distances using the large circle formula. It also takes a lot of time and is O (n).

• Modification of the KD-Tree algorithm may work, but I do not understand how to change this algorithm to work in non-Cart coordinates, as is the case for lat / lon. We can predict the Mercator forecast if that helps.

• Use geodata like PostgreSQL. This does not work for me, period.

Any ideas?

Answer 1

You might think of it as a 3D problem. Convert (lat, lon) coordinates to (x, y, z) coordinates. This needs to be done only once for your database.

For each test point, convert to (x, y, z) and calculate the squares of the distance of the chords (for speed and simplicity) for each city. Choose the nearest one. I believe that the nearest city in 3 places will also be the closest city in terms of a large circle.

If you need a long distance, you can only calculate it for the nearest city.

With a (x, y, z) space, perhaps there is a spatial partitioning structure that you can use to limit which cities you should check. I do not think that there is one that will help directly in the (lat, lon) space. But O (N) is really not that bad. In addition, the problem is very well drawn.

Answer 2

I think you can’t save on calculating the distance matrix between cities, just use the Haversin formula . The calculation of the matrix should be done only once, and you can use it later every time you need it, without any complicated translation.

You can calculate distance with MySQL also if you don't have access to PostgreSQL, for example. See this article on Google Code . The part regarding your problem can be compiled in the following SQL query:

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM cities ORDER BY distance LIMIT 1; 

Answer 3

About 2: Just start with the range [-90..90, -180, 180] .

The only caveat is that when you divide the entire range above into four smaller rectangles and calculate the distance from the current point to each of them, you need to consider the possibility of "overflow". (that the points (0, -179) and (0, 179) closer than it seems from their longitude)

I also assume that you have no cities near the south / north pole.

Answer 4

I had this exact problem and I just decided to use R-Tree, i.e. handle latitude / longitude as if they were Cartesian coordinates.

This works quite well, as there is a noticeable lack of cities along the International Date Line and around the poles, and my application can tolerate, sometimes not getting exactly the nearest city.

Nevertheless, I did not like this inaccuracy, and asked about it . Someone suggested a solution that I think might work, although I did not find the time to implement it:

• There must be a way to transform the coordinates in such a way as to compensate for the different distances between the meridians - this leaves gaps at the 180 ° meridian and the poles that you have to deal with.
• Use two indexes with different coordinate systems: one regular and one that is rotated so that its meridian is 180 ° perpendicular and opposite to that in the main coordinate system. Thus, gaps in one coordinate system are completely regular points in another.

Answer 5

Instead of using latitude and longitude functions, what about using latitude, longitude, and distance from 0.0? Could you use the KD tree?

Of course, it will take time to calculate the distance from each city to the place of origin, but you only needed to do this once.

Answer 6

I was thinking of creating a huge data structure in the form of a balanced binary tree with balanced nodes and a map.

Let them say that root / head starts in London (selected as the center in the horizontal normal world map, GMT): right: the center is the city in the right half of the world map. left: city center in the left half of the map world map.

Now preach in the same way to include all cities in it. x, y will be part of the data. When repeating through each node, we can compare our coordinates of our CityX and ourCityY.

I suppose it's easy to find the closest one on the left with left right nodes running down the tree. I did not implement this, but it seems to have found a good solution.

---

  London 

  / \ 

  New York Singapore / \ / \ Florida Cuba Mumbai Melborne 

etc.

It is based on distance and NOT based on the difference in latitude or longitude. Let's see if this works.