8

I'm trying to implement a very efficient check to see whether two points are within a mile of each other, or not.

My current approach is to compute the Haversine distance, and then check to see if it's less than a mile.

Efficiency matters in this case because I have to compute this yes/no flag for large record sets.

I only care whether they are within a mile - nothing else about the distance matters to me.

So, what is the most efficient way to tell whether two lat/long points are within a mile of each other?

In response to the comments, I'm doing this in SQL Server. My code is below.

CREATE FUNCTION dbo.USR_UFN_HAVERSINE_DISTANCE
(
  @LAT1 FLOAT(18)
 ,@LONG1 FLOAT(18)
 ,@LAT2 FLOAT(18)
 ,@LONG2 FLOAT(18)
 ,@UnitOfMeasure NVARCHAR(10) = 'KILOMETERS'
)
RETURNS FLOAT(18)
AS
BEGIN
  DECLARE
    @R FLOAT(8)
   ,@DLAT FLOAT(18)
   ,@DLON FLOAT(18)
   ,@A FLOAT(18)
   ,@C FLOAT(18)
   ,@D FLOAT(18)
   ;
  SET @R =
    CASE @UnitOfMeasure
      WHEN 'MILES'      THEN 3956.55 
      WHEN 'KILOMETERS' THEN 6367.45
      WHEN 'FEET'       THEN 20890584
      WHEN 'METERS'     THEN 6367450
      ELSE 6367.45  --km
    END
  SET @DLAT = RADIANS(@LAT2 - @LAT1);
  SET @DLON = RADIANS(@LONG2 - @LONG1);
  SET @A = SIN(@DLAT / 2) 
         * SIN(@DLAT / 2) 
         + COS(RADIANS(@LAT1))
         * COS(RADIANS(@LAT2)) 
         * SIN(@DLON / 2) 
         * SIN(@DLON / 2);
  SET @C = 2 * ASIN(MIN(SQRT(@A)));
  SET @D = @R * @C;
  RETURN @D;
END;
  • What has your research turned up as a possible candidate so far? – PolyGeo Mar 25 '16 at 2:12
  • 1
    Are you looking for a software solution or creating your own code? What have you tried so far? – MaryBeth Mar 25 '16 at 2:13
  • 2
    What's wrong with just checking the haversine distance? You could save a little processing time by just checking planar distance--at a mile, haversine won't make much of a difference. – Tom Mar 25 '16 at 2:15
  • 4
    could you just use geomA.STDistance(geomB) < d? – Ian Turton Mar 25 '16 at 10:45
  • 2
    The "planar distance" check suggested by @Tom could easily be misinterpreted: to work correctly, it needs careful interpretation. One is the following. Assuming you never have to compare points across the 180 degree meridian or the poles, you could apply the Pythagorean formula to the coordinates (lat1, cos(lat1)*lon1), (lat2, cos(lat2)*lon2). In other words, comparing (lat1-lat2)^2 + (cos(lat1)*lon1-cos(lat2)*lon2)^2 to 1/69^2 (all in degrees) tells you whether the two points are separated by a mile (to an accuracy of a fraction of a percent). Whether this is faster than Haversine is unclear. – whuber Mar 25 '16 at 21:09
2

Try this method-may not be the best but could limit your search space to a few and thus help you speeding up the process.

  1. Create half mile buffers around every point
  2. Dissolve the resulting buffers -ensure there are no multipolygons
  3. Any point lying outside this polygon is now excluded from the search space

Make sure you have built spatial indices and verify if this procedure has improved your query response time.You could also refine the approach by building near table(ESRI ArcGIS has a tool) with 1 mile as criteria.

  • buffers need to have a one mile radius, don't they? – radouxju Nov 5 '16 at 21:48
  • @radouxju, two 1/2 miles from each point is 1 mile distance. – addcolor Nov 7 '16 at 5:41
  • 1
    I don't get it. Either you want to create a polygon layer based on a predefined set of points, then use this polygon with a "point in polygons" algorithm to find out if new points are within one mile (then you need to compute one-mile-radius buffer... Or directly work with all points, with half mile buffers, dissolve and then select the isolated buffers based on area (that you need to compute). Note that 1) creating true 1-mile buffers is quite expensive 2) dissolve is quite expensive. Only option 1 makes sense to me, if you reuse the polygons several times. – radouxju Nov 7 '16 at 6:56
2

If you work at a global extent, you can avoid computing a lot of sin and cos by simple straightforward testing:

The first test to screen out points before computing haversine is to exclude point where @DLAT > 0.015 degrees (could be more precise, but I prefer safety).

In a second step, you can also do this with @DLON in a given latitude range with a conservative value (e.g. between -60 and 60 degrees, exclude @DLON > 0.03 (=0.015/cos(60)).

Because 1 miles is quite small, you will only rarely need to compute Haversine with these two rules (except if you work on polar areas), and you could replace Haversine with Pythagorean (2 cosines vs 2 sines and 2 cosines with Haversine) as mentioned by @whuber.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.