BearMaps

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)\)的做法，后续有时间再去优化吧。

Route Search

建好地图后，就要做路由工作，给定一个起始点和终点，选一条距离最短的路径。
应该从距起点最近的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”

Autocomplete and Search

搜索地名时只输入一部分，就返回以他开头的所有地名，就是一个单词补全功能。

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