Get results that fall within marker radiuses from database

Question

Update 16th November 2012

I would like to raise this question again, offering with a new bounty for a solid, good solution. It seems that only the solution (shubhansh's answer) does not effectively work now. I will explain why.

Firstly, this is the live map I have with radiuses and people, the radiuses are in red and the people are in blue.

As you can see, there are two people in this map with eight radiuses, basically I am getting only the person which is Person A, but I am not getting Person B, I'm guessing that the SQL is not correctly picking it up which I need it to be precise and accurate from the person's radius and the marker radiuses.

It looks like what is picked up are are inside the radiuses, not those who overlap a radius, I need it to be able to pick up any results for any radiuses that overlap each other.

I am looking for a precise and accurate SQL than shubhansh's answer. You may read below to read how exactly I need the query to act and pick up accurate people.

The data, PEOPLE:

+-----------+-----------+--------+
| latitude  | longitude | radius |
+-----------+-----------+--------+
| 51.517395 | -0.053129 | 5.6    |
| 51.506607 | -0.116129 | 0.7    |
+-----------+-----------+--------+

Please note that radius is in kilometers.

+-----------+-----------+-----+
| latitude  | longitude | km  |
+-----------+-----------+-----+
| 51.502117 | -0.103340 | 0.3 |
| 51.498913 | -0.120850 | 0.7 |
| 51.496078 | -0.108919 | 0.7 |
| 51.496506 | -0.095873 | 0.7 |
| 51.503399 | -0.090723 | 0.7 |
| 51.508049 | -0.100336 | 0.7 |
| 51.508797 | -0.112610 | 0.7 |
| 51.505535 | -0.125227 | 0.7 |
| 51.502331 | -0.108061 | 0.7 |
+-----------+-----------+-----+

The current SQL I use:

SELECT ppl.latitude,
       ppl.longitude,
       ppl.radius
FROM 
(
    people ppl
),
(
    SELECT latitude, longitude 
    FROM radiuses
) AS radius
WHERE (POW((ppl.longitude - radius.longitude) * 111.12 * COS(ppl.latitude), 2) + POW((ppl.longitude - radius.longitude) * 111.12, 2)) <= 4
GROUP BY ppl.id

The data for MySQL which you can use to test your query,

INSERT INTO radiuses (id, latitude, longitude, km) VALUES ('1', '51.502117', '-0.103340', '0.3'), ('2', '51.498913', '-0.120850', '0.7'), ('3', '51.496078', '-0.108919', '0.7'), ('4', '51.496506', '-0.095873', '0.7'), ('5', '51.503399', '-0.090723', '0.7'), ('6', '51.508049', '-0.100336', '0.7'), ('7', '51.508797', '-0.112610', '0.7'), ('8', '51.505535', '-0.125227', '0.7'), ('9', '51.502331', '-0.108061', '0.7');

INSERT INTO people (id, latitude, longitude, radius) VALUES ('1', '51.517395', '-0.053129', '5.6'), ('2', '51.506607', '-0.116129', '0.7');

---

Old summary

Note: all the latitudes and longitudes are just randomly made.

I have a map applet which a user can place his radius of a lat/lng location, with a 1km radius.

Now, there is another user that can put his radiuses, at any location on the map, each with 1km radius (same as the user above).

Like this User A is red and User B is blue.

Basically User A stores his radiuses in a table that looks like this:

+-----------+---------+-----------+-----------+
| radius_id | user_id | latitude  | longitude |
+-----------+---------+-----------+-----------+
|         1 |       1 | 81.802117 | -1.110035 |
|         2 |       1 | 81.798272 | -1.144196 |
|         3 |       1 | 81.726782 | -1.135919 |
+-----------+---------+-----------+-----------+

And User B stores his radius in another table that looks like this - (note: they can only store 1 coordinates per account):

+---------+-----------+-----------+
| user_id | latitude  | longitude |
+---------+-----------+-----------+
|       6 | 81.444126 | -1.244910 |
+---------+-----------+-----------+

I want to be able to pick up those users that fall within the defined radiuses, even if the radius circles are touching, in the map picture. Only marker C would be able to pick up the single radius, when A and B do not.

I'm sure this is possible, but I do not know how to come up with this kind of system in MySQL.

I found this on the Google Developers site it's close but not just what it performs I need.

• Creating a Store Locator with PHP, MySQL & Google Maps

EDIT: I have found a better one, this is very close, but still not what I am looking for, since it uses 1 bound of latitude and longitude coordinates when I have multiple in a table.

• Select points from a database by latitude/longitude within a bounding circle

Answer 1

For solving this you need to understand equation of circle, which is something like this For any point (x,y) to fall within circle with center (x1, y1) and radius r units is

(x-x1)^2 + (y - y1)^2 <= r^2

where a^b = a to the power b

Here in your case User B's (latitude, longitude) are the center of circle, User A's (latitude, longitude) are the points (x,y) and radius = 2kms.

But basic problem is of changing degrees of latitudes to longitudes, so here is solution, 1 degree = 111.12 km. So to keep units same on both side of equation, we will convert it to Kms

So our final equation becomes:

((x-x1)*111.12)^2 + ((y-y1)*111.12)^2 = 4      (=2^2) 

SQL statement for the same should look something like this

SELECT A.user_id, A.radius_id, A.latitude, A.logitude
FROM UserA AS A, 
     (SELECT user_id, latitude, longitude 
       FROM UserB 
       WHERE user_id = 8) AS B
WHERE (POW((A.latitude-B.latitude)*111.12, 2) + POW((A.longitude - B.longitude)*111.12, 2)) <= 4
/* **Edit** Here I have used (A.longitude - B.longitude)*111.12, for more accurate results one can replace it with (A.longitude - B.longitude)*111.12*cos(A.latitude)) or (A.longitude - B.longitude)*111.12*cos(B.latitude)) 

And, as i have suggested in the comments that first filter some records based on approximation, so whether one uses A.latitude or B.latitude it will not make much difference */

Hope this will help...

Answer 2

At the heart of your problem is the question "how do I know if two circles overlap". The answer to that is "if the distance between their centers is less than the sum of their radii". So what you're looking for is how to determine the distance between two points.

The other answer is treating latitude and longitude as if they comprise a Cartesian plane. which they do not (longitude tends towards zero as you approach the poles from the equator). Now, as an approximation, it may work just fine for your solution, depending on the accuracy needed by your solution. On the other hand, if you need this to be very accurate, you need the Haversine formula. There's a great description of how to implement it in MySQL here:

http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

From slide 7 of that presentation, you have the following formula:

3956*2*ASIN(SQRT(POWER(SIN((orig.lat-dest.lat)*pi()/180/2),2)+
    COS(orig.lat*pi()/180)*COS(dest.lat*pi()/180)*
    POWER(SIN((orig.lon-dest.lon)*pi()/180/2),2)))

Note that the first number is the mean radius of the earth in miles; change that to 6371 for kilometers.

How you use this calculated distance is going to depend on details not included in your post, such as the number of points you're dealing with, the geographic dispersion, any performance requirements, and whether or not the data is static or being continually updated.

I mention these things because performance is going to be an issue, especially if you have any significant amount of data and/or it's being continuously updated (like user's locations based on their phone's GPS data).

One way you can help with the performance issue is use squares instead of circles, and use the approximation of one degree = 111.12 km. That way you can automatically cull out any points that are obviously far away from one another. Then you're left just calculating the Haversine formula only for the handful of points that fall within the area of interest.

I hope this is helpful in pointing you in the right direction.

Answer 3

The essential point of your geometry is that two circles overlap if the distance between their centers is less than the sum of their radii. Since we're doing a comparison, we can use the square of the distance, since that avoids a square root operation. In the original, each radius is fixed at 1, the sum of the two radii is 2, and the square of the sum is 4.

There's a big difference between the original question and the new question. In the first you've got circles of fixed radius and the second you've got circles of varying radius. The constant 4 in the comparison expression [...distance^2...] <= 4 needs to be replaced, since that's an artifact of the fixed radius of the original. To implement this, add the km field into the query. And as you should check, you weren't using ppl.radius in the WHERE filter, so it's hardly surprising that varying that value didn't change your query results.

SELECT ppl.latitude, ppl.longitude, ppl.radius
FROM 
  ( people ppl ),
  ( SELECT latitude, longitude, km FROM radiuses ) AS B
WHERE [...distance^2...] <= POW( ppl.radius + B.km, 2)

I should say that this question took far longer to understand than it should have, because you're calling the entity-that's-not-a-person a "radius", when really you've got a property that ought to be called 'radius' on two different entities. So name that other entity something descriptive.