Given two lat/longs, how can I tell if they are within 1 mile of each other?

Question

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

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

Because of that narrow focus, I am not looking for a general purpose "how far apart are these points" function.

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.

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

I'm doing this check in T-SQL, not that it matters much. My current haversine computation 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;

Possible duplicate of [Fastest Way to Find Distance Between Two Lat/Long Points](http://stackoverflow.com/questions/1006654/fastest-way-to-find-distance-between-two-lat-long-points) — Ken Y-N, Mar 25 '16 at 02:00
@KenY-N Thanks for pointing me there. I already have a general purpose function to get the distance between two points. Since in this case I only care if the distance is within a mile or not, I am hoping there is a faster way without having to actually compute the full distance. I've edited the question to try and make this distinction clear. — JosephStyons, Mar 25 '16 at 02:06
Check the second answer on that linked question? Seems to be getting towards what you want... — Dan Field, Mar 25 '16 at 02:18
What games will do is first check for x < 1 mile and y < 1 mile before running the actual calc. Basically throw it our early. — paparazzo, Mar 25 '16 at 03:43
Obligatory caution: are you sure it's this code that's your bottleneck and that it's too slow for your requirements? I've never seen a real-world SQL query that was too slow just because of scalar math. — solublefish, Mar 26 '16 at 02:27
@solublefish great point, and frankly no, it's not. This is one of many calculations, some of which involve actual database operations. But I'm going through it with a fine toothed comb to try and squeeze it for every bit of performance I can. I'm focused on areas that my profiling shows as the real bottleneck. But this is one that I "feel" could be better. — JosephStyons, Mar 26 '16 at 04:32
1° of latitude is about 69 miles, so if `Abs( @Lat1 - @Lat2 ) > 1.0 / 69.0` then the distance will be at least one mile. 1° of longitude varies depending on the latitude, e.g. about 50 miles at 45° latitude. Depending on your data it might be worth checking, e.g. `Abs( @Lat1 ) <= 45 and Abs( @Lat2 ) <= 45 and Abs( @Long1 - @Long2 ) >= 1.0 / 50.0` then it will be at least one mile. You could use several latitudes with precalculated longitudinal distances depending on the distribution of latitudes within your data. (Apologies for my earlier sleep-deprived comments.) — HABO, Mar 26 '16 at 18:42
@HABO that's exactly the kind of hack I was thinking of - something that avoided calculating the distance altogether, and just used something that 'falls out' of the data I have on hand. I'll try this out and see if it works. I'm sure it (or some variation) will. — JosephStyons, Mar 28 '16 at 13:31

Vincent · Answer 1 · 2016-03-25T02:38:45.733

1

DECLARE 
    @pt1 geography,
    @pt2 geography;

    SET @pt1 = geography::Point(45.65100, -120.34900, 4326);
    SET @pt2 = geography::Point(44.65100, -120.37654, 4326);

    SELECT @pt1.STDistance(@pt2);

-The return value is in meters though you can specify the return by changing the SRID.

-The list of SRID's are available here

 Select * from sys.spatial_reference_systems

edited Mar 25 '16 at 02:38

answered Mar 25 '16 at 02:30

Vincent

842
7
13

score 1 · Accepted Answer · answered Mar 25 '16 at 03:55

Since you specify that you need to run this over large data sets, I'd suggest a table-valued function. Better if you can pre-compute the geography points, but this does it all inline.

create function dbo.fn_areWithinOneMile(@long1 float, @lat1 float, @long2 float, @lat2 float)
returns table
as
return

    select cast(
        case when 
            geography::Point(@lat1, @long1, 4236).STDistance(geography::Point(@lat2, @long2, 4236)) > 1609.34 then 0 
            else 1 
        end as bit) as [withinOneMile?]

go

with cte as (select * from (values
    (42, 42),
    (43, 43),
    (44, 44)
    ) as x(lat, long)
), j as (
    select long, lat, lag(long, 1) over (order by lat) as long2, lag(lat, 1) over (order by lat) as lat2
    from cte
)
select *
from j
cross apply dbo.fn_areWithinOneMile(long, lat, long2, lat2) as o
where long2 is not null;

Given two lat/longs, how can I tell if they are within 1 mile of each other?

2 Answers2