Algorithm to find nearest point

Question

I have a list of a few hundred cities with their latitude/longitude. Given another location (also in lat/long) I need to find the nearest city.

As I don't use any GIS, by now the obvious algorithm is to make a loop for all the cities, calculating the distance between the points.

Making the loop is practicable for me, but there is some easy-to-implement algorithm to accomplish that more efficiently? Or some light Java library that can help to solve that?

Notes: I don't need/want a complete GIS solution or a heavy/complicated library. I prefer a less good but easiest and lighter solution because that is the only thing that I need to solve.

Answer 1

I investigated exactly this question 20 years ago when designing a desktop GIS. We needed to find point-to-point distances interactively; our target was to do the computations in less than 1/2 second for thousands of points. Testing (on a 25 MHz 486 PC!) showed that we could compute all the distances, exactly as you describe (with the simple obvious algorithm), so quickly that it made no sense to create a more sophisticated solution, such as a quadtree structure.

For computing distances to a single "probe" point your options include (a) projecting all points using an equidistant projection centered at the probe point or (b) adopting a spherical earth model and using the Haversine formula. The first is appropriate if you need the accuracy of an ellipsoidal model. In either case the calculations are reasonably fast, probably taking less than 1000 ticks: you could query around a million points a second with a single processor.

Fast enough for you? If not, the brute-force method parallelizes easily and scales directly with the number of processors: just divide the points among the processors and then do a final comparison of the closest one found by each processor.

If you need to go faster, you can use various approximations to screen points. For example, if you are between -88 and +88 degree latitude and the nearest point found so far is 200 km away, then any point whose latitude differs from the probe point's latitude by more than 2 degrees cannot possibly be closer (because anywhere on earth, one degree of latitude exceeds about 110 km). In many cases this kind of pre-screening might enable you to process hundreds of millions of points a second.

Answer 2

I agree with others that a simple loop should be effective for "a few hundred cities".

Given your application, dealing with ellipsoidal distances is probably major overkill - you are probably dealing with weather predictions whose locality is hardly down to a few meters. Spherical geometry is simple enough that you could easily do that in your loop.

It could be even simpler (eg; use delta lat as y and delta lon * cos(lat) as x and find the minimum x^2+y^2). You are using the cosine of the target latitude, which you only calculate once. This will be increasingly inaccurate for distant cities, but they will be rejected anyway so don't matter. Assuming that your nearest city is generally within a couple hundred kilometers, the chances of a different result (nearest city) using this vs using a more accurate formula are quite small and would occur only when the differences are small enough that "which forecast is more accurate" would probably depend on other factors anyway (ie: lost in the noise).

Unless you are using an embedded system or a slow interpreter, you can probably afford to just use the spherical formals others are suggesting, tho.

Answer 3

This is in addition to what has already been said, but I thought I would note the importance of picking an appropriate data structure. I wrote my own code for a K-Function in .NET, and found that using efficient collections sped things up substantially. Sorry I don't know the O notation for exact speeds. I used two Dictionaries for x and y coordinates with the point ID as a key. I don't know Java so couldn't suggest anything.

Cheers, David