Given a latitude and longitude, find users interested in that position

Question

Given a table,

+-----+---------+---------+---------+---------+---------+
| user| min_lat | max_lat | min_lng | max_lng |
+-----+---------+---------+---------+---------+---------+
| a   |    46   |     407 |       6 |     367 | 
| b   |   226   |     227 |     186 |     188 |

And a Point(x, y) Find users where the point is within the min and max latitude and longitude ranges of users (where min and max long and lat = current position minus or plus radius).

Minimum values can be less than 0 and maximum values can be greater than 360, the query needs to take these into account.

E.g. filtering using Point(7,5) should also return user A, as 367-360=7.

Not sure if I'm getting this right, but hopefully somebody can give me some insight.

Answer 1

To answer one part of your query, if you are saying that 367 and 7 are the same, I assume equally that 727 is also.

Therefore, you want to use the modulus of 360. E.g. the remainder of dividing by 360.

e.g. (where % is the C# and C++ syntax, you'll probably find an SQL way to do this)

7 % 360 = 7
367 % 360 = 7
727 % 360 = 7

Looks like something like SELECT b MOD 360 from table; is the sort of thing you want.

Answer 2

I suspect there is a more elegant answer, but I think the confines of a SQL where clause make this a little more difficult.

Assumptions:

• 0 <= x < 360
• 0 <= y < 360
• max_lat - min_lat <= 361
• max_lng - min_lng <= 361

SELECT user FROM user_location WHERE  
((min_lat <  0 AND ((0 <= y AND y <= max_lat) OR (min_lat + 360 <= y AND y < 360))) OR  
 (min_lat >= 0 AND ((min_lat <= y AND y <= max_lat) OR (0 <= y AND y <= max_lat - 360))))  
AND  
((min_lng <  0 AND ((0 <= x AND x <= max_lng) OR (min_lng + 360 <= x AND x <= 360))) OR  
 (min_lng >= 0 AND ((min_lng <= x AND x <= max_lng) OR (0 <= x AND x <= max_lng - 360))))

In one dimension, if min < 0 then x must fall between 0 and max or x must fall between min + 360 and 360. Similarly if min >= 0 then x must fall between min and max, or it must fall between 0 and max - 360.

The format above is presented for clarity. If you move the addition and subtraction of 360 to the x and y parameters, the comparisons become constant and probably speed the query dramatically.

Answer 3

Use a modulo to ensure all values are between 0 and 360, and the query becomes pretty simple. Assume {pointLat} and {pointLng} are the coordinates of the point that's being filtered on.

SELECT *
FROM table
WHERE IF(min_lat < max_lat,
        MOD({pointLat}, 360) BETWEEN MOD(min_lat, 360) AND MOD(max_lat, 360)),
        MOD({pointLat}, 360) NOT BETWEEN MOD(min_lat, 360) AND MOD(max_lat, 360)))
    AND IF(min_lng < max_lng,
        MOD({pointLng}, 360) BETWEEN MOD(min_lng, 360) AND MOD(max_lng, 360)),
        MOD({pointLng}, 360) NOT BETWEEN MOD(min_lng, 360) AND MOD(max_lng, 360)));

While this would work, I strongly recommend performing the MOD calculations outside the SQL query or adding extra columns with normalized values. Using the MOD function as in this code would prevent the query from taking advantage of any indexes on those columns.

Answer 4

I recommend limiting the latitude & longitude values stored in the table to the range [0, 360]. Create triggers before insert and update to enforce the mod 360 equivalency and, if max-min > 360, set the min and max values to 0 and 360, respectively. For example:

delimiter ;;

CREATE TRIGGER normalize_inserted_ranges BEFORE INSERT 
  ON table
  FOR EACH ROW BEGIN
    IF NEW.max_lat - NEW.min_lat >= 360 THEN
        SET NEW.min_lat=0;
        SET NEW.max_lat=360;
    ELSE
        SET NEW.min_lat = NEW.min_lat % 360;
        SET NEW.max_lat = NEW.max_lat % 360;
    END IF;
    IF NEW.max_lng - NEW.min_lng >= 360 THEN
        SET NEW.min_lng=0;
        SET NEW.max_lng=360;
    ELSE
        SET NEW.min_lng = NEW.min_lng % 360;
        SET NEW.max_lng = NEW.max_lng % 360;
    END IF;
  END
;;
delimiter ;

You can then use the following query:

SELECT user FROM table
  WHERE
      IF(min_lng <= max_lng, 
         @x BETWEEN min_lng AND max_lng, 
         @x <= max_lng OR min_lng <= @x)
    AND
      IF(min_lat <= max_lat,
         @y BETWEEN min_lat AND max_lat, 
         @y <= max_lat OR min_lat <= @y)
;