一种导航方法及导航装置

1.一种导航方法，其特征在于，包括：
根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；
搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径；所述特定类型节点包括第一类节点和第二类节点中的至少一种，所述第一类节点仅连接一条路段，所述第二类节点为内部结构中的节点，所述内部结构由至少一条路段构成且仅连接所述内部结构外的一个节点。
2.如权利要求1所述的导航方法，其特征在于，所述特定类型节点包括第一类节点，所述导航方法还包括：将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点；
所述搜索所述道路拓扑网络中除特定类型节点以外的节点包括：搜索所述道路拓扑网络中的节点，若所搜索的节点与第一类节点连接则继续搜索其他节点。
3.如权利要求1所述的导航方法，其特征在于，所述特定类型节点包括第二类节点，所述导航方法还包括：将连接所述内部结构的路段标记为连接路段；
所述搜索所述道路拓扑网络中除特定类型节点以外的节点包括：搜索所述道路拓扑网络中的节点，若所搜索的节点与连接路段连接则继续搜索其他路段的节点。
4.如权利要求1所述的导航方法，其特征在于，所述特定类型节点包括第二类节点，所述导航方法还包括：将所述内部结构中与所述内部结构外的节点连接的第二类节点标记为连接节点；
所述搜索所述道路拓扑网络中除特定类型节点以外的节点包括：搜索所述道路拓扑网络中的节点，若所搜索的节点与连接节点连接则继续搜索其他节点。
5.如权利要求1所述的导航方法，其特征在于，搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径包括：
更新所述道路拓扑网络以去除所述特定类型节点；
搜索更新后的道路拓扑网络中的节点以得到导航路径。
6.如权利要求1所述的导航方法，其特征在于，还包括：加载所述导航路径的数据以将所述导航路径显示于导航电子地图。
7.一种导航装置，其特征在于，包括：
获取单元，用于根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；
搜索单元，用于搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径；所述特定类型节点包括第一类节点和第二类节点中的至少一种，所述第一类节点仅连接一条路段，所述第二类节点为内部结构中的节点，所述内部结构由至少一条路段构成且仅连接所述内部结构外的一个节点。
8.如权利要求7所述的导航装置，其特征在于，所述特定类型节点包括第一类节点，所述导航装置还包括：
第一标记单元，用于将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点；
所述搜索单元包括：
第一搜索子单元，用于搜索所述道路拓扑网络中的节点，若所搜索的节点与第一类节点连接则继续搜索其他节点。
9.如权利要求7所述的导航装置，其特征在于，所述特定类型节点包括第二类节点，所述导航装置还包括：
第二标记单元，用于将连接所述内部结构的路段标记为连接路段；
所述搜索单元包括：
第二搜索子单元，用于搜索所述道路拓扑网络中的节点，若所搜索的节点与连接路段连接则继续搜索其他路段的节点。
10.如权利要求7所述的导航装置，其特征在于，所述特定类型节点包括第二类节点，所述导航装置还包括：
第三标记单元，用于将所述内部结构中与所述内部结构外的节点连接的第二类节点标记为连接节点；
所述搜索单元包括：
第三搜索子单元，用于搜索所述道路拓扑网络中的节点，若所搜索的节点与连接节点连接则继续搜索其他节点。

一种导航方法及导航装置\n技术领域\n[0001] 本发明涉及导航技术领域，特别涉及一种导航方法及导航装置。\n背景技术\n[0002] 随着汽车产业的日益发展，各种车载设备应运而生。人们在拥有汽车的同时，也关注车载设备所带来的优越体验。车载设备的种类有很多，例如车载导航系统、GPS(Global Positioning System)定位系统、TTS(Text to Speech)播报系统、车载DVD播放系统、车载通信系统等。目前，利用GPS定位车辆当前位置的应用已得到普适，导航系统将定位系统与电子地图数据结合，能够提供车载用户关于导航问题的解决方案，当车载用户在交通中因道路不熟悉、天气恶劣等原因，需要导航服务时，导航系统能够帮助车载用户方便快捷地到达目的地。\n[0003] 导航电子地图数据是导航系统不可或缺的一部分，导航电子地图是通过节点和节点之间的路段来对现实中的道路网络进行数字化的，导航中所建立的道路拓扑网络是以节点之间的关系作为拓扑结构的，道路网络是存储在节点之间的关系中，举例来说，对于图1A中的道路a，是通过节点100-路段101-节点102来定义的；而对于图1B中的道路b，是通过节点200-路段201-节点202来定义的；对于图1C中的道路c，是通过节点300-路段301-节点\n302-路段303-节点304来定义的。\n[0004] 通过图1A至1C可知，导航电子地图数据是用路段数据和节点数据来表达道路网络的：路段数据实质对应了道路段的中心线，也即路心线，用来表示道路段，它是形状点的集合；节点数据用来表达道路网络中道路段间的交点，比如可以代表一个路口、道路段的起始点或道路段的终止点。当确定一条道路的第一节点，沿该第一节点指向的路段寻找下一个节点，直到到达所确定的第二节点处，便可形成得到第一节点和第二节点之间的路径。\n[0005] 在使用导航系统进行导航时，导航系统会基于用户的导航请求进行路径计算，并将计算出的导航路径绘制于导航电子地图上显示，使车载用户得到导航路线。上述路径计算是基于上述导航电子地图数据的，具体过程包括：\n[0006] 获得导航电子地图中的节点数据和路段数据；\n[0007] 根据导航请求中的出发地和目的地确定第一节点和第二节点；\n[0008] 沿所述第一节点指向的路段寻找下一个节点，遍历第一节点和第二节点之间的所有节点，直到到达所确定的第二节点处，以得到至少一条从出发地到目的地的路径；\n[0009] 选择所得到的路径作为导航路径。\n[0010] 从上述过程可以了解到，现有技术路径计算的过程是基于导航请求所获得的道路拓扑网络上所有的节点数据和路段数据的，遍历了道路拓扑网络上的所有节点才得到出发地到目的地的路径，这使得路径计算所基于的数据量比较大，路径计算效率较低，导航请求的处理速度不佳。\n发明内容\n[0011] 本发明技术方案所需解决的技术问题是：如何提高导航请求的处理速度。\n[0012] 为了解决上述技术问题，本发明技术方案提供了一种导航方法，包括：\n[0013] 根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0014] 搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径；所述特定类型节点包括第一类节点和第二类节点中的至少一种，所述第一类节点仅连接一条路段，所述第二类节点为内部结构中的节点，所述内部结构由至少一条路段构成且仅连接所述内部结构外的一个节点。\n[0015] 可选的，所述特定类型节点包括第一类节点，所述导航方法还包括：将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点；\n[0016] 所述搜索所述道路拓扑网络中除特定类型节点以外的节点包括：搜索所述道路拓扑网络中的节点，若所搜索的节点与第一类节点连接则继续搜索其他节点。\n[0017] 可选的，所述特定类型节点包括第二类节点，所述导航方法还包括：将连接所述内部结构的路段标记为连接路段；\n[0018] 所述搜索所述道路拓扑网络中除特定类型节点以外的节点包括：搜索所述道路拓扑网络中的节点，若所搜索的节点与连接路段连接则继续搜索其他路段的节点。\n[0019] 可选的，所述特定类型节点包括第二类节点，所述导航方法还包括：将所述内部结构中与所述内部结构外的节点连接的第二类节点标记为连接节点；\n[0020] 所述搜索所述道路拓扑网络中除特定类型节点以外的节点包括：搜索所述道路拓扑网络中的节点，若所搜索的节点与连接节点连接则继续搜索其他节点。\n[0021] 可选的，搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径包括：\n[0022] 更新所述道路拓扑网络以去除所述特定类型节点；\n[0023] 搜索更新后的道路拓扑网络中的节点以得到导航路径。\n[0024] 可选的，所述导航方法，还包括：加载所述导航路径的数据以将所述导航路径显示于导航电子地图。\n[0025] 为了解决上述技术问题，本发明技术方案还提供了一种导航装置，包括：\n[0026] 获取单元，用于根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0027] 搜索单元，用于搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径；所述特定类型节点包括第一类节点和第二类节点中的至少一种，所述第一类节点仅连接一条路段，所述第二类节点为内部结构中的节点，所述内部结构由至少一条路段构成且仅连接所述内部结构外的一个节点。\n[0028] 可选的，所述特定类型节点包括第一类节点，所述导航装置还包括：\n[0029] 第一标记单元，用于将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点；\n[0030] 所述搜索单元包括：\n[0031] 第一搜索子单元，用于搜索所述道路拓扑网络中的节点，若所搜索的节点与第一类节点连接则继续搜索其他节点。\n[0032] 可选的，所述特定类型节点包括第二类节点，所述导航装置还包括：\n[0033] 第二标记单元，用于将连接所述内部结构的路段标记为连接路段；\n[0034] 所述搜索单元包括：\n[0035] 第二搜索子单元，用于搜索所述道路拓扑网络中的节点，若所搜索的节点与连接路段连接则继续搜索其他路段的节点。\n[0036] 可选的，所述特定类型节点包括第二类节点，所述导航装置还包括：\n[0037] 第三标记单元，用于将所述内部结构中与所述内部结构外的节点连接的第二类节点标记为连接节点；\n[0038] 所述搜索单元包括：\n[0039] 第三搜索子单元，用于搜索所述道路拓扑网络中的节点，若所搜索的节点与连接节点连接则继续搜索其他节点。\n[0040] 本发明技术方案的有益效果至少包括：\n[0041] 与现有技术相比，本发明技术方案考虑到路径计算中的非必要数据，对路径计算所基于的节点数据进行了分类及剔除：由于导航电子地图数据所包括的节点数据中，第一类节点和第二类节点均会造成路径计算的耗时，且这部分计算对于路径计算是非必要数据计算，因此在搜索节点的过程中对第一类节点和/或第二类节点进行剔除，减小了路径计算的数据量；本发明技术方案不仅提高了导航请求的处理速度，也使导航设备的路径显示速度也得到了加强。\n[0042] 在可选方案中，本发明技术方案根据第一类节点和第二类节点，直接对获得的道路拓扑网络中的节点数据进行剔除，以得到已剔除特定类型节点的道路拓扑网络再进行搜索，得到导航数据，这避免了搜索过程中的耗时，进一步提高了导航请求的处理速度。\n附图说明\n[0043] 图1A为道路a的结构示意图；\n[0044] 图1B为道路b的结构示意图；\n[0045] 图1C为道路c的结构示意图；\n[0046] 图2为道路拓扑网络40的结构示意图；\n[0047] 图3为道路拓扑网络50的结构示意图；\n[0048] 图4为实施例1所述导航方法的流程示意图；\n[0049] 图5A和5B为实施例1中道路拓扑网络40的数据存储表格的数据示意图；\n[0050] 图6A和6B为实施例1中道路拓扑网络50的数据存储表格的数据示意图；\n[0051] 图6C为实施例2中道路拓扑网络50的数据存储表格的数据示意图；\n[0052] 图7为实施例2所述导航方法的流程示意图；\n[0053] 图8为实施例3所述导航方法的流程示意图；\n[0054] 图9为道路拓扑网络40’的结构示意图；\n[0055] 图10为实施例3中道路拓扑网络40’的数据存储表格的数据示意图；\n[0056] 图11为道路拓扑网络50’的结构示意图；\n[0057] 图12为实施例3中道路拓扑网络50’的数据存储表格的数据示意图；\n[0058] 图13为实施例4所述导航方法的流程示意图。\n具体实施方式\n[0059] 导航电子地图数据是现实中的道路网络的数字化内容，导航电子地图数据使用包括节点数据和路段数据来表示现实中的道路段。\n[0060] 但是，现实中的道路网络是多样化的，比如图2所示的一种道路拓扑网络40，包括节点400～406、路段407～415。\n[0061] 道路拓扑网络40中，假使导航请求中的出发地为x1，目的地为x2，现有技术的导航方法为：\n[0062] 获得道路拓扑网络40中的节点400～406、路段407～415；\n[0063] 根据导航请求中的出发地x1和目的地x2确定第一节点400和第二节点406，其中，出发地x1在路段407上，目的地x2在路段415上；\n[0064] 沿节点400指向的路段寻找下一个节点，遍历第一节点400和第二节点406之间的所有节点(节点401～405)直到到达所确定的节点406处，以得到至少一条从出发地到目的地的路径：在本步骤中可知，节点400所指向的路段应为指向节点406方向的路段，因此可确定为路段407和路段408，由此至少可搜索得到如下路径：\n[0065] 第一路径：节点400-路段408-节点402-路段411-节点403-路段413-节点405；\n[0066] 第二路径：节点400-路段408-节点402-路段411-节点403-路段412-节点404-路段\n414-节点406；\n[0067] 第三路径：节点400-路段409-节点401-路段410-节点404-路段414-节点406。\n[0068] 上述所搜索到的路径中，第二路径和第三路径为从出发地到目的地的路径。\n[0069] 现有技术的导航方法可以从第二路径和第三路径中选择一条路径作为导航路径。\n[0070] 从上述分析可知，第一路径实际是非必要的数据计算，会造成导航请求的处理过程中，路径计算的耗时，影响导航请求的处理效率。\n[0071] 再如图3所示的一种道路拓扑网络50，包括节点500～509、路段510～522。\n[0072] 道路拓扑网络50中，假使导航请求中的出发地为x3，目的地为x4，现有技术的导航方法为：\n[0073] 获得道路拓扑网络50中的节点500～509、路段510～522；\n[0074] 根据导航请求中的出发地x3和目的地x4确定第一节点500和第二节点509，其中，出发地x3在路段510上，目的地x4在路段522上；\n[0075] 沿节点500指向的路段寻找下一个节点，遍历第一节点500和第二节点509之间的所有节点(节点501～508)，直到到达所确定的节点509处，以得到至少一条从出发地到目的地的路径：在本步骤中可知，节点500所指向的路段应为指向节点509方向的路段，因此可确定为路段511和路段512，由此至少可搜索得到如下路径：\n[0076] 第四路径：节点500-路段512-节点502-路段514-节点503-路段516-节点505-路段\n518-节点506-路段519-节点507-路段520-节点508-路段521-节点505-路段516-节点503-路段515-节点504-路段517-节点509；\n[0077] 第五路径：节点500-路段512-节点502-路段514-节点503-路段516-节点505-路段\n521-节点508-路段520-节点507-路段519-节点506-路段518-节点505-路段516-节点503-路段515-节点504-路段517-节点509；\n[0078] 第六路径：节点500-路段512-节点502-路段514-节点503-路段515-节点504-路段\n517-节点509；\n[0079] 第七路径：节点500-路段511-节点501-路段513-节点504-路段517-节点509。\n[0080] 上述所搜索到的路径中，第四路径至第七路径均可从出发地到目的地的路径，但对比第六路径，可知：第四路径中的路径段“节点503-路段516-节点505-路段518-节点506-路段519-节点507-路段520-节点508-路段521-节点505-路段516-节点503”及第五路径中的路径段“节点503-路段516-节点505-路段521-节点508-路段520-节点507-路段519-节点\n506-路段518-节点505-路段516-节点503”为非必要数据计算，会造成导航请求处理过程中路径计算的耗时。\n[0081] 进一步分析第一路径、第四路径和第五路径中的数据特点，可知：\n[0082] 对比第二路径，造成第一路径的计算结果是由于现实道路网络中的道路段“节点\n403-路段413-节点405”，分析该段道路的特点，可知，道路段“节点403-路段413-节点405”是一种“断头路”，即节点405并未被继续延伸生成道路，而在节点405处仅有一条路段413与之连接；\n[0083] 对比第六路径，造成第四路径和第五路径的计算结果是由于现实道路网络中的道路结构“节点505-路段518-节点506-路段519-节点507-路段520-节点508-路段521-节点\n505”和道路结构“节点505-路段521-节点508-路段520-节点507-路段519-节点506-路段\n518-节点505”，分析上述道路结构，可知：上述道路结构实质是道路拓扑网络中的一种内部结构，其由至少一条路段构成，除通过道路段节点503-路段516-节点505与道路结构外的道路拓扑网络50连接外，其他路段及其节点构成封闭区域。\n[0084] 实施例1\n[0085] 本实施例基于上述分析，将类似于第一路径中节点405的节点类型定义为第一类节点，将类似于第四路径的道路结构“节点505-路段518-节点506-路段519-节点507-路段\n520-节点508-路段521-节点505”和第五路径的道路结构“节点505-路段521-节点508-路段\n520-节点507-路段519-节点506-路段518-节点505”中的节点类型定义为第二类节点，并给出一种如图4所示的导航方法，包括：\n[0086] 步骤S100，根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络。\n[0087] 导航请求中一般带有输入的出发地信息和目的地信息，由于导航电子地图数据较为完备，本步骤中，获取出发地和目的地之间的道路拓扑网络可以采用多种方式：\n[0088] 第一种方式：根据出发地所在道路段和目的地所在道路段，得到上述道路段对应的路段，再根据出发地和目的地之间的方向关系，确定出发地所在路段上的一个节点作为第一节点，确定目的地所在路段上的一个节点作为第二节点，再获取第一节点和第二节点之间的道路拓扑网络；\n[0089] 第二种方式：根据出发地和目的地之间的直线距离建立出发地和目的地之间的区域范围，直接获取所述区域范围内的道路拓扑网络作为所获取的道路拓扑网络；\n[0090] 第三种方式：根据出发地所在道路段和目的地所在道路段，得到出发地所在道路段对应的第一路段和目的地所在道路段对应的第二路段，获取第一路段和第二路段之间的道路拓扑网络。\n[0091] 出发地和目的地之间的道路拓扑网络的获取方式并不限于上述三种方式。\n[0092] 步骤S101，搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径。\n[0093] 所述特定类型节点包括第一类节点和第二类节点中的至少一种，所述第一类节点，可参考图2中的节点405的描述，即第一类节点仅连接一条路段，所述第二类节点为内部结构(类似于图3中的道路结构)中的节点，可参考图3中的节点505至508，所述内部结构由至少一条路段构成且仅连接所述内部结构外的一个节点(例如图3中的节点503)。\n[0094] 当然，若步骤S100所获取的道路拓扑网络中，不存在所述特定类型节点，则建立导航路径时，搜索的节点为所有节点。\n[0095] 需要说明的是，为了清楚地说明第一类节点和第二类节点，本实施例是分别通过图2所示的仅包含第一类节点的道路拓扑网络40和图3所示的仅包含第二类节点的道路拓扑网络50进行举例说明的，本领域技术人员应当可以理解，道路拓扑网络是存在既包括所述第一类节点又包括所述第二类节点的情况的。\n[0096] 对于特定类型节点，可以在执行步骤S101之前，设置先执行步骤S200以对道路拓扑网络的节点或路段进行标记以增强步骤S101的搜索速率：\n[0097] 步骤S200，将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点；\n将连接内部结构的路段标记为连接路段。\n[0098] 步骤S200与步骤S100并无特定的顺序关系：步骤S200中的道路拓扑网络可以是出发地和目的地之间的道路拓扑网络，也可以是包括所述出发地和目的地之间的道路拓扑网络的任何道路拓扑网络，内部结构可以是出发地和目的地之间的道路拓扑网络中的内部结构，也可以是包括所述出发地和目的地之间的道路拓扑网络的任何道路拓扑网络中的内部结构。本实施例步骤S200设置于步骤S100之后。\n[0099] 图5A是步骤S200执行前，与图2所示道路拓扑网络所对应的节点数据和路段数据的存储表格(假使存储表格中的节点数据和路段数据即为图2中各节点和各路段的标号)，其中，路段413对应节点403和节点405。\n[0100] 经步骤S200标记后，如图5B所示，将节点405的节点数据405设置为0，代表节点405为一个空节点。\n[0101] 通过图5A和图5B的对比，可知：所述将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点的一种方式可以是将第一类节点的对应数据设置为0，以空节点标记第一类节点。这是从现实道路网络中，第一类节点所代表的特性考虑的，以便于现实道路网络更新建设，重新将空节点写入对应数据，以及时和道路网络同步；另一方面，将第一类节点置零也是基于减小导航数据存储量的考虑，没有必要将第一类节点归为路径计算的有效数据，因而直接将该部分数据置零以减小这部分数据的存储空间的占用。\n[0102] 图6A是步骤S200执行前，与图3所示道路拓扑网络所对应的节点数据和路段数据的存储表格(假使存储表格中的节点数据和路段数据即为图2中各节点和各路段的标号)，其中：\n[0103] 路段516对应节点514和节点505；\n[0104] 路段518对应节点505和节点506；\n[0105] 路段519对应节点506和节点507；\n[0106] 路段520对应节点507和节点508；\n[0107] 路段521对应节点508和节点505。\n[0108] 经步骤S200标记后，如图6B所示，路段516被标记为连接路段，可以用flag标记连接路段，进一步还可以对flag赋予不同值以对路段516对应的节点特性做标记，比如用1作为flag标记时，表示被标记路段的起始点为通路而结束点为非通路，用2作为flag标记时，表示被标记路段的起始点为非通路而结束点为通路，用3作为flag标记时，表示被标记路段的起始点和结束点均为通路，用4作为flag标记时，表示被标记路段的起始点和结束点均为非通路。路段516可以被真实地标记路段特性为3，也可以被虚假标记路段特性为1：在对道路拓扑网络的连接路段进行标记，可先对道路拓扑网络内的各路段的真实特性进行检索记录，可以将该真实特性直接作为flag标记，也可以对该连接路段另外地提炼虚假特性作为flag标记，作为虚假特性的flag标记是任意的，也可以用其他与路段特性不相关的标记作为其flag标记。本实施例以路段的真实特性作为连接路段的flag标记的，图6B中，路段516被标记为3。\n[0109] 通过图6A和图6B的对比，可知：所述将连接所述内部结构的路段标记为连接路段的一种方式可以是将第二类节点所在的内部结构与该内部结构外的道路结构所连接的路段作flag标记，并通过flag值对被标记路段上的节点作一个特性标记，以供路径计算使用。\n所述内部结构在现实道路中一般代表为比较封闭的小区道路结构或建筑工地的内部道路结构，且上述内部结构仅连接有一个外部节点，连接该外部节点与内部结构的第二类节点的路段作为该内部结构的出入口被定义为连接路段。上述标记的主要目的是为了避免搜索内部结构上的节点数据，也就是第二类节点，以提高节点遍历的速率和有效性。\n[0110] 对应步骤S200，步骤S101中的搜索步骤进一步是通过如下方式执行的：\n[0111] 搜索所述道路拓扑网络中的节点：\n[0112] 若所搜索的节点与第一类节点连接则继续搜索其他节点；\n[0113] 若所搜索的节点与连接路段连接则继续搜索其他路段的节点。\n[0114] 对于第一类节点，结合图2和图5B，当执行步骤S101时搜索到节点411，可知与节点\n411相关的路段包括路段412和路段413，与节点411通过路段412连接的节点为404，与节点\n411通过路段413连接的节点为空节点(节点0，对应图2中的节点405)，则此时，继续搜索的其他节点为除所述第一类节点以外的、与所搜索节点连接的节点，即继续搜索的节点为非空节点，即通过路段412与节点411连接的节点404。\n[0115] 对于第二类节点，结合图3和图6B，当执行步骤S101时搜索到节点503，可知与节点\n503相关的路段包括路段515和路段516，与节点503通过路段515连接的节点为504，与节点\n503通过路段516连接的节点为505，则此时，所述其他路段为除连接路段的其他与所搜索节点相关的路段，继续搜索的节点为与所搜索节点连接、为非连接路段的路段上的节点，即路段515上的节点504，这样与连接路段516连接的内部结构中的第二类节点即节点505、506、\n507、508将不再被搜索。\n[0116] 本实施例对导航请求的处理过程中，路径计算所涉及的节点数据和路段数据进行了分类和标记；在路径计算的搜索过程里，采用避开所标记数据的方式对节点数据进行选择性遍历，以加快路径计算的速率。\n[0117] 需要说明的是，本实施例是先标记第一类节点和关联于第二类节点的连接路段，然后搜索节点得到导航路径的过程中通过识别标记来过滤不必要的节点。在其他实施例中，也可以不做标记，而在搜索节点得到导航路径的过程中直接判断与所搜索的节点是否属于第一类节点或第二类节点并进行过滤。\n[0118] 实施例2\n[0119] 本实施例提供了一种如图7所示的导航方法，包括：\n[0120] 步骤S100，根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0121] 步骤S300，将所述道路拓扑网络中仅与一条路段连接的节点标记为第一类节点；\n将所述内部结构中与所述内部结构外的节点连接的第二类节点标记为连接节点；\n[0122] 步骤S201，搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径。\n[0123] 步骤S300和步骤S100也无特定的顺序关系。步骤S300与步骤S200的不同之处在于，对第二类节点的标记方式不同：步骤S300是对内部结构中与外界节点连接的第二类节点标记为连接节点：\n[0124] 参考图6C并结合图6A，经步骤S300标记后，节点505被标记为连接节点，进一步还可以对节点505的flag标记赋值以对该节点的特性做出标记，与标记为连接路段类似的，用\n1作为flag标记时，表示被标记节点为通路，用2作为flag标记时，表示被标记节点为非通路。图6C中，节点505被标记为1。本实施例连接节点的flag标记方式可以参考实施例1连接路段的flag标记方式，可以以连接节点的真实特性、虚假特性或其他任意标记作为其flag标记。\n[0125] 通过图6A和图6C的对比，可知步骤S300在路径计算中避开第二类节点方式上，给出了不同于步骤S200的技术手段：所述将所述内部结构中与所述内部结构外的节点连接的第二类节点标记为连接节点的一种方式可以是将第二类节点所在的内部结构与该内部结构外的道路节点所连接的节点(属于第二类节点)标记为连接节点，使用flag标记对被标记节点作特性标记，以供路径计算使用。上述标记的主要目的也是为了在路径计算中避免非必要地搜索内部结构上的节点数据，即第二类节点，能够提高节点遍历的速率和有效性。\n[0126] 对应步骤S300，步骤S201中的搜索步骤的具体实现方式也与实施例1有所区别：\n[0127] 搜索所述道路拓扑网络中的节点：\n[0128] 若所搜索的节点与第一类节点连接则继续搜索其他节点；\n[0129] 若所搜索的节点与连接节点连接则继续搜索其他节点。\n[0130] 对于第一类节点，执行步骤S201的搜索步骤可以参考实施例1。\n[0131] 对于第二类节点，结合图3和图6C，当执行步骤S201时搜索到节点503，可知与节点\n503相关的路段包括路段515和路段516，与节点503通过路段515连接的节点为504，与节点\n503通过路段516连接的节点为505，而节点505是被flag标记为1的，此时，继续搜索的节点应为非连接节点，也就是通过路段515连接的节点504。\n[0132] 本实施例的其他内容可参考实施例1。\n[0133] 实施例3\n[0134] 本实施例提供了一种如图8所示的导航方法，包括：\n[0135] 步骤S100，根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0136] 步骤S400，更新所述道路拓扑网络以去除特定类型节点；以及，[0137] 步骤S401，搜索更新后的道路拓扑网络中的节点以得到导航路径。\n[0138] 步骤S400中，所述道路拓扑网络指的是步骤S100中所获取的出发地和目的地之间的道路拓扑网络；当然，在其他实施例中也可以不限定步骤S400和步骤S100之间的顺序，道路拓扑网络可以指区域范围内的道路拓扑网络。\n[0139] 本实施例直接去除被遍历道路拓扑网络的非必要节点数据和路段数据：\n[0140] 对照图2和图5A至图5B，更新后的道路拓扑网络40’如图9所示，而道路拓扑网络\n40’对应的节点数据和路段数据的存储表格如图10所示，图10中，由于图9所示道路拓扑网络40’的路段413去除了一个节点(节点405)，可以在道路拓扑网络40’对应的存储表格中直接略去路段413对应的节点数据和路段数据。在对道路拓扑网络40进行路径计算时，步骤S401仅需对图9和图10所示的道路拓扑网络40’中的节点进行遍历。\n[0141] 对照图3和图6A至图6C，更新后的道路拓扑网络50’如图11所示，而道路拓扑网络\n50’对应的节点数据和路段数据的存储表格如图12所示，同样在图12中，由于图11所示道路拓扑网络50’的路段516去除了一个节点(节点505)，可以在道路拓扑网络50’对应的存储表格中直接略去路段516对应的节点数据和路段数据。在对道路拓扑网络50进行路径计算时，步骤S401仅需对图11和图12所示的道路拓扑网络50’中的节点进行遍历。\n[0142] 实施例4\n[0143] 本实施例的导航方法，如图13所示，包括：\n[0144] 步骤S100，根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0145] 步骤S102，搜索所述道路拓扑网络中除特定类型节点以外的节点以得到导航路径；\n[0146] 步骤S103，加载所述导航路径的数据以将所述导航路径显示于导航电子地图。\n[0147] 步骤S102具体实施时，可以参考实施例1的步骤S200和S101，或者参考实施例2的步骤S300和S201，或者参考实施例3的步骤S400和S401。\n[0148] 实施例5\n[0149] 本实施例的导航方法包括如下步骤：\n[0150] 根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0151] 搜索所述道路拓扑网络中除第一类节点以外的节点以得到导航路径。\n[0152] 实施例6\n[0153] 本实施例的导航方法，包括如下步骤：\n[0154] 根据接收到的导航请求，获取出发地和目的地之间的道路拓扑网络；\n[0155] 搜索所述道路拓扑网络中除第二类节点以外的节点以得到导航路径。\n[0156] 本发明虽然已以较佳实施例公开如上，但其并不是用来限定本发明，任何本领域技术人员在不脱离本发明的精神和范围内，都可以利用上述揭示的方法和技术内容对本发明技术方案做出可能的变动和修改，因此，凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化及修饰，均属于本发明技术方案的保护范围。