CODEWITHSUNDEEP
phparraysmaps
robertlayton
robertlayton

Reputation: 722

Find closest lat/lng in PHP for an array of input values

I have code that, for an array of lat/long pairs, finds the nearest lat/long pair from another array:

Input:

$reference_array, which is an associative array, where the keys are "labels", and the values are the lat/long of that label. For example, it could match town name to the centroid of the town.

$input_array, which is a list of lat/long pairs.

I need to find the label from $reference_array that is nearest to each of the points in $input_array. I also have a maximum radius, so any nearest point not within that radius is given the "nearest label" of null.

I have code that works - I iterate through each array, compute the distance between each pair, and then record the nearest label (and its distance) for each point in $input_array. This works, and is basically the same as this question, but is not efficient, and my script is timing out with relatively few points. I can't control the size of $reference_array, so there are always going to be large amounts of comparisons that need to be performed.

My question - what data structures or algorithms can I use to improve the efficiency of this computation?

Upvotes: 0

Views: 306

Answers (1)

Stanislav Baturin
Stanislav Baturin

Reputation: 319

You can improve the efficiency if at first you check the points is included in the square with side 2 * radius or not. Becouse a comparison operations is much smaller load than the calculation of the distance.

Upvotes: 2

Related Questions