20

2012 年 11 月 16 日更新

我想再次提出这个问题，提供一个新的赏金，以获得一个可靠的、好的解决方案。似乎只有解决方案（shubhansh的答案）现在不能有效地工作。我会解释为什么。

首先，这是我有半径和人的实时地图，半径在red，人在blue。

在此处输入图像描述

如您所见，two这张地图中有eight半径的人，基本上我只得到那个人Person A，但我没有得到Person B，我猜 SQL 没有正确选择它，我需要它是精确的并且根据人的半径和标记半径准确。

看起来拾取的内容在半径内，而不是与半径重叠的那些，我需要它能够拾取任何相互重叠的半径的任何结果。

我正在寻找比 shubhansh 的答案更精确和准确的 SQL。您可以阅读下面的内容，以了解我究竟需要该查询来采取行动并找到准确的人。

数据，人：

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

请注意，radius以公里为单位。

+-----------+-----------+-----+
| 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 |
+-----------+-----------+-----+

我使用的当前 SQL：

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

可用于测试查询的 MySQL 数据，

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');

老总结

注意：所有的经纬度都是随机制作的。

我有一个地图小程序，用户可以放置他的纬度/经度位置半径，半径为 1 公里。

现在，有另一个用户可以将他的半径放在地图上的任何位置，每个半径为 1 公里（与上面的用户相同）。

像这样，用户 A是红色的，用户 B是蓝色的。

在此处输入图像描述

基本上，用户 A将他的半径存储在一个如下所示的表中：

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

并且用户 B将他的半径存储在另一个看起来像这样的表中 - （注意：他们每个帐户只能存储 1 个坐标）：

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

我希望能够在地图图片中找到那些落在定义半径内的用户，即使半径圆是接触的。只有标记C能够拾取单个半径，何时A和B不。

我确信这是可能的，但我不知道如何在 MySQL 中提出这种系统。

我在 Google Developers 网站上发现它很接近，但不仅仅是我需要的性能。

编辑：我找到了一个更好的，这是非常接近的，但仍然不是我想要的，因为当我在一个表中有多个时，它使用 1 个纬度和经度坐标的界限。

4

3 回答 3

14

为了解决这个问题，您需要了解圆方程，类似于这样 对于任何点 (x,y) 落入具有中心 (x1, y1) 且半径为 r 单位的圆内是

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

where a^b = a to the power b

在您的情况下，用户 B 的（纬度，经度）是圆心，用户 A 的（纬度，经度）是点（x，y），半径 = 2kms。

但基本问题是纬度到经度的变化，所以这里是解决方案，1度= 111.12公里。因此，为了保持等式两边的单位相同，我们将其转换为 Kms

所以我们的最终方程变为：

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

相同的 SQL 语句应该看起来像这样

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 */

希望这会有所帮助...

于 2012-07-20T21:54:18.550 回答
7

您问题的核心是“我怎么知道两个圆圈是否重叠”的问题。答案是“如果它们的中心之间的距离小于它们的半径之和”。所以你要找的是如何确定两点之间的距离。

另一个答案是将纬度和经度视为构成笛卡尔平面。他们没有（当您从赤道接近两极时，经度趋于零）。现在，作为一个近似值，它可能适用于您的解决方案，具体取决于您的解决方案所需的准确性。另一方面，如果您需要非常准确，则需要 Haversine 公式。这里有一个关于如何在 MySQL 中实现它的很好的描述：

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

从该演示文稿的幻灯片 7 中，您有以下公式：

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)))

请注意，第一个数字是以英里为单位的地球平均半径；将其更改为 6371 公里。

你如何使用这个计算出的距离将取决于你的帖子中没有包含的细节，比如你正在处理的点数、地理分布、任何性能要求，以及数据是静态的还是持续更新的.

我提到这些事情是因为性能将成为一个问题，特别是如果您有大量数据和/或它正在不断更新（例如基于手机 GPS 数据的用户位置）。

您可以帮助解决性能问题的一种方法是使用正方形而不是圆形，并使用 1 度 = 111.12 公里的近似值。这样你就可以自动剔除任何明显相距很远的点。然后，您只需要为感兴趣区域内的少数点计算 Haversine 公式。

我希望这有助于为您指明正确的方向。

于 2012-07-20T23:06:02.890 回答
6

几何学的要点是，如果两个圆的中心之间的距离小于它们的半径之和，则两个圆重叠。由于我们正在进行比较，我们可以使用距离的平方，因为这样可以避免平方根运算。原来，每个半径固定为1，两个半径之和为2，和的平方为4。

原始问题和新问题之间存在很大差异。第一个你有固定半径的圆，第二个你有不同半径的圆。4比较表达式中的常量[...distance^2...] <= 4需要替换，因为这是原始固定半径的产物。要实现这一点，请将km字段添加到查询中。正如您应该检查的那样，您没有ppl.radius在 WHERE 过滤器中使用，因此改变该值不会改变您的查询结果也就不足为奇了。

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)

我应该说，这个问题的理解时间比它应该的要长得多，因为你称实体——那不是一个人为“半径”，而实际上你有一个应该被称为“的属性”半径'在两个不同的实体上。因此，将其他实体命名为描述性的。

于 2012-11-17T16:09:08.620 回答