0

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.

SirKometa
  • 1,857
  • 3
  • 16
  • 26
  • A KDTree is good for this kind of processing. Have a look at https://code.google.com/p/kd-sharp/ – Elliveny Feb 09 '15 at 15:51
  • Also, if you don't want to write your own, you can consider marshalling boost: http://www.boost.org/doc/libs/1_56_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_quickstart.html – Nicko Po Feb 11 '15 at 00:06
  • I'd rather keep it Java based. – SirKometa Feb 11 '15 at 09:23
  • In which case https://code.google.com/p/java-algorithms-implementation/ includes a KD-Tree implementation, including a nearest neighbour search – Elliveny Feb 11 '15 at 09:34

1 Answers1

1

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

Community
  • 1
  • 1
Elliveny
  • 2,159
  • 1
  • 20
  • 28