What is the best approach to find all addresses that are in a specific distance to the selected point

Question

I am developing an application that is supposed to show addresses that are in a specific distance of a location. I know how to find the distance between two points, but the problem is I am not sure what would be the best approach in terms of performance.

One way is to retrieve all addresses and check them one by one toward the selected address in back-end but is there any way to minimize the number of items that I retrieve from database, rather than using the memory? whats the best approach to do it and how?

Imagine I have 300,000 records do I have to retrieve them all and calculate their distance to the selected point? As James suggested I can have the records in different regions and calculate the distance, then which method would be good to follow,distance calculation through query or Java?

  public class Address{
    long Id;
    Double latitude;
    Double longitude;
    ..
  }

Calculation

public static double distFrom(double lat1, double lng1, double lat2, double lng2) {
  double earthRadius = 3958.75;
  double dLat = Math.toRadians(lat2-lat1);
  double dLng = Math.toRadians(lng2-lng1);
  double sindLat = Math.sin(dLat / 2);
  double sindLng = Math.sin(dLng / 2);
  double a = Math.pow(sindLat, 2) + Math.pow(sindLng, 2)
        * Math.cos(Math.toRadians(lat1)) *     Math.cos(Math.toRadians(lat2));
  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
  double dist = earthRadius * c;

  return dist;
}

This question and this one offer methods to calculate distance through mysql but which way is better Java or mysql I am quite confused.

Answer 1

I am using hibernate and do this in this way:

public List<Tour> searchTours(double lat, double lon, double distance) {

    Session session = getSession();

    Criteria criteria = session.createCriteria(Tour.class, "tour");

    //
    // 1 Grad lat = 111 km
    // 1 grad lon = cos(lat) * 111
    //
    final double KM_IN_ONE_LAT = 111.0;

    double t1 = distance / Math.abs(Math.cos(Math.toRadians(lat)) * KM_IN_ONE_LAT);
    double t2 = distance / KM_IN_ONE_LAT;

    double lonA = lon - t1;
    double lonB = lon + t1;

    double latA = lat - t2;
    double latB = lat + t2;

    Criterion c1 = Restrictions.between("longitude", lonA, lonB);
    Criterion c2 = Restrictions.between("latitude", latA, latB);

    criteria.add(c1);
    criteria.add(c2);

    criteria.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

    return criteria.list();
}

Check this paper for more information: Geo (proximity) Search with MySQL

Answer 2

When I have implemented this in MySQL (for storing places on an oblate sphere, which is basically what earth is (I assume you're talking about earth!)), I have stored as much pre-calculated information as possible in the database. So, for a row that stores latitude and longitude, I also calculate at insertion time the following fields:

• radiansLongitude (Math.toRadians(longitude))
• sinRadiansLatitude (Math.sin(Math.toRadians(latitude))
• cosRadiansLatitude (Math.cos(Math.toRadians(latitude))

Then when I search for the places that are within X units of the latitude/longitude in question, my prepared statement is as follows:

from Location l where
    acos(
        sin(:latitude) * sinRadiansLatitude + 
        cos(:latitude) * cosRadiansLatitude * 
        cos(radiansLongitude - :longitude) 
        ) * YYYY < :distance
    and l.latitude>:minimumSearchLatitude
    and l.latitude<:maximumSearchLatitude 
    and l.longitude>:minimumSearchLongitude 
    and l.longitude<:maximumSearchLongitude 
    order by acos(
                sin(:latitude) * sinRadiansLatitude + 
                cos(:latitude) * cosRadiansLatitude * 
                cos(radiansLongitude - :longitude)  
        ) * YYYY asc

Where YYYY = 3965 gives you distances in miles or YYYY = 6367 can be used for distances in km.

Finally, I have used the maximumSearchLatitude / maximumSearchLongitude / minimumSearchLongitude / maximumSearchLongitude parameters to exclude the majority of points from the resultset before the database has to perform any calculations. You may or may not need this. If you do use this, it'll be up to you what values you choose for these parameters, as it will depend on what you're searching.

Obviously judicious applications of indexes in the database will be necessary.

The benefit of using this approach is that the information which never changes but is needed every time is only calculated once, whereas calculating the values of radiansLongitude, sinRadiansLatitude, cosRadiansLatitude for every row every time you perform a search is going to get very expensive very fast.

The other option is to use a geospatial index, which means that all of this is taken handled for you by the database. I don't know how well Hibernate integrates with that though.

Disclaimer: it's a long time since I looked at this, and I'm not a GIS expert!