Oracle spatial search within distance

Question

I have the following table Cities:

ID(int),City(char),latitude(float),longitude(float).

Now based on a user`s longitude(ex:44.8) and latitude(ex:46.3) I want to search for all the cities near him within 100 miles/KM.

I have found some examples but don`t know how to adapt them to my case

select *
from GEO.Cities a
where SDO_WITHIN_DISTANCE([I don`t know],
MDSYS.SDO_GEOMETRY(2001, 8307, MDSYS.SDO_POINT_TYPE(44.8,46.3, NULL) ,NULL, NULL), 
'distance = 1000') = 'TRUE';

Any help would be appreciated.

P.S: If it is possible to have the distance and to be sorted

P.P.S: I want to do it in this way due to performance issues, I have done this in this way http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL but it takes too long...

Answer 1

You have a pretty good reference there for mySQL distance search.

Forget about the Oracle Spatial stuff. Too much code, too much complexity, not enough value-add.

Here's a query that will do the trick. This uses distances in statute miles. EDIT This fixes the bug mentioned by mdarwin, at the cost of divide-checking if you try to use it for a location at the north or south pole.

  SELECT id, city, LATITUDE, LONGITUDE, distance
    FROM
  (
    SELECT id, 
           city, 
           LATITUDE, LONGITUDE,
           (3959 * ACOS(COS(RADIANS(LATITUDE)) 
                 * COS(RADIANS(mylat)) 
                 * COS(RADIANS(LONGITUDE) - RADIANS(mylng)) 
                 + SIN(RADIANS(LATITUDE)) 
                 * SIN(RADIANS(mylat)) 
               ))
           AS distance,
           b.mydst
      FROM Cities
      JOIN (
        SELECT :LAT AS mylat,
               :LONG AS mylng,
               :RADIUS_LIMIT AS mydst
          FROM DUAL
      )b ON (1 = 1)
     WHERE LATITUDE >=  mylat -(mydst/69)
       AND LATITUDE <=  mylat +(mydst/69)
       AND LONGITUDE >= mylng -(mydst/(69 * COS(RADIANS(mylat))))
       AND LONGITUDE <= mylng +(mydst/(69 * COS(RADIANS(mylat))))
  )a
   WHERE distance <= mydst
   ORDER BY distance

If you're working in kilometers, change mydst/69 to mydst/111.045, and change 3959 to 6371.4. (1/69 converts miles to degrees; 3959 is a value for the radius of the planet.)

Now, you'll probably be tempted to use this large query as a "magic black box." Don't do it! It's not very hard to understand, and if you do understand it you'll be able to do a better job. Here's what's going on.

This clause is the heart of what makes the query fast. It searches your Cities table for nearby cities to the point you specified.

     WHERE LATITUDE >=  mylat -(mydst/69)
       AND LATITUDE <=  mylat +(mydst/69)
       AND LONGITUDE >= mylng -(mydst/(69 * COS(RADIANS(mylat))))
       AND LONGITUDE <= mylng +(mydst/(69 * COS(RADIANS(mylat))))

For it to work, you definitely need an index on your LATITUDE column. An index on your LONGITUDE column will also help a bit. It does an approximate search, looking for rows that are within a quasi-rectangular patch on the surface of the earth near your point. It selects too many cities, but not far too many.

This clause here lets you eliminate the extra cities from your result set:

   WHERE distance <= mydst

This clause is the haversine formula which calculates the great-circle distance between each city and your point.

           (3959 * ACOS(COS(RADIANS(LATITUDE)) 
                 * COS(RADIANS(mylat)) 
                 * COS(RADIANS(LONGITUDE) - RADIANS(mylng)) 
                 + SIN(RADIANS(LATITUDE)) 
                 * SIN(RADIANS(mylat)) 

This clause lets you enter your point, and your radius-limit, just once as bound variables to your query. It's helpful because the various formulas use those variables multiple times.

        SELECT :LAT AS mylat,
               :LONG AS mylng,
               :RADIUS_LIMIT AS mydst
          FROM DUAL

The rest of the query simply organizes things so you select and order by distance.

Here is a more complete explanation: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

Answer 2

If you decide to make your own formula, I think this function could be very useful for oracle users and could be modified slightly for other DB's. This is the flat earth formula which is a lot less computationally expensive than the more accurate haversine formula.

CREATE OR REPLACE Function CIC3.F_FLATEARTHRAD
   ( latoriginrad IN number,
     longoriginrad IN number,
     latdestrad IN number,
     longdestrad IN number)

RETURN  number IS
   a number;
   b number;
   c number;
   u number;
   v number;

   HalfPi number:=1.5707963;
   R number:=3956;
BEGIN
   if latoriginrad is null or latdestrad is null or 
   longdestrad  is null or  longoriginrad is null then
         return null;
   end if; 
   a := HalfPi - latoriginrad;
   b := HalfPi - latdestrad;
   u := a * a + b * b;
   v := - 2 * a * b * cos(longdestrad - longoriginrad);
   c := sqrt(abs(u + v));

   return R * c;
END;

Then your query becomes

select * from GEO.Cities a
where F_FLATEARTHRAD(44.8*0.0174,46.3*0.0174,
               latitude_radians,longitude_radians)<1000 

The 0.0174 factor is needed because the formula uses radians not degrees. So you would need to either store radians (maybe with a trigger). Or you would need to modify the formula to accept degrees. For query purposes you may be querying thousands of records and even a single extra multiplication can make a difference in response time. In our case some queries compare distances between two tables 4k records on one and 200k so we have in the order of billions of function calls.

Below is the haversine equivalent for people not needing to worry about time.

CREATE OR REPLACE Function CIC3.F_HAVERSINE 
  ( latorigin IN number,
    longorigin IN number,
    latdest IN number,
    longdest IN number)

  RETURN  number IS
    v_longoriginrad number;
    v_latoriginrad number;
    v_longdestrad number;
    v_latdestrad number;
    v_difflat number;
    v_difflong number;
    a number;
    c number;
    d number;
    z number;
    x number;
    e number;
    f number;
    g number;
    h number;
    i number;
    j number;
    k number;
    l number;
    m number;
    n number;
    o number;
    p number;
    q number;
    y number;
BEGIN
    z := .017453293;
    x := 3956;
    y := 57.295780;
    v_longoriginrad:=longorigin*z;
    v_latoriginrad:=latorigin*z;
    v_longdestrad:=longdest*z;
    v_latdestrad:=latdest*z;
    v_difflong:=v_longdestrad-v_longoriginrad;
    v_difflat:=v_latdestrad-v_latoriginrad;

    j:=(v_difflat/2);
    k:=sin(j);
    l:=power(k,2);

    m:=cos(v_latoriginrad);

    n:=cos(v_latdestrad);

    o:=v_difflong/2;
    p:=sin(o);
    q:=power(p,2);

    a:=l+m*n*q;

    c := 2 * asin(sqrt(a));

    d := x * c;

    return d;
END;