沿引导路径检索兴趣点的方法及使用了此方法的导航系统

1.一种沿引导路径检索兴趣点的方法，其特征在于，包括以下步骤：
A：接收用户输入的兴趣点属性信息；
B：根据当前导航系统生成的引导路径计算兴趣点检索范围；
C：根据步骤A用户输入的兴趣点属性信息在步骤B中计算得到的兴趣点检索范围中检索得到兴趣点；
其中，所述的步骤B中，兴趣点检索范围包括左侧搜索延伸范围及右侧搜索延伸范围；
所述左侧搜索延伸范围为沿引导路径向路径左侧延伸一预设的左侧搜索延伸距离所覆盖的范围；所述右侧搜索延伸范围为沿引导路径向路径右侧延伸一预设的右侧搜索延伸距离所覆盖的范围。
2.如权利要求1所述的沿引导路径检索兴趣点的方法，其特征在于，所述的步骤A中，还包括接收用户输入的左侧搜索延伸距离及右侧搜索延伸距离，用于计算左侧搜索延伸范围及右侧搜索延伸范围的步骤。
3.如权利要求1所述的沿引导路径检索兴趣点的方法，其特征在于，所述的步骤B中，根据当前导航系统生成的引导路径计算兴趣点检索范围时，仅计算在当前行车位置前方的未行驶的引导路径所在路段的兴趣点检索范围。
4.如权利要求3所述的沿引导路径检索兴趣点的方法，其特征在于，所述的步骤B中，根据当前导航系统生成的引导路径计算兴趣点检索范围时，仅计算沿着引导路径、在行车方向且距离当前行车位置一预设的搜索距离长度内所在路段的兴趣点检索范围。
5.如权利要求4所述的沿引导路径检索兴趣点的方法，其特征在于，所述的步骤A中，还包括接收用户输入的搜索距离长度，用于计算兴趣点检索范围的步骤。
6.如权利要求4所述的沿引导路径检索兴趣点的方法，其特征在于，所述的步骤C中，包括以下步骤：
C1：根据兴趣点检索范围，依次确定离当前行车位置最近、且未检索过的路段内的兴趣点检索范围为当前检索范围；执行步骤C2，当所述的兴趣点检索范围所覆盖的所有路段都检索完成时，结束此次检索，显示检索得到的兴趣点；
C2：获得当前检索范围所覆盖的栅格，选择一个未检索过的栅格确定为当前检索栅格，执行步骤C3；当当前检索范围覆盖的所有的栅格都已检索完成时，执行步骤C1；
C3：检索过滤当前检索栅格内的兴趣点，记录栅格内所有与用户输入的兴趣点属性信息相匹配的兴趣点，重新执行步骤C2。
7.如权利要求6所述的沿引导路径检索兴趣点的方法，其特征在于，所述的导航系统中设有用于保存检索到的兴趣点的过滤结果集；所述的步骤C3中，将每个栅格中获得的兴趣点按先后顺序保存在过滤结果集中，当过滤结果集已满时，提前结束本次兴趣点的检索。
8.如权利要求1所述的沿引导路径检索兴趣点的方法，其特征在于，所述的步骤C之后，还包括以下步骤：
若当前的兴趣点检索范围内没有检索到符合要求的兴趣点，则扩大兴趣点检索范围，在扩大后的兴趣点检索范围内对未检索过的范围进行进一步检索。
9.一种使用了如权利要求1所述的沿引导路径检索兴趣点的方法的导航系统，包括：
沿引导路径进行兴趣点检索的兴趣点检索装置，其特征在于，所述的兴趣点检索装置包括：
参数获取模块，用于获取用户输入的兴趣点属性信息；所述兴趣点属性信息包括左侧搜索延伸距离、右侧搜索延伸距离的值、及沿路径前方搜索距离长度的值；
兴趣点检索范围生成模块，用于根据当前导航系统生成的引导路径计算兴趣点检索范围；依据从所述参数获取模块获得的左侧搜索延伸距离、右侧搜索延伸距离的值、沿路径前方搜索距离长度的值生成兴趣点检索范围；
兴趣点过滤模块，兴趣点过滤模块和兴趣点检索范围生成模块相连接，用于在兴趣点检索范围生成模块计算得到的兴趣点检索范围内检索与参数获取模块获取的兴趣点属性信息相匹配的兴趣点。

沿引导路径检索兴趣点的方法及使用了此方法的导航系统\n技术领域\n[0001] 本发明涉及GPS导航技术领域，更具体的说，涉及一种沿引导路径检索兴趣点的方法及使用了此方法的导航系统。\n背景技术\n[0002] 目前，车用全球定位系统(Global Positioning System，GPS)是GPS导航重要应用方向之一。车用GPS导航系统的GPS天线接收来自环绕地球的24颗GPS卫星中的至少\n3颗所传递的数据信息，结合储存在车用导航终端内的电子地图，通过GPS卫星信号确定的位置坐标与此相匹配，确定导航对象在电子地图中的准确位置。\n[0003] 图1示出了现有的导航系统的结构组成：\n[0004] 所述的导航系统包括：扬声器1、存储装置2、输入装置3、声音输出装置4、显示装置5、分别控制存储装置2、输入装置3及声音输出装置4的控制装置6、和与控制装置6连接的GPS接收装置16。\n[0005] 所述的控制装置6为微机，如可采用掌上电脑、智能手机、车载终端等。其包括：用户接口控制模块7、地图数据管理模块8及导航模块9；导航模块9主要由导航控制模块10、地图显示模块11、路径引导模块12、路径搜索模块13、兴趣点检索装置14、自车位置检测模块15构成。\n[0006] 卡盘装置2可以对插入其中的记录有地图数据、控制程序数据等的记录媒体中的记录内容还原成数字数据，并送至送到控制装置6。其记录媒体可以采用例如安全数码卡(Secure Digital Card，SD)，闪存卡(TransFlash Card，TF)等。\n[0007] 输入装置3可使用按键、摇杆、旋钮或触摸板等。输入装置3用于输入用户的各种要求，将用户的输入信号送到控制装置6的用户接口控制模块7中。\n[0008] 声音输出装置4将控制装置6送来的声音数据转化为声音信号，送到扬声器1。扬声器1将声音输出装置4送来的声音信号转换成声音并输出，这样，扬声器1就可以配合控制装置6的需要，发出各种操作通知及路径引导的语音。\n[0009] 显示装置5可使用LCD(Liquid Crystal Display)液晶显示器或投影仪或CRT(Cathode Ray Tube)显示器，根据控制装置6送来的显示数据，显示其对应的图像。例如，显示装置5可以显示地图、自车位置标记、已规划路径及用户输入界面等。\n[0010] GPS接收装置16接收来自GPS卫星的信号，检测车辆的现在位置及移动方向，并将检测到的结果转换成协议数据，这些协议数据进一步被送到控制装置6的导航模块9内的自车位置检测模块15。\n[0011] 控制装置6的用户接口控制模块7接收输入装置3的输入，生成与输入所要求的内容对应的控制指令，送到导航模块9内的一个或多个子模块之中。此外，用户接口控制模块7响应控制指令，并把从导航模块9返回的处理结果，送到声音输出装置4、显示装置5之中。\n[0012] 控制装置6的地图数据管理模块8响应导航模块9的要求从卡盘装置2读出地图数据，这些地图数据中也含有用于图片引导用的数据内容。\n[0013] 导航模块9的导航控制模块10控制并调用导航模块9的其余子模块。\n[0014] 导航模块9的地图显示模块11根据从地图数据管理模块8读出的地图数据信息，生成地图显示用的显示数据，送到用户接口控制模块7。\n[0015] 导航模块9的路径引导模块12从地图数据处理模块8取得地图数据，对其进行路径诱导处理，并把诱导处理结果返回给地图数据管理模块11，以便于地图数据管理模块11进行预测读取。另还将诱导时的界面、导航语音等数据传送给用户接口控制模块7。\n[0016] 导航模块9的路径搜索模块13从地图数据管理模块8取得地图数据，并对其实行路径探索处理，并将路径探索结果返回路径引导模块12。\n[0017] 由于用户在驱车行驶途中会要找加油站加油或找宾馆住宿或找厕所等，用户会希望能直接在引导路径旁边的适当范围内找到这些场所。用户并不希望绕远去距离当前导航路径太远的地方，因此，这些兴趣点即使检测到也是没有意义的。\n[0018] 为了实现沿引导路径检索兴趣点的功能，导航模块9还包括兴趣点检索装置14；\n所述的兴趣点检索装置14从地图数据管理模块8取得待过滤数据，检索出输入装置3输入的兴趣点检索指令，将检索结果返回给地图数据管理模块8、地图显示模块11、路径引导模块12。\n[0019] 导航模块9的自车位置检测模块15将从GPS接收装置16得到的表示现在位置的数据，送到地图数据管理模块8、地图显示模块11、路径引导模块12。\n[0020] 现有的沿引导路径检索兴趣点的方法普遍存在效率低下的问题。\n[0021] 以中华人民共和国国家知识产权局在专利申请文献“导航仪在导航过程中检索沿引导路径的兴趣点的方法”(专利申请号为：CN200710021502.2；专利申请日为：2007年4月27日；公开号为：CN101046383A；以下简称专利文献1)中公开的一种导航仪在导航过程中检索沿引导路径的兴趣点的方法为例，其包括如下步骤：\n[0022] A、在沿预设引导路径导航过程中，导航仪的CPU单元接受用户通过触摸屏操控单元输入的所需的兴趣点的属性信息；\n[0023] B、CPU单元根据GPS接收器接收的GPS信号探测当前位置，然后读取地图数据库中的当前位置周边预设范围(如500m的范围)内的所有兴趣点；\n[0024] C、CPU单元从所述所有兴趣点中查找出与所需的兴趣点的属性信息相符且沿所述引导路径的兴趣点，并由触摸屏操控单元显示这些兴趣点。\n[0025] 专利文献1记载的方法首先把预设周边检索范围内的所有栅格内的兴趣点数据全部进行装载，再判断已装载的各兴趣点记录是否沿已规划路径分布来进行筛选。请参考附图2的情形，图中车标周围的圆圈为预设的周边检索范围；车标为一飞碟形的透白图标；\n普通路段为黑粗线；已规划路径行为路段比普通路段更粗，且为灰色，即车标前方的路段。\n使用专利文献1所述的技术进行沿路段进行搜索，需要对48个栅格内的兴趣点数据进行筛选排除(请参考附图3)，但实际上，有效的沿所述引导路径的目标兴趣点所在的栅格只有4个(请参考附图4)。其他进行了预读取的48-4＝44个栅格都是远离了当前的引导路径的，没有发挥实际效用的栅格，因此，在附图2的情形下，栅格有效读取命中率仅为：\n[0026] 4÷48≈8％\n[0027] 而若相符的兴趣点未查找到，CPU单元则将扩大预设范围进行搜索，而越是扩大搜索范围(如1500m)，由于其总是以当前行车位置为中心点进行搜索，搜索范围越大，其栅格有效读取命中率就越低。由于专利文献1所公开的技术方案的本质特征，即使在其它的一般情形下，也都会存在着这种原因造成的运行效率低下的情况。\n发明内容\n[0028] 为克服上述缺陷，本发明所要解决的技术问题是提供一种沿引导路径检索兴趣点的方法，及使用了此沿引导路径检索兴趣点的方法的导航系统。\n[0029] 本发明的目的是通过以下技术方案来实现的：\n[0030] 一种沿引导路径检索兴趣点的方法，包括以下步骤：\n[0031] A：接收用户输入的兴趣点属性信息；\n[0032] B：根据当前导航系统生成的引导路径计算兴趣点检索范围；\n[0033] C：根据步骤A用户输入的兴趣点属性信息在步骤B中计算得到的兴趣点检索范围中检索得到兴趣点。\n[0034] 所述的步骤B中，兴趣点检索范围包括左侧搜索延伸范围及右侧搜索延伸范围；\n所述左侧搜索延伸范围为沿引导路径向路径左侧延伸一预设的左侧搜索延伸距离所覆盖的范围；所述右侧搜索延伸距离为沿引导路径向路径右侧延伸一预设的右侧搜索延伸距离所覆盖的范围。这样的设置限定了沿当前引导路径向道路两侧延展搜索的范围。\n[0035] 所述的步骤A中，还包括接收用户输入的左侧搜索延伸距离及右侧搜索延伸距离，用于计算左侧搜索延伸范围及右侧搜索延伸范围的步骤。\n[0036] 所述的步骤B中，根据当前导航系统生成的引导路径计算兴趣点检索范围时，仅计算在当前行车位置前方的未行驶的导航路径所在路段的兴趣点检索范围。这样的设计不再考虑已经驶过的路线，减少了计算量；当然，也可以对在当前用户所在的整条路段进行检索，虽然可能检索到已经驶过的位置的兴趣点，可仍有可能会有用户因为其距离当前行车位置较近而更感兴趣的可能。\n[0037] 所述的步骤B中，根据当前导航系统生成的引导路径计算兴趣点检索范围时，仅计算沿着导航路径、在行车方向且距离当前行车位置一预设的搜索距离长度内所在路段的兴趣点检索范围。这样的设计不再检索离用户过远以至于没有意义的兴趣点，进一步提高了检索的执行效率，尤其适用于用户的目的地很远时所进行的沿导航路径检索兴趣点的情况。 \n[0038] 所述的步骤A中，还包括接收用户输入的搜索距离长度，用于计算兴趣点检索范围的步骤。\n[0039] 所述的步骤C中，包括以下步骤：\n[0040] C1：根据兴趣点检索范围，依次确定离当前行车位置最近、且未检索过的路段内的兴趣点检索范围为当前检索范围；执行步骤C2，当所述的兴趣点检索范围所覆盖的所有路段都检索完成时，结束此次检索，显示检索得到的兴趣点；\n[0041] C2：获得当前检索范围所覆盖的栅格，选择一个未检索过的栅格确定为当前检索栅格，执行步骤C3；当当前检索范围覆盖的所有的栅格都已检索完成时，执行步骤C1；\n[0042] C3：检索过滤当前检索栅格内的兴趣点，记录栅格内所有与用户输入的兴趣点属性信息相匹配的兴趣点，重新执行步骤C2。这样的设计优先检索离用户最近的区域的兴趣点，更加贴合用户的使用目的。\n[0043] 所述的导航系统中设有用于保存检索到的兴趣点的过滤结果集；所述的步骤C3中，将每个栅格中获得的兴趣点按先后顺序保存在过滤结果集中，当过滤结果集已满时，提前结束本次兴趣点的检索。这样的设置在保证了检索结果足够丰富的前提下，舍弃离用户较远的区域的兴趣点，尽可能的减少了系统计算的时间，进一步提高了周边检索的执行效率。\n[0044] 所述的步骤C之后，还包括以下步骤：\n[0045] 若当前的兴趣点检索范围内没有检索到符合要求的兴趣点，则扩大兴趣点检索范围，在扩大后的兴趣点检索范围内的对未检索过的范围进行进一步检索。这样的设置能尽可能的检索出用户希望检索到的兴趣点。\n[0046] 一种使用了上述沿引导路径检索兴趣点的方法的导航系统，包括：沿导航路径进行兴趣点检索的兴趣点检索装置，其中，所述的兴趣点检索装置包括：\n[0047] 参数获取模块，用户获取用户输入的兴趣点属性信息；\n[0048] 兴趣点检索范围生成模块，用于根据当前导航系统生成的引导路径计算兴趣点检索范围；\n[0049] 兴趣点过滤模块，参数获取模块和兴趣点检索范围生成模块相连接，用于在兴趣点检索范围生成模块计算得到的兴趣点检索范围内检索与参数获取模块获取的兴趣点属性信息相匹配的兴趣点。\n[0050] 在远离引导路径的地区范围进行兴趣点的检索是没有意义的，因为即使在此范围内我们检索到了与用户输入的兴趣点属性信息相匹配的兴趣点，也因为兴趣点所在地点不在我们希望的引导路径周边的兴趣点检索范围内而被过滤掉；而本发明由于先根据导航系统生成的引导路径确定要检索的兴趣点所在的兴趣点检索范围，再读取此兴趣点检索范围内的兴趣点，进行兴趣点的检索，对兴趣点检索范围以外的区域不予检索，因此，显著的降低了系统资源的消耗，大大提高了周边检索的执行效率，减少了用户的等待时间。\n附图说明\n[0051] 图1是现有技术中导航系统的结构图；\n[0052] 图2是现有技术的一个行车情形示意图；\n[0053] 图3是现有技术中在图2情形下需要预读取的栅格范围的示意图；\n[0054] 图4是现有技术中在图2情形下有效的栅格范围示意图；\n[0055] 图5是本发明实施例中沿导航路径寻找各组成路段的示意图；\n[0056] 图6是本发明实施例中沿导航路径的各组成路段向两侧延伸得到左侧搜索延伸范围及右侧搜索延伸范围的示意图；\n[0057] 图7是本发明实施例中沿导航路径的各组成路段向两侧延伸后所涉及到的栅格的示意图；\n[0058] 图8是本发明实施例中导航系统的兴趣点检索装置的功能框图；\n[0059] 图9是本发明实施例的处理流程图。\n具体实施方式\n[0060] 下面结合附图和较佳的实施例对本发明作进一步说明。\n[0061] 本发明的主要构思为：先根据当前导航系统生成的引导路径计算兴趣点检索范围；再在这计算得到的兴趣点检索范围内对兴趣点进行检索。在确定了有效的兴趣点检索范围后，再进行兴趣点检索，有效的提高了检索的命中率，加快了计算的速度。\n[0062] 其中，兴趣点检索范围包括左侧搜索延伸范围及右侧搜索延伸范围；所述左侧搜索延伸范围为沿引导路径向路径左侧延伸一预设的左侧搜索延伸距离(即附图6中的len1)所覆盖的范围；所述右侧搜索延伸距离为沿引导路径向路径右侧延伸一预设的右侧搜索延伸距离(即附图6中的len2)所覆盖的范围。位于左侧搜索延伸范围内的兴趣点，它们与已规划路径的最短距离，都会小于预设的左侧搜索延伸距离；位于右侧搜索延伸范围内的兴趣点，它们与已规划路径的最短距离，都会小于预设的右侧搜索延伸距离。\n[0063] 路径左侧搜索延伸距离与路径右侧搜索延伸距离之所以要各自独立地设置，是因为每一个地区的交通规则都会有一个确定的侧行方向，例如中华人民共和国的交通规则规定靠右行驶，导致向右转弯比向左转弯容易，到达右边的兴趣点也比到达左边的兴趣点容易。因此，在使用实践中，路径左侧搜索延伸距离可以设置成100米，路径右侧搜索延伸距离可以设置成200米，以适应这种实际特点。\n[0064] 本实施例使用的正是上述的经验值。但是，本领域的技术人员很容易就可以根据不同的地区或不同目标消费人群的爱好特点，把上述两个搜索延伸范围设置成不同值，或者通过实现一人机交互界面，由用户随时调整。如果不希望搜索某一侧的兴趣点，则可以通过把该侧的延伸距离设置为零来达到这个目的。\n[0065] 另外，兴趣点检索范围的大小还可以通过预设的搜索距离长度来控制，即当根据当前导航系统生成的引导路径计算兴趣点检索范围时，仅计算沿着导航路径、在行车方向且距离当前行车位置一预设的搜索距离长度内所在路段的兴趣点检索范围。考虑在行车途中进行周边检索时，检索到的兴趣点不应该太远，因此，本实施例采用了前方10千米作为沿路径前方搜索的最长距离长度。但是，本领域的技术人员很容易就可以根据不同的地区或不同目标消费人群的爱好特点，把上述的沿路径前方搜索距离长度设置成不同值，或者通过实现一人机交互界面，由用户随时调整。\n[0066] 由于在本实施例中，将导航地图划分为若干个紧密排列的栅格，每个栅格的宽与高一致，具有确定的长度，以及确定的地理位置。周边兴趣点数据都是按照其所在地理位置分别存放在这些栅格之中，因此，可以按照由近及远的顺序依次对落在兴趣点检索范围内的栅格一个个的检索，针对每个栅格内的兴趣点分析过滤得到与用户输入的兴趣点属性信息相匹配的兴趣点。\n[0067] 如附图5所示，已规划的引导路径，由多个首尾相连的路段(由链路Link表示)组成。其中，当前行车位置或已规划的引导路径的结束终点很有可能是落在链路的两个端点之间的(例如附图5的车标A点，落在链路BL即link1之间)，这时，将当前行车位置到下一个链路AB段也作为一个独立的链路，由图中可见，已规划的引导路径由AB链路、BC链路等组成。\n[0068] 在检索兴趣点时，先获取从当前行车位置前方的第一个路段(链路AB段即图中的link2)的兴趣点检索范围(包括左侧搜索延伸范围及右侧搜索延伸范围)所覆盖的栅格；\n只要当前栅格有一部分落入左侧搜索延伸范围或右侧搜索延伸范围，当前栅格就算是为兴趣点搜索范围所覆盖；依照一定的顺序依次检索每个栅格中所包含的兴趣点是否是与用户输入的兴趣点属性信息相匹配，保存记录所有相匹配的兴趣点，直至将当前路段内的兴趣点检索范围所覆盖的所有栅格全部一一检索完成。当检索完第一个路段内的兴趣段检索范围后，同样，继续检索与第一个路段相邻接的第二个路段内(链路BC段图中的link3)的兴趣点检索范围所覆盖的栅格；再依次检索每个栅格内的兴趣点；就这样依次检索已规划的引导路径中的每个路段内的兴趣点检索范围所覆盖的栅格内的兴趣点，直至到达已规划的引导路径的终点，或到达由预设的搜索距离长度所确定的搜索终点。\n[0069] 将已规划的引导路径中涉及到的路段链路按车辆行经顺序由先到后进行排列，将沿路径前方的预设的搜索距离长度依次减去各个路段链路的长度，最终会到达已规划的引导路径终点。当引导路径的长处超过搜索距离长度时，该沿路径前方的搜索距离长度会被减尽，提前到达搜索终点。在沿路径前方的搜索距离长度被减尽的情形下，有可能出现最后一节路段链路的长度有剩余的情形。例如，沿路径前方搜索距离已被减至100米，接下来的一节链路有1000米，那么，该节链路只需用掉100米，沿路径前方搜索距离就已全部被减掉，这样，最后那节进行周边检索的链路只有100米，而非1000米。这种情况类似于附图5的完整链路LB与部分链路AB的情形，并且是刚好相反的过程。\n[0070] 在附图6中，因为len1，len2的确定，从而可以确定出路径周边的兴趣点检索范围。例如AB链路的右侧搜索延伸范围为多边形AMNB。因为A点在链路LA之上，此时，角度∠LAM被设置为直角。另外，例如链路AB与链路BC都在参与沿路径周边检索的情形下，图中的角度∠ABD被设置成等于角度∠DBC，角度∠CBE被设置成等于角度∠EBA。其他链路的左右两侧的搜索延伸范围情况依次类推。\n[0071] 对每一个已确定的某链路一侧的搜索延伸范围，例如附图6的链路AB的右侧搜索延伸范围AMNB，也就可以确定所涉及到的栅格。对每一个覆盖范围内的栅格，读取它的兴趣点记录集合，对集合中的各记录使用常规过滤条件(例如兴趣点的分类)进行过滤，并判断它是否落入某链路一侧的覆盖范围之内。符合上面两方面条件的记录即为用户希望检索到的记录。\n[0072] 导航系统中通过兴趣点检索装置对沿导航路径进行兴趣点检索。如图8所示，所述的兴趣点检索装置包括：\n[0073] 参数获取模块100，用于获取用户输入的兴趣点属性信息，左侧搜索延伸距离、右侧搜索延伸距离的值、及沿路径前方搜索距离长度的值；参数可以从人机交互界面获得，而左侧搜索延伸距离、右侧搜索延伸距离的值、沿路径前方搜索距离长度也可以为一预设在兴趣点检索装置内部的预定的值；\n[0074] 兴趣点检索范围生成模块101，与参数获取模块100连接，用于根据导航系统生成的引导路径，依据上述从参数获取模块100获得左侧搜索延伸距离、右侧搜索延伸距离的值、沿路径前方搜索距离长度的值生成兴趣点检索范围；\n[0075] 兴趣点过滤模块，与兴趣点检索范围生成模块101相连接，包括以下模块：\n[0076] 剩余未搜索链路判断模块102，用于根据兴趣点检索范围生成模块101生成的兴趣点检索范围，判断在路径前方搜索距离内是否还有未搜索路段链路(Link)；\n[0077] 下一链路确定模块103，用于确定下一个还没有进行搜索的路段链路的两端端点地理位置坐标；其中获取未搜索路段链路是按车辆按预定路径行驶经过的先后顺序从先至近逐个获取的；\n[0078] 路段链路两侧栅格获取模块104，用于确定当前处理路段链路的左侧、右侧搜索延伸范围多边形，并求得与此范围相交的栅格；\n[0079] 剩余未处理栅格判断模块105，用于判断是否还有相交栅格尚未进行兴趣点搜索处理；\n[0080] 栅格内兴趣点数据集合读取模块106，用于读取下一个未处理栅格的兴趣点记录集合；\n[0081] 剩余未过滤记录判断模块107，用于判断已读取的当前正在处理栅格的兴趣点记录集合中是否还有兴趣点记录没有进行过滤操作；\n[0082] 兴趣点记录过滤判断模块108，用于对兴趣点记录进行过滤；过滤条件包括两个方面，一方面是常规过滤条件(例如兴趣点记录的分类是否是用户期望的，兴趣点属性信息是否与用户输入的属性信息相匹配)，另一方面是该兴趣点记录是否落在此路段链路的左侧搜索延伸范围多边形或右侧搜索延伸范围多边形内；\n[0083] 过滤结果集维护模块109，用于记录符合条件的兴趣点记录，将这些兴趣点记录置于过滤结果集中；\n[0084] 过滤结果集已满判断模块110，用于判断过滤结果集是否已满；本实施例中，考虑到设备终端的内存容量是有限的，以及太多的待选兴趣点并没有大的实用意义，因此，本实施例使用了100作为过滤结果集的最大容量，一旦加入过滤结果集的兴趣点记录达到100个，即判断过滤结果集为已满；当得知过滤结果集已满时，即停止兴趣点的检索；\n[0085] 过滤结果集展示模块111，用于在检索结束时或过滤结果集已满时，把过滤结果集中的记录数据通过人机交互界面(例如屏幕输出，或通过语音输出)进行展示，以供用户进一步利用。在用户得到当前的兴趣点后，可对兴趣点进行一系列的后续操作，如：设为新的目的地、加入地址簿等操作。\n[0086] 附图9是本实施例的沿路径兴趣点检索装置的实际处理方法的流程图。其处理过程如下：\n[0087] 步骤S101：参数获取模块100获取路径左侧搜索延伸距离及右侧搜索延伸距离的值及沿路径前方的搜索距离长度的值；\n[0088] 步骤S102：剩余未搜索链路判断模块102判断路径前方搜索距离内是否还有未进行搜索处理的路段链路(Link)；如是，执行步骤S103，否则执行步骤S111；\n[0089] 步骤S103：下一链路确定模块103确定下一需进行搜索处理的链路的两端点地理位置数据；\n[0090] 步骤S104：链路两侧栅格获取模块104确定待处理链路的两侧的搜索延伸范围多边形，并进一步获取与左侧搜索延伸范围多边形及右侧搜索延伸范围多边形相交的栅格；\n[0091] 步骤S105：剩余未处理栅格判断模块105判断前一步骤所取得的栅格中是否还有未处理的栅格；如是，执行步骤S106，否则返回步骤S102继续执行；\n[0092] 步骤S106：栅格内兴趣点数据集合读取模块106获取下一未处理栅格的兴趣点数据集合；\n[0093] 步骤S107：剩余未过滤记录判断模块S107判断前一步骤获取得到的兴趣点数据集合中是否还有未过滤记录；如是，执行步骤S108，否则返回执行步骤S105；\n[0094] 步骤S108：记录过滤判断模块108判断下一待过滤记录是否符合过滤条件；判断的条件有两个，一类是常规条件，例如兴趣点的分类；另一类是判断该兴趣点的地理坐标是否落该链路的两侧延伸覆盖范围多边形中；如果本步骤判断成立，执行步骤S109：否则返回执行步骤S107；\n[0095] 步骤S109：过滤结果集维护模块109将符合过滤条件的记录加入到过滤结果集中；\n[0096] 步骤S110：过滤结果集已满判断模块110判断过滤结果集是否已满，如是，执行步骤S111，否则返回执行步骤S107；\n[0097] 步骤S111：过滤结果集展示模块111对过滤结果集进行展示，供用户进一步选用过滤结果集中的记录。\n[0098] 其中，若当前的兴趣点检索范围内没有检索到符合要求的兴趣点，则还可以扩大兴趣点检索范围，如，扩大设置的左侧搜索延伸距离及右侧搜索延伸距离的值，或扩大搜索距离长度的值，并在扩大后的兴趣点检索范围内的对未检索过的范围进行进一步检索。\n[0099] 本发明由于先根据导航系统生成的引导路径确定要检索的兴趣点所在的兴趣点检索范围，判断栅格是否与引导路径路段链路的左侧搜索延伸范围多边形及右侧搜索延伸范围多边形是否相交，相交的栅格才进行读取过滤，对兴趣点检索范围以外的区域不予检索，因此，显著的提高了栅格有效命中率，降低了系统资源的消耗，大大提高了周边检索的执行效率，减少了用户的等待时间。\n[0100] 以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。