热门标签 | 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修饰成员变量,写一个函数接口去访问。


推荐阅读
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 本文探讨了在不使用服务器控件的情况下,如何通过多种方法获取并修改页面中的HTML元素值。除了常见的AJAX方式,还介绍了其他可行的技术方案。 ... [详细]
  • 本文介绍如何使用 NSTimer 实现倒计时功能,详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器,确保在指定时间间隔内执行特定任务。 ... [详细]
  • 本文介绍了在Windows环境下使用pydoc工具的方法,并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外,还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]
  • 本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本,并进行数据处理和保存。 ... [详细]
  • 国内BI工具迎战国际巨头Tableau,稳步崛起
    尽管商业智能(BI)工具在中国的普及程度尚不及国际市场,但近年来,随着本土企业的持续创新和市场推广,国内主流BI工具正逐渐崭露头角。面对国际品牌如Tableau的强大竞争,国内BI工具通过不断优化产品和技术,赢得了越来越多用户的认可。 ... [详细]
  • 深入理解 Oracle 存储函数:计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程,并提供完整的代码示例。 ... [详细]
  • 本文总结了2018年的关键成就,包括职业变动、购车、考取驾照等重要事件,并分享了读书、工作、家庭和朋友方面的感悟。同时,展望2019年,制定了健康、软实力提升和技术学习的具体目标。 ... [详细]
  • 本周信息安全小组主要进行了CTF竞赛相关技能的学习,包括HTML和CSS的基础知识、逆向工程的初步探索以及整数溢出漏洞的学习。此外,还掌握了Linux命令行操作及互联网工作原理的基本概念。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • Linux 系统启动故障排除指南:MBR 和 GRUB 问题
    本文详细介绍了 Linux 系统启动过程中常见的 MBR 扇区和 GRUB 引导程序故障及其解决方案,涵盖从备份、模拟故障到恢复的具体步骤。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 深入理解Tornado模板系统
    本文详细介绍了Tornado框架中模板系统的使用方法。Tornado自带的轻量级、高效且灵活的模板语言位于tornado.template模块,支持嵌入Python代码片段,帮助开发者快速构建动态网页。 ... [详细]
  • PHP 5.2.5 安装与配置指南
    本文详细介绍了 PHP 5.2.5 的安装和配置步骤,帮助开发者解决常见的环境配置问题,特别是上传图片时遇到的错误。通过本教程,您可以顺利搭建并优化 PHP 运行环境。 ... [详细]
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社区 版权所有