Looking for the nearest coordinates in an array?

Question

I have two types of ArrayList array, Double, 1.latitudes 2. longitudes, each of them has more than 200 elements

let's say I give random test coordinates, for example (1.33, 103.4), format [latitude, longitude]

Is there any algorithm that makes it easy to find the closest point, or do I need brute force to calculate every possible point, find the hypotenuse, and then compare more than 200 hypotenuses to get the nearest point back? thanks

Answer 1

Sort an array of points along one axis. Then find the point in the array closest to the desired point along this axis and calculate the distance (using any metric that matches the problem topology and scale).

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

This can lead to the need to search the entire array and is a Branch and bound form limited by the geometry of the problem. If the points are reasonably evenly distributed around the point you are looking for, then scanning will not require a lot of testing.

Alternative spatial indexes (such as ATVs) will give better results, but your small number of points will make the installation cost when preparing the index much more than a simple view. You will need to track the position changes caused by sorting, since your other array will not sort the same. If you change the data into a single array of points, then sorting will change the order of whole points at the same time.

Answer 2

If your arrays are sorted, you can use a binary search to find the position of the requested point in the array. After you find the index, you must check four nearby points to find the nearest one.

1) Suppose you have two sorted arrays of longitude - wise and latitudinal -

2) First, you search and find two adjacent points.

3) Then you search for the second and find two more points

4) Now you have two to four points (results may overlap)

5) These points form a square around the destination

6) Find the nearest point

Answer 3

It is not true that the closest lat (or long) value should be selected to search along the long (or lat) axis, in fact you can stay on the lat (or long) line, but far away along the long (or lat) value

the best way is to calculate all the distances and sort them