CODEWITHSUNDEEP
algorithmgraph-algorithm
user46372
user46372

Reputation: 159

Find closest nodes given list of nodes and coordinates

Let's say I have a series of locations and their X, Y coordinates:

L1(X1, Y1) L2(X2, Y2) L3(X3, Y3) ... L10000(X10000, Y10000)

And I have a function that returns the distance between 2 locations: distance(L1, L2) = 5 miles

For a given location, how do I find all of the locations within 100 miles? Or if it's easier, the 50 closest locations

Our setup is a SQL Server table of locations and their zip codes. The function takes 2 zip codes, looks up the latitude / longitude of each and returns the distance. We can cache the results since they don't change very often.

Upvotes: 2

Views: 2467

Answers (4)

gvd
gvd

Reputation: 1831

Use a Kd-tree if you can store all location in memory (lat/lon/id). See my answer to another question Kd-trees allows for efficient nearest neighbor search and k-nearest neighbor search. Average time complexity is O(log n). If you can't store all locations in memory, check if your database supports spatial indices.

Upvotes: 1

rharrison33
rharrison33

Reputation: 1282

One solution is to write a function like the following that is generic and will allow for cutstomization:

Location[] findLocationsWithinDist(Location L1, Integer dist, LocationsList locations){
    LocationList results;
    foreach(location : locations){
        if(dist(L1, location) <= dist)
            results.add(location);
    }
    return results;
}

You could have a data structure that stores each location with a list of locations within a certain range. Then, you would need to update this data structure everytime you added a new location. That seems like a separate problem though.

Upvotes: 0

tvanfosson
tvanfosson

Reputation: 532445

You don't really give us a lot of information about the table structure so it's hard to give you an exact answer. However, let's say the target zip code is supplied to the query as parameter, P1. Further let's say table T has id, name, and zip fields. To find all locations within 100 miles we can use

select id, name, zip, distance(zip,P1) as distance
from T
where distance(zip,P1) <= 100

For a top 50 query

select top 50 id, name, zip, distance(zip,P1) as distance
from T
order by distance(zip,P1)

A better solution would be to calculate the latitude and longitude of each location and store it in the database. You can think skip the latitude/longitude look up in your function and improve the speed dramatically. I assume that you've already got the code to calculate the great circle distance in your existing function.

Upvotes: 0

Xonar
Xonar

Reputation: 1326

You would have to loop through them and simply throw out all the locations that are further away that 100miles and it will be O(N)

SELECT Location FROM Table WHERE (POWER(Location.X-Selected.X,2) + POWER(Location.Y-Selected.Y,2)) < POWER(Distance,2)

Location would be the location entry. Selected would be your selected city just replace it's X and Y with the respective location.

My SQL is a bit rusty so shout if there's a mistake and I'll fix it.

Upvotes: 0

Related Questions