兴趣点检索方法及装置

1.一种兴趣点检索方法，其包括以下步骤：
1)读取图幅中兴趣点的数据；
2)计算周边范围兴趣点和周边距离；
3)用固定结点个数n的周边二叉排序树筛选符合要求的兴趣点，所述周边二叉树排序树是指二叉树按中序遍历后，所得到的结点按周边距离由小到大有序排列的周边二叉树，且该周边二叉树保存有左子树、右子树、父亲结点和周边距离；
4)把符合要求的兴趣点取出来。
2.如权利要求1所述的兴趣点检索方法，其特征在于：
所有的兴趣点的数据的经度和纬度放在一起存储，兴趣点的其他数据放在其后面一起存储。
3.如权利要求1所述的兴趣点检索方法，其特征在于：
在计算周边距离前，判断周边范围兴趣点是不是在一个矩形范围内；如果是，就可判断此兴趣点在要查找的范围内；如果不是，就可判断此兴趣点不在要查找的范围内。
4.如权利要求3所述的兴趣点检索方法，其特征在于：
所述矩形范围在经度和纬度上的范围分别为A*B和A*C，其中A为最大允许长度，B为经度系数，C为纬度系数。
5.如权利要求4所述的兴趣点检索方法，其特征在于：其中最大允许长度A为5公里。
6.如权利要求4或5所述的兴趣点检索方法，其特征在于：如果当前位置兴趣点与其他兴趣点的经度与经度相减、纬度与纬度相减分别小于A*B、A*C，则该兴趣点在所述矩形范围内，否则，该兴趣点不在所述矩形范围内。
7.如权利要求1所述的兴趣点检索方法，其特征在于：
假如固定结点个数的周边二叉排序树中结点个数小于n，则按二叉排序树插入新结点的方法插入此结点；但若此插入结点的周边距离等于固定结点个数的周边二叉排序树中某结点A的周边距离，则此插入结点作为结点A的左子结点插入；而结点A原来的左子结点放在插入结点的左子结点上；
假如固定结点个数的周边二叉排序树中结点个数等于n；比较此新结点与周边距离最大的结点即保存起来的最右边的结点，看哪个周边距离大；若此新结点大，则跳过，继续比较下一个兴趣点；若此新结点小，则删掉固定结点个数的周边二叉排序树中最右边的结点M，然后把新结点的值赋给已删二叉树中最右边的结点M，再把已删二叉树中最右边的结点M按二叉排序树插入新结点的方法插入；后把新的二叉树最右边即周边距离最大的结点保存起来；赋给结点M；继续比较下一个兴趣点；若此新结点的周边距离等于固定结点个数的周边二叉排序树中某结点B的周边距离，则删掉固定结点个数的周边二叉排序树中最右边的结点M，然后把新结点的值赋给已删二叉树中最右边的结点M，把此已删二叉树中最右边的结点M作为结点B的左子结点插入，而结点B原来的左子结点放在此已删二叉树中最右边的结点M的左子结点上；后把新的二叉树最右边即周边距离最大的结点保存起来；赋给结点M；继续比较下一个兴趣点。
8.如权利要求7所述的兴趣点检索方法，其特征在于：
n的取值为50-200。
9.如权利要求7所述的兴趣点检索方法，其特征在于：
在把符合要求的兴趣点取出来之前，通过二叉排序树的中序遍历来得到符合要求的兴趣点。
10.一种兴趣点检索装置，其包括：存储单元、中心计算单元、结果输出单元；存储单元存放图幅中的兴趣点数据，中心计算单元读取存储单元中的兴趣点数据，计算周边范围兴趣点和周边距离，然后用固定结点个数n的周边二叉排序树筛选符合要求的兴趣点，最后把符合要求的兴趣点取出来，输出到结果输出单元，所述周边二叉树排序树是指二叉树按中序遍历后，所得到的结点按周边距离由小到大有序排列的周边二叉树，且该周边二叉树保存有左子树、右子树、父亲结点和周边距离。
11.如权利要求10所述的兴趣点检索装置，其特征在于：所有的兴趣点的数据的经度和纬度放在一起存储，兴趣点的其他数据放在其后面一起存储。
12.如权利要求11所述的兴趣点检索装置，其特征在于：在计算周边距离前，判断周边范围兴趣点是不是在一个矩形范围内；如果是，就可判断此兴趣点在要查找的范围内；如果不是，就可判断此兴趣点不在要查找的范围内。
13.如权利要求12所述的兴趣点检索装置，其特征在于：
所述矩形范围在经度和纬度上的范围分别为A*B和A*C，其中A为最大允许长度，B为经度系数，C为纬度系数。
14.如权利要求13所述的兴趣点检索装置，其特征在于：其中最大允许长度A为5公里。
15.如权利要求13或14所述的兴趣点检索装置，其特征在于：如果当前位置兴趣点与其他兴趣点的经度与经度相减、纬度与纬度相减分别小于A*B、A*C，则该兴趣点在所述矩形范围内，否则，该兴趣点不在所述矩形范围内。
16.如权利要求10所述的兴趣点检索装置，其特征在于：
假如固定结点个数的周边二叉排序树中结点个数小于n，则按二叉排序树插入新结点的方法插入此结点；但若此插入结点的周边距离等于固定结点个数的周边二叉排序树中某结点A的周边距离，则此插入结点作为结点A的左子结点插入；而结点A原来的左子结点放在插入结点的左子结点上；
假如固定结点个数的周边二叉排序树中结点个数等于n；比较此新结点与周边距离最大的结点即保存起来的最右边的结点，看哪个周边距离大；若此新结点大，则跳过，继续比较下一个兴趣点；若此新结点小，则删掉固定结点个数的周边二叉排序树中最右边的结点M，然后把新结点的值赋给已删二叉树中最右边的结点M，再把已删二叉树中最右边的结点M按二叉排序树插入新结点的方法插入；后把新的二叉树最右边即周边距离最大的结点保存起来；赋给结点M；继续比较下一个兴趣点；若此新结点的周边距离等于固定结点个数的周边二叉排序树中某结点B的周边距离，则删掉固定结点个数的周边二叉排序树中最右边的结点M，然后把新结点的值赋给已删二叉树中最右边的结点M，把此已删二叉树中最右边的结点M作为结点B的左子结点插入，而结点B原来的左子结点放在此已删二叉树中最右边的结点M的左子结点上；后把新的二叉树最右边即周边距离最大的结点保存起来；赋给结点M；继续比较下一个兴趣点。
17.如权利要求16所述的兴趣点检索装置，其特征在于：
n的取值为50-200。
18.如权利要求16所述的兴趣点检索装置，其特征在于：
在把符合要求的兴趣点取出来之前，通过二叉排序树的中序遍历来得到符合要求的兴趣点。

兴趣点检索方法及装置\n技术领域\n[0001] 本发明涉及导航地理信息系统，具体涉及一种兴趣点(point of interest)检索方法和兴趣点检索装置。\n背景技术\n[0002] 手机作为一种新型导航终端，得到了越来越广泛的应用，兴趣点检索是手机导航一个很重要的应用。用户如需查找当前位置周边的兴趣点，只需输入兴趣点类型或名称，然后，触发导航终端启动兴趣点检索方法，查找距离用户当前位置最近的并且符合检索条件的兴趣点。\n[0003] 关于兴趣点检索方法，现有技术采取的是根据用户输入的兴趣点类型和用户当前的经度/纬度，由经度/纬度计算出用户输入的当前点所在的图幅及其旁边的几个图幅，读取这些图幅中的兴趣点数据，计算周边距离，若周边距离小于预置的周边距离，如5公里，则是符合检索条件的兴趣点，反之则为不符合检索条件的兴趣点，对符合检索条件的兴趣点进行排序，现有技术采用排序方法包括：边插边排方法或符合检索条件的兴趣点达到一定数量进行一次排序的方法。\n[0004] 对于当前的手机终端，由于处理器速度较慢，内存较小，现有技术存在以下缺点：\n[0005] 1)要对当前城市的一个或几个图幅的所有数据即兴趣点进行比较查找，而一个图幅包含几万个数据，故读取的数据量非常大。而且，图幅中的每个兴趣点数据点都要计算周边距离，而计算周边距离的速度相对较慢，所以耗费的时间较长。\n[0006] 2)在周边查找时，用于计算两个兴趣点周边距离的时间比较长。\n[0007] 3)在周边查找时，查找到的符合结果的数据要按周边距离由小到大排序。\n[0008] 4)由于是动态分配内存，系统和别的地方也要共用内存，势必影响速度。\n发明内容\n[0009] 本发明旨在解决上述现有技术中的问题，提出一种能够快速检索兴趣点的方法。\n[0010] 本发明的第二个目的是提供一种兴趣点检索装置。\n[0011] 为了解决上述问题并达到上述目的，本发明的兴趣点检索方法包括以下步骤：1)读取图幅中的兴趣点的数据；2)计算周边范围兴趣点和周边距离；3)用固定结点个数n的周边二叉排序树筛选符合要求的兴趣点，所述周边二叉树排序树是指二叉树按中序遍历后，所得到的结点按周边距离由小到大有序排列的周边二叉树，且该周边二叉树保存有左子树、右子树、父亲结点和周边距离；4)把符合要求的兴趣点取出来。\n[0012] 在本发明的兴趣点检索方法中，所有兴趣点的经度和纬度放在一起存储，兴趣点的其余数据放在它的后面一起存储。\n[0013] 这样就能把兴趣点的详细数据中的经度和纬度与其余数据分开处理，每次计算周边距离和周边范围兴趣点时，只需读出经度和纬度，而不需要读出其它数据，从而缩短读数据的时间。\n[0014] 在本发明的兴趣点检索方法中，在计算周边距离前，判断周边范围兴趣点是不是在一个矩形范围内。矩形范围在经度和纬度上的范围分别为A*B和A*C，其中A为最大允许长度，B为经度系数，C为纬度系数。如不是，就可判断此兴趣点不在要查找的范围内。如果当前位置兴趣点与其他兴趣点的经度与经度相减、纬度与纬度相减分别小于A*B、A*C，则该兴趣点在矩形范围内，否则，该兴趣点不在所述矩形范围内。\n[0015] 这样，对于不是矩形范围内的兴趣点，不需要再计算周边距离，从而减少了计算周边距离的时间。\n[0016] 在本发明的兴趣点检索方法中，引入固定结点个数n的周边二叉排序树，且二叉排序树中所有结点的周边距离总是最小的前面n个。并把最右边即周边距离最大的结点保存起来。这样就可用如下步骤降低排序的时间。\n[0017] 步骤1：假如固定结点个数的周边二叉排序树中结点个数小于n，(n为固定结点个数的周边二叉排序树的固定结点个数即二叉排序树结点个数的最大值)，则按二叉排序树插入新结点的方法插入此结点。但若此插入结点的周边距离等于固定结点个数的周边二叉排序树中某结点A的周边距离，则此插入结点作为结点A的左子结点插入。而结点A原来的左子结点放在插入结点的左子结点上。\n[0018] 步骤2：假如固定结点个数的周边二叉排序树中结点个数等于n，(n为固定结点个数的周边二叉排序树的固定结点个数即二叉排序树结点个数的最大值)。比较此新结点与周边距离最大的结点即保存起来的最右边的结点，看哪个周边距离大；若此新结点大，则跳过，继续比较下一个兴趣点。若此新结点小，则删掉固定结点个数的周边二叉排序树中最右边的结点M，然后把新结点的值赋给已删二叉树中最右边的结点M，再把已删二叉树中最右边的结点M按二叉排序树插入新结点的方法插入；后把新的二叉树最右边即周边距离最大的结点保存起来；赋给结点M。继续比较下一个兴趣点。若此新结点的周边距离等于固定结点个数的周边二叉排序树中某结点B的周边距离，则删掉固定结点个数的周边二叉排序树中最右边的结点M，然后把新结点的值赋给已删二叉树中最右边的结点M，把此已删二叉树中最右边的结点M作为结点B的左子结点插入，而结点B原来的左子结点放在此已删二叉树中最右边的结点M的左子结点上；后把新的二叉树最右边即周边距离最大的结点保存起来；赋给结点M。继续比较下一个兴趣点。\n[0019] 由于固定结点个数的周边二叉排序树固定使用n个结点，即只用数组[n]；每个数组成员的大小为固定结点个数的周边二叉排序树的结点大小。结点的左子树，右子树，父亲结点均用下标1到n之一表示；实现内存的自行管理；避免因内存太小，频繁动态分配而造成的速度慢的问题。从而总体上提高速度。\n[0020] 最后通过二叉排序树的中序遍历即可得到结果。\n[0021] 因为手机的屏幕较小，其处理器速度慢且内存小，优选地，n取值为50到200。\n[0022] 上述方法中，读数据：作用是把图幅中的兴趣点经度和纬度读出来，用于计算周边范围兴趣点和周边距离。计算周边范围兴趣点和周边距离：作用是判断给定任一兴趣点是否为想要的周边兴趣点。用固定结点个数的周边二叉排序树筛选符合要求的兴趣点：作用是对符合周边距离要求的即周边距离小于一定数值的兴趣点是否应留在周边二叉排序树内。当所有兴趣点数据都处理完后，最终留在周边二叉排序树内的兴趣点就是所要得到的兴趣点。把符合要求的兴趣点取出来：作用是把周边二叉排序树内的兴趣点取出来，转换成兴趣点的详细数据。\n[0023] 本发明进一步提出一种兴趣点检索装置，其包括：存储单元、中心计算单元、结果输出单元；存储单元存放着图幅中的兴趣点数据，中心计算单元读取存储单元中的兴趣点数据，计算周边范围兴趣点和周边距离，用固定结点个数n的周边二叉排序树筛选符合要求的兴趣点，最后把符合要求的兴趣点取出来，输出到结果输出单元，所述周边二叉树排序树是指二叉树按中序遍历后，所得到的结点按周边距离由小到大有序排列的周边二叉树，且该周边二叉树保存有左子树、右子树、父亲结点和周边距离。\n[0024] 通过上述方法和装置，可以减小每个兴趣点的计算时间、两个兴趣点间周边距离的计算时间、以及符合结果的兴趣点点查找时间，从而大大减小了检索时间。另外，该方法实现了内存的自行管理，避免因终端内存太小、频繁分配而造成的速度慢的问题。\n附图说明\n[0025] 图1为本发明的兴趣点检索方法的步骤流程图；\n[0026] 图2a-图2d是依照本发明的兴趣点检索方法的一个优选实施例的流程图。\n具体实施方式\n[0027] 从对说明本发明的主旨及其使用的优选实施例和附图的以下描述来看，[0028] 本发明的以上和其它目的、特点和优点将是显而易见的。\n[0029] 术语定义\n[0030] 距离：是指两个具有不同经度和纬度的点在平面直角坐标系中连接起来所形成的直线段长度。\n[0031] 周边距离：是指在汽车导航中汽车当前所在的兴趣点与周围任一确定的兴趣点之间的距离。\n[0032] 周边二叉树：是指二叉树中的结点保存有左子树，右子树，父亲结点和周边距离的二叉树。\n[0033] 周边二叉排序树：是指二叉树按中序遍历后，所得到的结点按周边距离由小到大有序排列的周边二叉树。\n[0034] 固定结点个数的周边二叉排序树：是指周边二叉排序树的结点数不超过固定结点个数(假定为n)；当周边二叉排序树的结点数超过n时，如要插入新结点，必须先把最右边的结点删掉；用此删掉结点作为新结点，赋给初值，然后按二叉排序树插入新结点的方法插入此新结点。若周边二叉排序树的结点数小于n时，按二叉排序树插入新结点的方法插入此新结点。\n[0035] 周边范围兴趣点：是指在平面直角坐标系中，与在汽车导航中汽车当前所在的兴趣点在水平和垂直方向上的长度都小于一定数值的兴趣点。\n[0036] 兴趣点的详细数据：是指兴趣点有关的所有数据。如经度、纬度、兴趣点名称、地址、简拼、城镇名、电话号码等。\n[0037] 图1是本发明实施例的主要步骤：\n[0038] (1)读取图幅中的兴趣点的数据，把兴趣点的经度和纬度读出来。\n[0039] (2)计算周边范围兴趣点和周边距离。\n[0040] (3)用固定结点个数的周边二叉排序树筛选符合要求兴趣点。\n[0041] (4)还有数据要处理，转到(1)。所有数据都读出来并处理完转到(5)。\n[0042] (5)用中序遍历把所有符合要求的兴趣点都取出来。\n[0043] 该实施例中用到的数据结构如下：\n[0044] 固定结点个数的周边二叉排序树中结点的数据结构\n[0045] \n[0046] \n[0047] 在该实施例中，用到多个变量，含义如下：\n[0048] #define n 50//固定结点个数的周边二叉排序树最大结点个数，优选地n为\n50-100，在该实施例中n取50；\n[0049] BinTreeStruct BTN[n+1]//BTN[n+1]为n+1个结点数组。BTN[0]不用；\n[0050] XB为数组BTN[n+1]下标值，为1到n；\n[0051] MAX_AROUND即周边距离最大值，为5000米；\n[0052] RR为固定结点个数的周边二叉排序树中最右边的点，即固定结点个数的周边二叉排序树中周边距离最大的结点；\n[0053] disTemp为周边范围POI点与汽车当前所在的POI点之间的周边距离；\n[0054] searchPos为临时变量。\n[0055] 图2a到图2d是筛选符合要求的兴趣点的具体实现。\n[0056] (1)各种数据的初始化；数组BTN初始化，大小为(n+1)，下标零不用，只用1到n作为二叉树模拟的下标，设周边距离最大值MAX_AROUND为5公里，令下标XB初值为1，设n为50。\n[0057] (2)A1：兴趣点的经度、纬度数据读完，把符合要求的兴趣点取出来并退出；否则读兴趣点的经度和纬度。\n[0058] (3)用经度和纬度范围分别为A*B和A*C矩形范围来判断是周边范围兴趣点吗？如果当前位置兴趣点与其他兴趣点的经度与经度相减、纬度与纬度相减分别小于A*B、A*C，则该兴趣点在矩形范围内，是周边范围兴趣点，否则，该兴趣点不在所述矩形范围内，不是周边范围兴趣点。其中A为最大允许长度为5公里，B为经度系数，C为纬度系数。\n[0059] (4)不是周边范围兴趣点，读下一个兴趣点，转到A1。是周边范围兴趣点，转到(5)。\n[0060] (5)计算周边范围兴趣点与汽车当前所在的兴趣点之间的周边距离disTemp。\n[0061] (6)判断周边距离disTemp是否小于周边距离最大值MAX_AROUND，比如，预置的五公里。\n[0062] (7)否，读下一个兴趣点，转到A1。是，转到(8)。\n[0063] (8)判断固定结点个数的周边二叉排序树是否为空，即判断根结点是否为零。\n[0064] (9)是，转到(10)。否，转到(11)。\n[0065] (10)根结点等于下标XB，数组第XB个值BTN[XB]的值为父亲结点为零；左子树为零；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。最右边的点即周边距离最大的结点RR为根节点。下标XB增一。(注：RR不属于BTN[XB]的值域范围)。读下一个兴趣点，转到A1。\n[0066] (11)下标XB是否大于等于(n+1)。\n[0067] (12)否，转到A4。是，转到(13)。\n[0068] (13)当前周边距离的值是否大于BTN[RR]的周边距离的值。RR为固定结点个数的周边二叉排序树中最右边的点，即固定结点个数的周边二叉排序树中周边距离最大的结点。\n[0069] (14)是，读下一个兴趣点，转到A1。否，转到(15)。\n[0070] (15)把根节点赋给searchPos，searchPos为临时变量。\n[0071] (16)A2：searchPos是否为叶子节点。\n[0072] (17)是，读下一个兴趣点，转到A1。否，转到(18)。\n[0073] (18)当前周边距离disTemp是否等于BTN[searchPos]的周边距离。\n[0074] (19)等于，转到(20)。不等于，转到(24)。\n[0075] (20)最右边的点即周边距离最大的结点RR是否为根节点。\n[0076] (21)是，转到(22)。否，转到(23)。\n[0077] (22)保存兴趣点地址给最右边的点即周边距离最大的结点RR中的兴趣点地址；\n转到下一个兴趣点；转向A1。\n[0078] (23)改变RR结点的结点关系，把它从二叉树中删去。数组第RR个值BTN[RR]的值为父亲结点为searchPos；左子树为searchPos的左子树；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。把RR插入到searchPos的左子树中；寻找最右边的点即周边距离最大的结点赋给RR结点。转到下一个兴趣点；转向A1。\n[0079] (24)当前周边距离是否小于BTN[searchPos]的周边距离。\n[0080] (25)否，转到A3。是，转到(26)。\n[0081] (26)BTN[searchPos]的左子树是否为零。\n[0082] (27)不是，转到(28)。是，转到(29)。\n[0083] (28)BTN[searchPos]的左子树赋给searchPos转向A2。\n[0084] (29)改变RR结点的结点关系，把它从二叉树中删去。数组第RR个值BTN[RR]的值为父亲结点为searchPos；左子树为零；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。把RR插入到searchPos的左子树中；寻找最右边的点即周边距离最大的结点赋给RR结点。转到下一个兴趣点；转向A1。\n[0085] (30)A3：BTN[searchPos]的右子树是否为零。\n[0086] (31)不为零，转到(32)。为零，转到(33)。\n[0087] (32)BTN[searchPos]的右子树赋给searchPos转向A2。\n[0088] (33)改变RR结点的结点关系，把它从二叉树中删去。数组第RR个值BTN[RR]的值为父亲结点为searchPos；左子树为零；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。把RR插入到searchPos的右子树中；寻找最右边的点即周边距离最大的结点赋给RR结点。转到下一个兴趣点；转向A1。\n[0089] (34)A4：把根节点赋给searchPos，searchPos为临时变量。\n[0090] (35)A5：searchPos是否为叶子节点。\n[0091] (36)是，读下一个兴趣点，转到A1。否，转到(37)。\n[0092] (37)当前周边距离是否等于BTN[searchPos]的周边距离。\n[0093] (38)等于，转到(39)。不等于，转到(40)。\n[0094] (39)数组第XB个值BTN[XB]的值为父亲结点为searchPos；左子树为searchPos的左子树；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。把XB插入到searchPos的左子树中；寻找最右边的点即周边距离最大的结点赋给RR结点。下标XB增一。转到下一个兴趣点；转向A1。\n[0095] (40)当前周边距离是否小于BTN[searchPos]的周边距离。\n[0096] (41)是，转到(42)。否，转到(43)。\n[0097] (42)BTN[searchPos]的左子树是否为零。\n[0098] (43)否，转到(44)。是，转到(45)。\n[0099] (44)BTN[searchPos]的左子树赋给searchPos转向A5。\n[0100] (45)数组第XB个值BTN[XB]的值为父亲结点为searchPos；左子树为零；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。把XB插入到searchPos的左子树中；\n寻找最右边的点即周边距离最大的结点赋给RR结点。下标XB增一。转到下一个兴趣点；\n转向A1。\n[0101] (46)BTN[searchPos]的右子树是否为零。\n[0102] (47)否，转到(48)。是，转到(49)。\n[0103] (48)BTN[searchPos]的右子树赋给searchPos转向A5。\n[0104] (49)数组第XB个值BTN[XB]的值为父亲结点为searchPos；左子树为零；右子树为零，保存当前周边距离的值；保存兴趣点的地址值。把XB插入到searchPos的右子树中；\n寻找最右边的点即周边距离最大的结点赋给RR结点。下标XB增一。转到下一个兴趣点；\n转向A1。\n[0105] 通过这些步骤，可以使周边查找与关键字索引查找在速度上达到同一个档次。而关键字索引查找在手机上的速度是快的。\n[0106] 本发明的兴趣点检索方法可以用在手机等移动终端上，使该移动终端成为一种兴趣点检索装置。移动终端包括存储单元、中心计算单元、结果输出单元；存储单元存放着图幅中的兴趣点数据，中心计算单元读取存储单元中的兴趣点数据，计算周边范围兴趣点和周边距离，用固定结点个数n的周边二叉排序树筛选符合要求的兴趣点，最后把符合要求的兴趣点取出来，输出到结果输出单元。\n[0107] 尽管已示出和描述了本发明的优选实施例，可以设想，本领域的技术人员可在所附权利要求的精神和范围内对本发明的进行各种修改。