CODEWITHSUNDEEP
phpsqldatabasealgorithm
aherlambang
aherlambang

Reputation: 14418

searching and sorting through huge array of latitude and longitude

so I have an array of latitude/longitude (it's fake latitude/longitude as you can see, but just to illustrate the point & the original array size is MUCH larger than this):

<?php
$my_nodes = array(
1=> array(273078.139,353257.444),
2=> array(273122.77,352868.571),
3=> array(272963.687,353782.863),
4=> array(273949.566,353370.127),
5=> array(274006.13,352910.551),
6=> array(273877.095,353829.704),
7=> array(271961.898,353388.245),
8=> array(272839.07,354303.863),
9=> array(273869.141,354417.432),
10=> array(273207.173,351797.405),
11=> array(274817.901,353466.462),
12=> array(274862.533,352958.718),
13=> array(272034.812,351852.642),
14=> array(274128.978,354676.828),
15=> array(271950.85,354370.149),
16=> array(275087.902,353883.617),
17=> array(275545.711,352969.325)));

?>

I want to be able to find the closest node (in this case a node is either 1,2,3, 4,5, ...) for a given latitude X and latitude Y. I know the easiest way to do this is to do a for loop and then do a margin error difference (abs(latitude_X - latitude_X_array) + abs(latitude_Y - latitude_Y_array)) but this will be very inefficient as the size of the array grows.

I was thinking of doing a binary search, however the array needs to be sorted first in a binary search, however it's hard to sort latitude/longitude and in the end we're finding the CLOSEST latitude/longitude in the array for a given lat X, long Y. What approach should I take here?

UPDATE:

Mark has a valid point, this data could be stored in a database. However, how do I get such info from the db if I want the closest one?

Upvotes: 0

Views: 1645

Answers (4)

rik
rik

Reputation: 8612

To sort a multidimensional array in PHP you'd have to iterate over all elements and compare two at a time. For an array of size n that makes O(n) comparisons. Finding the closest node in the sorted array needs O(log n) distance calculations.
If you iterate over all elements, calculate the distance to the target node and remember the closest element, you'd be done with O(n) distance calculations.
Assuming that comparing two nodes means to compare both lat and lon values and thus is O(2), and further assuming that calculating the distance between two nodes is O(3), you end with
O(2n + 3 log n) for binary search and O(3n) for naive search.
So binary search takes n - 3 log n less operations and is round about 33% faster.

Depending on the distribution of your nodes it could be even faster to sort the list into buckets. During filling the buckets you could also throw away all nodes that would go in a bucket that could never hold the closest node. I can explain this in more detail if you want.

Upvotes: 0

GordonM
GordonM

Reputation: 31740

I'm assuming you're storing your data in a DB table like this?

id | lat   | long   | data
------------------------------------------------
1 | 123.45 | 234.56 | A description of the item
2 | 111.11 | 222.22 | A description of another item

In this case you can use SQL to narrow your result set down.

if you want to find items close to grid ref 20,40, you can do the following query: 

SELECT * 
FROM locations
WHERE lat BETWEEN 19 AND 21
AND long BETWEEN 39 AND 41

This will return all the tiems in a 2x2 grid near your specified grid ref.

Several databases also provide spacial datatypes (MySQL and Postgres both do) and they might be worth investigating for this job. I don't, however, have experience with such things so I'm afraid I couldn't help with those.

Upvotes: 0

Rob Agar
Rob Agar

Reputation: 12459

I had a similar problem when I wanted to re-sample a large number of lat/long points to create a heightfield grid. The simplest way I found was like this:

  1. divide the lat/long space up into a regular grid
  2. create a bucket for each grid square
  3. go through the list, adding each point to the bucket for grid square it falls in
  4. then find the grid square your X,Y point falls in, and search outwards from there

Upvotes: 0

Mark Baker
Mark Baker

Reputation: 212412

Have a read of this article which explains all about finding the closest point using latitude and longitude from records stored in a database, and also gives a lot of help on how to make it efficient.... with PHP code examples.

Upvotes: 2

Related Questions