`
yajie
  • 浏览: 213850 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

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

阅读更多

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

当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中的所有元素必须具有相同的空间参考系(即相同的坐标系).
以上几种的类型依赖关系,如图所示:
xyz

了解过上述一些基本知识,下面来创建一张商户表,并且包含定义的空间数据库的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语句实现的是一个算术表达式
http://public.bay.livefilestore.com/y1po7ENYXgBlsmmLKp2_WlYd_iiXZhsAAIyqniUqqAkWrJYinExgS5_YBDIcI_vwVg8AEe5Fjh0NLwvbWlAapZpIA/x_y_z_1.png?psid=1
即两点间的直线距离。
比如说现在有两个点坐标A(x1,y1),B(x2,y2) 要求线段AB长度 就是用http://public.bay.livefilestore.com/y1po7ENYXgBlsmmLKp2_WlYd_iiXZhsAAIyqniUqqAkWrJYinExgS5_YBDIcI_vwVg8AEe5Fjh0NLwvbWlAapZpIA/x_y_z_1.png?psid=1 这个公式去计算。把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://public.bay.livefilestore.com/y1pM_5Xtwtl4QeSaP8qXtHUJyDToYypy1K3UmyZVxM_6_E64Xad_C0AlmQDWWE_ncb8ap6FRZfjQX2jWD4eGJMe8w/x_y_z_2.png?psid=1 ,
这个公式计算得出来的值就是两点间的直线距离。

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

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

0
1
分享到:
评论

相关推荐

    校园最短路径规划分析可视化

    同时,数据处理和存储也是关键,可能需要用到数据库系统,如MySQL或MongoDB,来存储和管理地图数据和路径信息。 综上所述,“校园最短路径规划分析可视化”是一个结合了算法设计、地图数据处理、GIS技术及前端开发...

    基于javaweb最短路径公交查询系统设计与实现.docx

    【基于javaweb最短路径公交查询系统设计与实现】 1. 绪论 随着互联网技术的飞速发展,人们的生活越来越依赖网络,特别是在公共交通出行方面。为了提高出行效率,减少等待时间,一个基于最短路径的公交查询系统显得...

    外卖最短路径计算

    Dijkstra算法保证找到从起点到所有其他节点的最短路径。在这个外卖场景中,起点可能是外卖员的位置,终点则是顾客的位置。 3. **A*搜索算法**:A*算法是Dijkstra算法的一种优化,它引入了启发式函数,通过预估到达...

    MySQL数据库目录查询

    MySQL 数据库目录查询 MySQL 数据库目录查询是数据库管理员和开发人员非常关心的一项任务。了解 MySQL 数据库的目录结构对于数据库的管理、维护和优化非常重要。在本文中,我们将详细介绍如何查询 MySQL 数据库的...

    guid.rar_导游 系统_最短路程_校园最短路径

    最短路径算法的使用是关键,它可能涉及到图论中的经典算法,如Dijkstra算法、A*搜索算法或者Floyd-Warshall算法,这些算法可以计算出两点之间最短的距离,并考虑到可能存在的障碍或限制。 标签进一步明确了关键主题...

    h2数据导入mysql数据库(看评论酌情下载)

    h2 数据库导入 MySQL 数据库是指将 h2 数据库中的数据导入到 MySQL 数据库中,以便更好地存储和管理数据。下面将详细介绍 h2 数据库导入 MySQL 数据库的步骤。 首先,需要创建一个 MySQL 数据库。这里可以起名为 ...

    MySql 5数据库驱动包

    要使用MySQL 5数据库驱动包,首先需要将其添加到Java项目的类路径中。这可以通过以下几种方式实现: 1. **命令行参数**:在运行Java程序时,可以使用`-cp`或`-classpath`参数指定包含驱动的`.jar`文件路径。 2. **...

    国家开放大学 MySQL数据库应用 实验训练1 在MySQL中创建数据库和表

    "国家开放大学 MySQL数据库应用实验训练1 在MySQL中创建数据库和表" 本实验训练旨在让学生掌握 MySQL 中的数据库和表的创建过程。 MySQL 是一种关系型数据库管理系统,广泛应用于各种领域。为提高学生的实践能力,...

    改进的Dijkstra算法在多点最优路径组合中的应用——以大学生出游App为例.pdf

    1.2.5 最优路径组合:在每次计算过程中,记录下当前起点到各终点的最短路径,然后通过比较这些路径的总长度,找到最优的多点路径组合。 2. 实现细节 在实际的App开发中,我们采用Html5作为前端界面,以提供用户...

    mysql连接数据库。。jar架包

    1. **安装驱动**:将"mysql连接数据库"中的jar文件(例如`mysql-connector-java-x.x.x.jar`)添加到MyEclipse的类路径中。这可以通过"构建路径" -&gt; "库" -&gt; "添加外部JARs"来完成,选择对应的jar文件,点击"确定...

    北京公交信息查询 VC+MapX GIS二次开发 最短路径,公交换乘.rar

    在公共交通查询系统中,"最短路径"通常指的是时间最短或距离最短的公交换乘方案。这需要实现Dijkstra算法或A*搜索算法等路径规划策略。这些算法可以帮助程序快速找到两个位置之间的最优路线,考虑到交通状况、换乘...

    MySQL数据库应用形考实验1-4全答案.zip

    在这个"MySQL数据库应用形考实验1-4全答案.zip"压缩包中,包含了四个关于MySQL基础操作的实验训练,涵盖了从数据库和表的创建,到数据的查询、增删改,以及数据库系统的维护等关键知识点。以下是对这些实验的详细...

    javaWebssh物流信息管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计最短路径算法源码

    开发环境为TOMCAT7.0,Myeclipse8.5开发,数据库为Mysql5.0,使用java语言开发。 二、功能介绍 功能如博客中介绍 三、注意事项 1、管理员账号:admin 密码:admin 数据库配置文件applicationContext.xml 2、开发...

    C#操作Mysql创建数据库,数据表,增、删、改数据

    Mysql则是一款流行的开源关系型数据库管理系统,因其高效、稳定和易于管理的特性而受到开发者们的青睐。本教程将详细介绍如何使用C#与Mysql进行交互,包括创建数据库、数据表以及执行基本的CRUD(Create、Read、...

    VB6.0连接MySQL数据库

    在编写应用程序时,经常会涉及到数据库的操作,比如查询、更新、删除和插入等。本文将详细地介绍新手如何使用VB6.0连接MySQL数据库,并提供清晰的步骤。 首先,要使VB6.0能够连接到MySQL数据库,需要在VB6.0的应用...

    MySQL数据库入门.rar

    MySQL数据库是目前世界上最受欢迎的关系型数据库管理系统之一,尤其在互联网应用中被广泛使用。这个"MySQL数据库入门"压缩包提供了一系列的学习资源,包括PPT、PDF文档和代码示例,帮助初学者快速掌握MySQL的基础...

    MySQL数据库巡检手册 MySQL DBA必备

    MySQL数据库巡检手册是MySQL数据库管理员(DBA)在进行数据库管理和维护工作中非常重要的参考资料。巡检手册包含了数据库性能、安全、运行状况等方面的检查项,以确保数据库能够正常稳定运行,及时发现并解决潜在问题...

    MySQL数据库-RevD.pdf

    MySQL广泛应用于从大型企业系统到专用的嵌入式应用系统中,支持各种不同的数据类型和数据操作,是目前世界上使用最为广泛的开源数据库之一。 2008年初,Sun Microsystems公司收购了MySQL AB公司,这标志着MySQL进入...

    MyEclipse连接MySQL数据库报错解决办法

    1、在MyEclipse中连接MySQL数据库:依次点击window–&gt;show view–&gt;other–&gt;MyEclipse Database–&gt;DB Browser 图一:找到数据库连接选项 2、选中DB Browser,右键单击,并选择New一个数据连接的菜单,新建一个MySQL...

    MySQL Migration Toolkit 数据库转换工具

    Access-to-MySQL Access数据库转MySQL数据库 DBF-to-MySQL DBF数据库转MySQL数据库 Excel-to-MySQL Excel数据库转MySQL数据库 MSSQL-to-MySQL MSSQL数据库转MySQL数据库 SQL Server数据库转MySQL数据库 MySQL-to-...

Global site tag (gtag.js) - Google Analytics