CODEWITHSUNDEEP
javac#sql-serverspringcoordinates
SirKometa
SirKometa

Reputation: 1887

Finding points in a distance range using code (having set of latitude/longitude stored in database)

I do have a relatively big application with a database of POIs (in this case it means that there are two sets, once contains around 40k points and another one contains around 400k).

It is a web application where you can view details of a given point and see other points around, let's say in the range of 25km.

So far I have had it solved with the MS SQL Stored Procedure. It has two arguments, latitude and longitude given as floats and returns nearest points (lat/lng are also stored as floats, not a geography type in MSSQL DB).

I would like avoid using stored procedures though. Feel like business logic should stay in the code (at least most of it).

Now when I am updating the project (which will most likely end up with a transition from ASP WebForms to Spring MVC), I would like to stop using my stored procedure.

Is there any good/easy way, which will not be an overkill, to do it?

The only thing I can come up with (code based) is retrieving all the points from DB and do a naive iteration through the collection, calculating distance between given point and current point from collection.

Something like

Point givenPoint = new Point(lat,lng);
List<Point> allPoints = repo.findAll();
List<Point> pointsInRange = new List<Point>();
for(Point p : allPoints){
    if(givenPoint.distanceTo(p) < 25)
         pointsInRange.add(p);
}

Looks like an overkill though.

Upvotes: 0

Views: 1009

Answers (1)

Elliveny
Elliveny

Reputation: 2203

See Fast algorithm to find the x closest points to a given point on a plane where a few options are discussed, including my hint at a KD-Tree being an appropriate data structure.

Also, this might give you some other options: Finding nearest point in an efficient way

And this is a useful discussion of the wider subject: http://en.wikipedia.org/wiki/Nearest_neighbor_search

Upvotes: 1

Related Questions