Finding closest coordinates in an array?

Question

I have two ArrayList, Double data type, 1.latitudes 2. longitudes, each has over 200 elements

say i give a random test coordinates, say (1.33, 103.4), the format is [latitude, longitude]

is there any algorithm to easily find closest point, or do i have to brute force calculate every possible point, find hypotenuse, and then compare over 200 hypotenuses to return the closest point? thanks

Answer 1

Sort the array of points along one axis. Then, locate the point in the array closest to the required point along this axis and calculate the distance (using whatever metric is appropriate to the problem topology and scale).

Then, search along the array in both directions until the distance to these points is greater than the best result so far. The shortest distance point is the answer.

This can result in having to search the entire array, and is a form of Branch and bound constrained by the geometry of the problem. If the points are reasonably evenly distributed around the point you are searching for, then the scan will not require many trials.

Alternate spatial indices (like quad-trees) will give better results, but your small number of points would make the setup cost in preparing the index much larger than a simple sort. You will need to track the position changes caused by the sort as your other array will not be sorted the same way. If you change the data into a single array of points, then the sort will reorder entire points at the same time.