MySQL空间数据库–查询点到多点间的最短路径

当SNS产品加入LBS的技术将会让移动互联网领域更加丰富多彩，例如：大众点评，街旁，盛大切客 这些运行在智能手机端的应用，当用户拿出手机就可以根据你当前的所在地向你推荐一些有用的信息，例如：附近的美食，商铺，周边生活信息，等。 攻城师们，你有没有

当SNS产品加入LBS的技术将会让移动互联网领域更加丰富多彩，例如：大众点评，街旁，盛大切客 这些运行在智能手机端的应用，当用户拿出手机就可以根据你当前的所在地向你推荐一些有用的信息，例如：附近的美食，商铺，周边生活信息，等。

攻城师们，你有没有想过这些应用背后的技术实现呢？手机端获得当前的坐标后是怎么进行计算和查询返回附件的结果呢？

用Java程序可以实现Dijkstra算法获得点与多点之间最短路径的计算结果，但是我个人认为是一种暴力的方法，开发的简化程度和计算的执行效率不会非常高。
参考资料：http://baike.baidu.com/view/7839.htm

接着再往下想，用到数据库技术是必然，但不会把节点的坐标信息存储到数据库普通的字段中进行查询，如果和Dijkstra算法相比不会简化工作量也不会提高性能，但使用到MySQL中空间数据库的概念就会简化很多也会得到性能的提升，开源的MySQL Spatial空间索引机制就可以对点到多点之间的距离计算，类似的Spatial Database还有，PostGIS，SpatiaLite。

我的废话：
在android手机上获得当前坐标后，将数据整好录入android中的SQLite数据库也可以获得当前点对多点的最短路径，也就是说在地理数据不会更新的场景下完全可以采用android手机上的数据库完成这项工作，没有必要非要利用服务器端的Spatial Database完成最短路径的计算。

MySQL空间数据几种主要类型:
– GEOMETRY Geometry是层次结构的根类。它是一种非实例化类，但具有很多属性，这些属性对由任何Geometry子类创建的所有几何值来说是共同的。
– POINT 代表坐标空间中单个位置的几何类，他的属性包含 X-坐标值，Y-坐标值。
– LINESTRING 具有线段的坐标，由每个连续的点对(两点)定义。如果仅包含两点，LineString为Line。 如果它既是简单的也是封闭的，LineString为LinearRing。
– POLYGON 它由单个外部边界以及0或多个内部边界定义，其中，每个内部边界定义为Polygon中的1个孔。例如:在地区地图上，Polygon对象可表示森林。
– MULTIPOINT MultiPoint是一种由Point元素构成的几何对象集合。这些点未以任何方式连接或排序。
– MULTILINESTRING MultiLineString是一种由 LineString元素构成的MultiCurve几何对象集合，例如：河流体系或高速路系统。
– MULTIPOLYGON MultiPolygon是一种由Polygon元素构成的几何对象集合。在地区地图上，MultiPolygon可表示湖泊系统。
– GEOMETRYCOLLECTION 他是由1个或多个任意类几何对象构成的几何对象。GeometryCollection中的所有元素必须具有相同的空间参考系(即相同的坐标系).
以上几种的类型依赖关系，如图所示：

了解过上述一些基本知识，下面来创建一张商户表，并且包含定义的空间数据库的POINT字段：
Create table shop (
shop_id int(3) primary key,
Location POINT,
Shop_na vachar(100),
Shop_info vachar(300)
);

插入几条商家的门店信息，其中采用GeomFromText方法将坐标的数据库插入POINT字段中，例如：
insert into shop values (‘XXX’,’,GeomFromText(‘POINT(1 1)’),’XX店’,’ '其他信息');
下面将根据客户当前所在位置在MySQL中查询，搜索出在当前位置附近的一定范围内的门店，并且可以做到按距离由近到远排列显示出来，从让用户而找到离他最近的门店。
把客户当前所在位置可设成变量 ，例如:set @center=GeomFromText(‘POINT(10 10)’)；

再把要找到最近门店可以缩小搜索范围 设半径，添加搜索条件
例：set @radius=30;
WHERE SQRT(POW( ABS( X(location) – X(@center)), 2) + POW( ABS(Y(location) – Y(@center)), 2 )) < @radius

最近门店搜索，完整的SQL示例：
SELECT shop_id,shop_na, SQRT(POW( ABS( X(Location) – X(@center)), 2) + POW(ABS(Y(Location) – Y(@center)), 2 )) AS distance
FROM shop WHERE SQRT(POW( ABS( X(location) – X(@center)), 2) + POW( ABS(Y(location) – Y(@center)), 2 )) < @radius
order by distance;

其中涉及的数学函数SQRT(x)：表示求一个数x的平方根。POW(x,y):包含两个参数表示求x的y次幂。ABS(x)：表示求数X的绝对值。整个SQRT(POW( ABS( X(Location) – X(@center)), 2) + POW(ABS(Y(Location) – Y(@center)), 2 ))这个SQL语句实现的是一个算术表达式

即两点间的直线距离。
比如说现在有两个点坐标A(x1,y1)，B(x2,y2) 要求线段AB长度 就是用这个公式去计算。把A看成当前位置B看成一个门店，不就是相当于计算当前位置到门店这两个点的距离吗。坐标点有了带进去就行，等于现在只要能用函数把这个公式表示出来就可以了。
所以用到这三个函数：
SQRT(x)：表示求一个数x的平方根。就相当于那个根号。√x
POW(x,y):包含两个参数表示求x的y次幂
例如pow(2,3)就表示23，那么POW((X1-X2),2)就相当于〖（x1-x2）〗^2
ABS(x)：表示求数X的绝对值。|x| ABS(x1-x2)就等于|x1-x2|.

根据那个公式组合起来就行了
整个SQRT(POW( ABS( X(Location) – X(@center)), 2) + POW(ABS(Y(Location) – Y(@center)), 2))这句话就是用来表示这个公式的
,
这个公式计算得出来的值就是两点间的直线距离。

参考资料：
http://dev.mysql.com/doc/refman/5.1/zh/spatial-extensions-in-mysql.html
http://en.wikipedia.org/wiki/Spatial_database

口水：
以上部分内容来自 NJ-AMT 实习生余珊的分析报告。

–end–