热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

BearMaps

Intro这是CS61B的Project3,也是最后一个Proj。刚好上完这门课出去旅个游,放松下心情开始15213。完成基本的要求花了5天时间,当然现在的版本还十分简陋,这个工程

Intro

这是CS61B的Project 3,也是最后一个Proj。刚好上完这门课出去旅个游,放松下心情开始15213。
完成基本的要求花了5天时间,当然现在的版本还十分简陋,这个工程我是想做得比较大,后面还得抽时间完善、优化。

SP18用了maven做项目建构工具,折腾了一天也没有配好,不知道这么垃圾的工具有啥用,最后实在没辙就把该项目所有需要的jar包导进来,后来发现SP19就抛弃了maven。
技术分享图片
项目需要的地图集以及地图上的点/路信息都是Google采集好的,可在这里下载,当然这个地图只是一小部分,后面想要扩展可以去下载需要的数据集。
整体需求是实现一个地图,用户通过浏览器输入URL,Java程序接收,然后生成相应的地图结果并返回,在浏览器中显示。服务器框架用的是Spark,前端以及前后端交互的部分已经写好了,其实我有时候觉得这些dirty的工作比较考验码力,这些代码写得漂亮说明System的能力是挺强的。


栅格化

将真实世界的经纬度信息转为实际地图,Rasterer.java会接收用户请求的矩形参数,生成对应的图像。
街景图采用冗余存储,都是256*256像素,每张图都是不同分辨率:d0x0y0是整个区域,但是分辨率很低,d1x0y0/d1x0y1/d1x1y0/d1x1y1分别代表四个角,分辨率加倍。更加规范的说:在第D个缩放级别,共有\(4^D\)张图片,dDx0y0到dDxkyk,\(k=2^D-1\),x增大向东移动,y增大向南移动,我们需要返回String[][]代表用户请求区域的图片文件名矩阵,当然还有一些其他参数。
这样对于同一个区域,可以有很多选择:可以用多张高分辨率的组合,也可以用很少几张低分辨率的图片组合,只要满足用户要求,但这样做很可能overflow,远远超过用户要求,浪费时间和资源,因为分辨率高就意味着展示的空间小,并且前端是不会做缩放的,如果用很多高分辨率图片,浏览器会有太多太多照片显示,因为大家都是256*256的。
所以定义单位像素的经度距离:\(\text{LonDPP} = \frac{\text{lower right longitude} - \text{upper left longitude}}{\text{width of the image (or box) in pixels}}\),我们要展示的是小于用户要求LONPPP的最大值,比方说用户要求每个像素2度,如果我们大于2,那么分辨率低到不能满足要求,只有小于2才能满足要求。又不能太小,分辨率太高展示范围变小。当然如果用户要求的很低,只能用现有的最低的LonPPp图片。
可以将LonPPP理解为模糊程度,LonPPP越大,最模糊,比如d0。
纬度也要做类似处理。
举例来看:
技术分享图片
主要工作在getmapRaster完成,传入map包含用户输入的查询请求,共有6个参数:
{lrlon=-122.2104604264636, ullon=-122.30410170759153, w=1085.0, h=566.0, ullat=37.870213571328854, lrlat=37.8318576119893}
经度范围,浏览器显示窗口宽和高,纬度范围

返回的map,除了String外还有object,这是因为java只能返回一个值,所以只能组装成obj返回。
[[d2_x0_y1.png, d2_x1_y1.png, d2_x2_y1.png, d2_x3_y1.png],
[d2_x0_y2.png, d2_x1_y2.png, d2_x2_y2.png, d2_x3_y2.png],
[d2_x0_y3.png, d2_x1_y3.png, d2_x2_y3.png, d2_x3_y3.png]]

具体实现分2步:



  • 需要的图片的depth

  • 确定起始和结束的k

边界判断一定要加EPS,不然一点小误差会崩掉程序

读取图片文件时,总是javax.imageio.IIOException: Can‘t read input file!
这一般都是路径问题,

全图的经纬度范围是:-122.29980, 37.89220 -122.21191, 37.82280

因为地球不是规则的,但是在确定Depth时,如果经度londpp满足要求即可,不用考虑纬度的影响,影响不大。
corner case:



  • 部分覆盖:用户拖到全图外;缩放很小,包含了全图


Routing & Location Data

路由和位置数据是通过berkeley-2018.osm.xml文件给的,是整个地球数据的一部分。
第一步就是要建一个图,因为最后要路径规划嘛。
用的是SAX Parser解析xml数据,遍历每个element,在每个元素的开始和结束位置,调用startElement和endElement回调函数:
先来熟悉下OSM XML文档:
技术分享图片
很好理解了,node结点是组成地图的主干,有id, lat, lon等属性,如果结点是一个位置,那么tag标签就会有名字,如果是其他的,比如路上的一个点,那么就没有tag
技术分享图片
way,一条路,上面可能有很多node,用id表示,同样,tag会包含额外信息,名字,如果是highway,会有道路类型之类的东西。

在GraphDB中表示图,要求允许插入和删除结点,最后要清理掉没有连接的结点

先用GraphDB写好一些接口函数,然后用GraphBuildingHandler将XML中的信息解析为真正的图。
选择邻接矩阵存储,由于这是一个动态的图,可能要增加或者删除结点,所以一开始顶点个数是不确定的,也就不能用int[][]表示。所以想到用Map,映射一对结点之间有边,value设置为经过的结点的集合:

邻接表更好,因为有clean()操作,需要找到单独的结点并删除,邻接表更快,找到有没有相邻的结点很方便。
builder每次只处理XML的一行,也就是一个标签,builder这个类可以被其它方法多次调用去处理完所有的XML,我发现这种拆分很有用,系统会变得简单,只需要考虑当前状态就很好写。清楚需求后,需要设计类的接口,数据结构和算法,这才是最难的部分。

要在元素开始处和结束处做一些事情,在2个方法中实现。

由于parse解析是从上到下的,所以处理way时最好不要直接把边和 边上的点直接加进图里,因为后面的highway的值可能不在合法范围内,这种边是不算的。所以在碰到边上的点,先存到一个数组里,最后endElement时候如果路合法,在加进图里。处理node也同理,在endElement加入图
我们的way包括很多个结点,一条way有很多边,边的属性就是fromid, toid, 名字,就是更加细粒度的控制,而不是直接用一个id和一串nd ref表示。每条way是由多个edge连接成的。

adj不能只存某个结点id到其邻居的id,这样信息是不完整的,还要存储距离,名字等,所以就存为所有的邻边,通过边可以找到邻居node的id等信息。
记得每次做完一个node或way要clear上一个的状态信息。

ConcurrentModificationException如果迭代同时进行修改就会引发该异常
long closest(double lon, double lat)方法会被用来找最短路,需要返回最近的有邻居的点,一个点可能没有邻居,因为他是饭店啥的,不能用来找最短路。另外,这个方法复杂度要求\(O(lgn)\),先实现一个\(O(n)\)的做法,后续有时间再去优化吧。


建好地图后,就要做路由工作,给定一个起始点和终点,选一条距离最短的路径。
应该从距起点最近的Node开始导航到剧终点最近的node结束。当然这些node必须是connected的。
距离就是计算12之间、23之间...的距离之和,两点间距离采用Great-circle distance,即当作球模型来计算弧长距离。还要考虑经纬度是不同的,并且随着纬度变化,每度代表的实际距离也是不同的。
用A*算法,具体没什么特殊的,重要的就是优化:
debug真痛苦啊

要注意目标不可达的情况

笔记本配置太烂,跑大的数据集根本跑不动,只能用小的来测试:

先实现SP18的基本功能,后续再根据SP19去优化。

TODO 这里有一个optimal feature,就是增加导航信息,DIRECTION on WAY for DISTANCE miles
DIRECTION有8种选择:
“Start”
“Continue straight”
“Slight left/right”
“Turn left/right”
“Sharp left/right
方向取决于当前结点和上一个节点的角度,
Between -15 and 15 degrees the direction should be “Continue straight”.
Beyond -15 and 15 degrees but between -30 and 30 degrees the direction should be “Slight left/right”.
Beyond -30 and 30 degrees but between -100 and 100 degrees the direction should be “Turn left/right”.
Beyond -100 and 100 degrees the direction should be “Sharp left/right”.
“unknown road”


搜索地名时只输入一部分,就返回以他开头的所有地名,就是一个单词补全功能。
技术分享图片
public static List getLocationsByPrefix(String prefix)没啥好说的,用Trie,复杂度要求\(O(k)\),k是共享前缀的所有地名。

public static List> getLocations(String locationName)还有search功能,就是搜索一个地名,要返回同名的所有地方的信息,如果正确实现,那么就会有一个mark标记在那个地方。
技术分享图片
需要\(O(k)\)复杂度,也要利用Trie,但是现在可能有重复,所以我们的数据结构需要做出相应修改,每个TrieNode还要增加(最好是只给叶子增加)经纬度和ID,用List>来存储,每当添加一个单词时,到最后都存储经纬度和ID,这样重名的地点的名字一样、所有的经纬度ID都在List当中,就可以直接展示出来。

还有要支持搜索餐厅名、体育场这种

debug很痛苦,有一次怎么样在浏览器都渲染不出来,折腾了一天,最后发现是因为html文件里一个js文件要FQ才可以访问,醉了。

笔记本性能太差,OSM DB PATH选大的有46MB,所以只能用32KB的小路径去测试


Extensions



  • Front-end Integration
    现在是每调用一次,就在后台raster the entire image,然后传到前端显示。前端可以缓存用过的tiles,然后下次调用直接组装。

  • Vectored Tiles
    现在是一张张图片,实际上大多用的是用oads, lines, filled areas, buildings and so on that make up the tile,用OpenGL/WebGL,并且用GPU比CPU快要很多.https://wiki.openstreetmap.org/wiki/Vector_tiles下载



TODO

做工程真是长期的活,遇到bug每天能写50行就不错了。
接下来,还有


Reference

Project 3: Bear Maps, version 3.0
Project 2C: Bear Maps, version 4.0

技术分享图片
技术分享图片

关于每个方法的时间复杂度,都已经标注在了代码中
long closest(double lon, double lat)最简单的实现就是遍历图中所有结点,找到最近的,但是文档里要求这个方法的复杂度必须是O(lgn),

尽量少用protected修饰成员变量,写一个函数接口去访问。


推荐阅读
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ,包括端口开放及防火墙设置。通过本文,您可以掌握完整的ActiveMQ部署流程,确保其在网络环境中正常运行。 ... [详细]
  • 深入理解 Oracle 存储函数:计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程,并提供完整的代码示例。 ... [详细]
  • 本文总结了2018年的关键成就,包括职业变动、购车、考取驾照等重要事件,并分享了读书、工作、家庭和朋友方面的感悟。同时,展望2019年,制定了健康、软实力提升和技术学习的具体目标。 ... [详细]
  • 在计算机技术的学习道路上,51CTO学院以其专业性和专注度给我留下了深刻印象。从2012年接触计算机到2014年开始系统学习网络技术和安全领域,51CTO学院始终是我信赖的学习平台。 ... [详细]
  • CSS 布局:液态三栏混合宽度布局
    本文介绍了如何使用 CSS 实现液态的三栏布局,其中各栏具有不同的宽度设置。通过调整容器和内容区域的属性,可以实现灵活且响应式的网页设计。 ... [详细]
  • Linux 系统启动故障排除指南:MBR 和 GRUB 问题
    本文详细介绍了 Linux 系统启动过程中常见的 MBR 扇区和 GRUB 引导程序故障及其解决方案,涵盖从备份、模拟故障到恢复的具体步骤。 ... [详细]
  • 本文介绍了如何使用jQuery根据元素的类型(如复选框)和标签名(如段落)来获取DOM对象。这有助于更高效地操作网页中的特定元素。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进,包括右缩进和左缩进的具体操作方法。 ... [详细]
  • 深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准,旨在为第三方应用提供安全的用户资源访问授权,同时确保用户的账户信息(如用户名和密码)不会暴露给第三方。 ... [详细]
  • 2023 ARM嵌入式系统全国技术巡讲旨在分享ARM公司在半导体知识产权(IP)领域的最新进展。作为全球领先的IP提供商,ARM在嵌入式处理器市场占据主导地位,其产品广泛应用于90%以上的嵌入式设备中。此次巡讲将邀请来自ARM、飞思卡尔以及华清远见教育集团的行业专家,共同探讨当前嵌入式系统的前沿技术和应用。 ... [详细]
  • 国内BI工具迎战国际巨头Tableau,稳步崛起
    尽管商业智能(BI)工具在中国的普及程度尚不及国际市场,但近年来,随着本土企业的持续创新和市场推广,国内主流BI工具正逐渐崭露头角。面对国际品牌如Tableau的强大竞争,国内BI工具通过不断优化产品和技术,赢得了越来越多用户的认可。 ... [详细]
  • MySQL中枚举类型的所有可能值获取方法
    本文介绍了一种在MySQL数据库中查询枚举(ENUM)类型字段所有可能取值的方法,帮助开发者更好地理解和利用这一数据类型。 ... [详细]
author-avatar
迷迷糊糊的Nancy
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有