如何以固定坐标A,B为中心，1km为半径内的用户按照距离P远近进行排序？

Question

现在有用户P其坐标为：（116.63255，39.90467），现数据库有40W用户坐标不固定。

业务需求为：以P为圆心，1km为半径内所有用户按照距离由近到远进行数据排序，MYSQL或者PHP或者MYSQL存储过程如何写（如果有）？

---

其P的数据库信息为：

uid 用户UID

longitude 经度

latitude 纬度

以P为圆心的四个坐标可以如下换算出来，

    define("EARTH_RADIUS",6378.137);
    /**
     * 获取距离四个坐标
     * @param $lon
     * @param $lat
     * @param int $distance 默认1KM的距离
     * @return array
     */
    public function getDistance($lon,$lat,$distance = 1){
        $range = 180 / pi() * $distance / EARTH_RADIUS;
        $lngR = $range / cos($lat * pi() / 180);
        $data = array();
        $data["maxLat"] = $lat + $range;
        $data["minLat"] = $lat - $range;
        $data["maxLng"] = $lon + $lngR ;//最大经度
        $data["minLng"] = $lon - $lngR ;//最小经度
        return $data;
    }

得出以上四个点坐标后，Mysql可以这样写：

"SELECT m.uid,m.username,m.email,m.regip,m.regdate,m.lastloginip,m.lastlogtime,f.weight,f.height,f.sex,f.qq,f.weixin,f.weibo,f.birthyear,f.birthmonth,f.birthday,f.blood,f.capricorn,f.birthprovince,f.birthcity,f.birthtown,f.resideprovince,f.residecity,f.residetown,f.friend,f.feedfriend,f.description,f.friendnum,f.follownum,f.device,f.edition,f.longitude,f.latitude FROM ".$_SGLOBAL["common_server"]->tname("member")." AS m LEFT JOIN ".$_SGLOBAL["common_server"]->tname("memberfield")." AS f ON m.uid=f.uid WHERE (f.longitude < '{$distance["maxLng"]}' AND  f.longitude > '{$distance["minLng"]}') AND (f.latitude < '{$distance["maxLat"]}' AND f.latitude > '{$distance["minLat"]}') AND 1 DESC LIMIT {$offset},20"

可，以上SQL，却无法进行距离排序，求解决办法！

---

补充说明一下，如何换算 P 与 P1之间的距离：

    /**
     * 获取两个坐标之间的距离
     * @param $lat1
     * @param $lng1
     * @param $lat2
     * @param $lng2
     * @param int $len_type
     * @param int $decimal
     * @return float
     */
    public function GetDistanceToM($lat1, $lng1, $lat2, $lng2, $len_type = 1, $decimal = 2){
        $radLat1 = $lat1 * PI ()/ 180.0;
        $radLat2 = $lat2 * PI() / 180.0;
        $a = $radLat1 - $radLat2;
        $b = ($lng1 * PI() / 180.0) - ($lng2 * PI() / 180.0);
        $s = 2 * asin(sqrt(pow(sin($a/2),2) + cos($radLat1) * cos($radLat2) * pow(sin($b/2),2)));
        $s = $s * EARTH_RADIUS;
        $s = round($s * 1000);
        if ($len_type > 1){
            $s = $s / 1000;
        }
        return round($s, $decimal);
    }

以上的方法是换算距离的，但是却无法在mysql中使用。

Answer 1

楼主可以看看这篇文章： http://www.infoq.com/cn/articles/depth-study-of-Symfony2
他列举了这类问题的几种解决方案，最后推荐的是mongodb，这也是LBS常见的解决方案之一

这两天我正好也在做这类服务，因为我的数据比较少，所以使用的是mysql partial index的方法。

set @x1 = 31.292491624635;
set @y1 = 121.50865016331;
set @r0 = 10;
select *, AsText(pos), X(pos), Y(pos), 
6378 * 2 *ASIN(SQRT( 
POWER(SIN((@orig_lat - abs(X(pos))) * pi()/180 / 2),2) + 
COS(@orig_lat * pi()/180 ) * COS(abs(X(pos)) *  pi()/180) * POWER(SIN((@orig_lon - Y(pos)) *  pi()/180 / 2), 2)
)) as distance
from user_posistion 
WHERE   MBRContains(LineString(Point(@x1 + @r0 / ( 111.1 / COS(RADIANS(@y1))), @y1 + @r0 / 111.1), Point(@x1 - @r0 / ( 111.1 / COS(RADIANS(@y1))), @y1 - @r0 / 111.1)), pos)
order by distance asc

其中@x1,@y1是坐标， @r0是搜索的半径km，pos是point类型的字段
先根据spatial索引检索出半径范围内的所有点，然后计算距离，最后排序

因为我的数据少，性能方面可以满足要求

Answer 2

有个东西叫GEOHASH。。速度极快，目前公司里这种需求都是用这种方法做的

Answer 3

想一步到位很难的哦，我的做法是先用mysql过滤出半径内的符合条件的数据，做法和你那个差不多。然后再用php算出每个点和指定坐标的距离，然后将这些数据进行排序，一般经过mysql筛选后的数据量就不是很大了，用php排序问题应该不大。

Answer 4

这个属于 GIS，最好还是用数据库扩展来做．例如：http://blog.csdn.net/historyasamirror/article/details/6528527 这里的做法． 硬要用 MySQL 的常规用法来解决就必须将计算两点距离的方法写成存储过程：

select uid from tableName order by distance(l1, n1, tableName.longitude, tableName.latitude) asc limit 10;

其中　distance 是一个算两点距离的存储过程．一般情况下不推荐这么做，因为这种运算会影响数据库性能。

Answer 5

精确计算太过于复杂，php+mysql有难度。

现实中解决实际问题可以将模型简化,按距离排序可以这样实现：

"SELECT * ,longitude*longitude + latitude*latitude as dis FROM table WHERE dis>'$x'  order by dis DESC LIMIT {$offset},20"

但是效率比较低下。

Answer 6

这不是k nearest neighbor的eager version么…

k-d tree搜这个关键词