建置空间数据库的方法与空间数据库之数据结构产品的制作方法
建置空间数据库的方法与空间数据库之数据结构产品的制作方法
【技术领域】
[0001]本发明是有关于一种数据结构产品，特别是指一种空间数据库之数据结构产品及其建置方法、应用方法。
【背景技术】
[0002]一般行车记录器可记录行车影像，以供日后纠纷举证或者违规检举时查阅。然而，大部分高速公路、快速道路四周景象无辨别性，因此难以从行车影像中辨识出车辆所在位置。
[0003]有关车辆所在位置的问题，目前市面上已出现可记录GPS坐标的行车记录器。但是就高速公路、快速道路的用路人来说，其熟悉的位置表示方式是例如某高速公路南下/北上几公里处(以下简称里程位置)，难以从GPS坐标转换为其熟悉的里程位置，因此使用上仍不方便。
【发明内容】
[0004]因此，本发明的目的，即在提供一种建置空间数据库的方法，该空间数据库供一行车记录装置使用，可有效率地显示及记录里程位置。
[0005]本发明的另一目的，在于提供一种空间数据库之数据结构产品，供行车记录装置应用，可有效率地显示及记录里程位置。
[0006]本发明的再一目的，在于提供一种行车记录装置，可利用前述空间数据库而有效率地显示及记录里程位置。
[0007]于是，本发明建置空间数据库的方法，由一计算机装置执行，包含:
(A)针对至少一道路建立多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；
针对该等兴趣点逐一地执行以下步骤，直到所有兴趣点皆处理完毕；
(B)依据该兴趣点的GPS坐标以及一预设插入原则，插入一树状数据结构的其中一叶节点中，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围；
(C)检查插入该兴趣点的该叶节点是否已超出预设的兴趣点笔数，若是则进行步骤(D);及
(D)依据一预设分割原则分割该叶节点。
[0008]较佳地，该步骤(B)的预设插入原则是，选择「在插入新的兴趣点后，叶节点的最小矩形需扩张的范围最小者」进行插入。
[0009]较佳地，该方法还包含步骤(D)之后的步骤(E):检查分割后的两个叶节点的父节点是否已超出预设的子节点数目，若是，则将该父节点中的子节点重新分配，成为两个具有最小矩形的父节点。进一步地，该方法还包含一步骤(D)之后的步骤(F):判断该步骤(D)进行分割的叶节点是否同时也是根节点，若否才执行步骤(E)，若是则建立一新的根节点，并将该步骤(D)分割得到的两个叶节点设定为该新的根节点的子节点。
[0010]较佳地，该步骤(A)所建立的该等兴趣点，内容还包括方位角，且该等兴趣点的方位角的建立方法包括以下子步骤:
(A1)读取一路网数据，该路网数据内容包括多个位置点，以及两两位置点构成的路网线段，且各该路网线段记载了有关行车方向的道路属性；
(A2)对每一兴趣点搜寻其最近的两个位置点Pn及Pn+1 ；
(A3)当该二位置点Pn、Pn+l所构成的路网线段的行车方向，与该路网线段的数化方向相同，则以该位置点Pn+1相对于该位置点Pn的角度作为该兴趣点的方位角，反之，则以该位置点Pn相对于该位置点Pn+1作为该兴趣点的方位角。
[0011]本发明空间数据库之数据结构产品，该空间数据库供一行车记录装置读取利用，并包含:
至少一道路的多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；及一树状数据结构，包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围；
当该行车记录装置接收一内容包含其GPS坐标的定位信息，读取并利用该空间数据库并执行以下步骤，
(a)找到对应其GPS坐标的叶节点，
(b)查询该叶节点中接近的兴趣点，及
(c)输出该兴趣点的道路名称及里程。
[0012]较佳地，该树状数据结构还包括一根节点，该叶节点为该根节点的子节点。当该行车记录装置接收该定位信息，执行的步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点；该步骤(b)是查询该叶节点中落于该目标矩形中的兴趣点。
[0013]更佳地，该树状数据结构中，该叶节点为该根节点间接的子节点。该行车记录装置执行的步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。
[0014]较佳地，每一兴趣点内容还包括方位角；该行车记录装置还依据陆续接收的定位信息判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(c)。
[0015]本发明行车记录装置，配合一空间数据库运作，该空间数据库包含至少一道路的多数个兴趣点及一树状数据结构，每一兴趣点内容包括道路名称、里程，及GPS坐标。该树状数据结构包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围。
[0016]该行车记录装置包含一接收一内容包含其GPS坐标的定位信息的卫星定位单元，及一处理器。
[0017]当该卫星定位单元接收一内容包含其GPS坐标的定位信息并传送给该处理器，该处理器读取并利用该空间数据库并执行以下步骤，
(a)找到对应其GPS坐标的叶节点，
(b)查询该叶节点中最接近的兴趣点，及 (c)输出该兴趣点的道路名称及里程。
[0018]较佳地,所述树状数据结构还包括一根节点，该叶节点为该根节点的子节点；该步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，及(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点。
[0019]更佳地，所述树状数据结构中，该叶节点为该根节点间接的子节点；该步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。
[0020]此外，该步骤(a2)是当下述任一条件成立，则判断两个矩形无相交:⑴其中一矩形的左缘坐标X值大于另一矩形的右缘坐标X值；(ii)其中一矩形的下缘坐标Y值大于另一矩形的上缘坐标Υ值。
[0021]较佳地，所述每一兴趣点内容还包括方位角；该处理器还依据该卫星定位单元陆续接收的定位信息，判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(c)。
[0022]本发明之功效在于建置了有关于道路里程的空间数据库，且该空间数据库的数据结构有助于行车记录装置有效率地找到所在位置的道路里程而予以显示及记录。
[0023]【【附图说明】】
本发明的其它特征及功效，将于参照图式的实施方式中清楚地呈现，其中:
图1是一方块图，说明本发明之行车记录器及其搭配之空间数据库的一种实施例；
图2是一流程图，说明本发明空间数据库的建置方法的一种实施例；
图3是一流程图，说明有关兴趣点的方位角的建立；
图4是一示意图，用于辅助说明有关兴趣点的方位角的建立；
图5是一流程图，说明应用该空间数据库的步骤；及图6是一示意图，用于辅助说明两矩形是否相交的条件。
[0024]【【具体实施方式】】
参阅图1，本发明之实施例是由一行车记录装置1搭配一空间数据库2运作。本发明所指行车记录装置1，可理解为任何可接收卫星定位讯号且 可对于行车相关信息进行记录的装置，本实施例是以安装于汽车且具有一处理器11、一卫星定位单元12及一影像录制单元13举例说明。该卫星定位单元12接收一内容包含其GPS坐标的定位信息，而该影像录制单元13用于录制行车过程的周遭影像。
[0025]本发明所指空间数据库2是指一种数据结构产品，可在网站、应用程序商店供下载而储存于该行车记录装置1的储存空间(图未示)，亦可储存于云端服务器的储存空间(图未示)，供行车记录装置1的处理器11实体连接或通讯连接而读取利用。
[0026]配合参阅图2，建置该空间数据库2的方法是由任何具有运算能力的计算机装置3执行，该计算机装置3例如为图资公司服务器或个人计算机。该方法包含以下步骤:
步骤S01—针对至少一道路建立多数个兴趣点(POI,point of interest),例如国道每
0.1公里建立一个兴趣点。每一兴趣点内容包括道路名称(例如1号国道)、里程(亦即几公里)、GPS坐标，及方位角(例如45度或180度，且定义正北为0度)。
[0027]参阅图3，本发明对于兴趣点的方位角，是利用以下方法流程建立。
[0028]步骤S11—读取一路网数据，该路网数据内容包括多个位置点，以及两两位置点构成的路网线段，且各该路网线段记载了有关行车方向的道路属性。
[0029]所谓路网数据包含的内容非常广泛，任何有关道路的信息都可能已经或在未来被纳入图资供应者的路网数据内。路网资料包含但不限于以下提及的项目:位置点、其坐标，及两两位置点构成的路网线段。有关于每个路网线段，还记载了它的位置与形状、路网线段的名称、所在的行政区、道路属性(车道数量、车道宽度、可以通行的方向、车道转弯限制、行车速限、允许行走的车辆种类等)、道路等级(国道、省道、县道、乡道、普通道路等)、道路功能(重要联信道路、一般道路、私人道路等)、道路材质(铺设道路、未铺设道路、碎石子路、鹅卵石路等)。
[0030]路网数据还包含两条以上的路网线段是透过哪一个位置点连接；某一路网线段上的车辆往某一位置点行进时，可以通往哪些路网线段及不能通往哪些路网线段。当许多的路网线段被集合起来，就成为路网资料。
[0031]步骤S12—如图4所示，对每一兴趣点搜寻其最近的两个位置点Pn及Pn+1。
[0032]步骤S13—接下来，判断该二位置点Pn、Pn+l所构成的路网线段的行车方向，与该路网线段的数化方向是否相同？所谓数化方向，是指该路网线段被数字化(digitized)时之线段方向，即由Pn往Pn+1之方向，以例如以45度、180度的形式记录(正北为0度)，此方向即为线段PnPn+1的数化方向。若大致相同(例如差值在10度内)，则进行步骤S14，以该位置点Pn+1相对于该位置点Pn的方位角作为该兴趣点的方位角，以图3举例来说，所谓该位置点Pn+1相对于该位置点Pn的方位角就是「Pn与正北之联机」及「Pn与Pn+1之联机」的夹角，为90度。反之,则进行步骤S15,以该位置点Pn相对于该位置点Pn+1作为该兴趣点的方位角。
[0033]再回到图2，针对该等兴趣点逐一地执行以下步骤，直到所有兴趣点皆处理完毕。
[0034]步骤S02—依据该兴趣点的GPS坐标以及一预设插入原则，插入一树状数据结构的其中一叶节点中。本实施例是以三层的树状数据结构简单举例说明，但当然不以此为限。本实施例之树状数据结构可看作倒挂的树型，包括一根节点(R)、以该根节点(R)做为父节点往下延伸的两个子节点(S)，及以各该子节点(S)作为父节点再往下延伸且没有再延伸子节点的叶节点(L)。
[0035]各该叶节点具有一由其所包含的兴趣点构成的最小矩形(Minimum BoundingRectangle,以下称MBR)范围；叶节点的父节点的MBR涵盖该叶节点甚至更多叶节点的所有兴趣点，因此是构成较大范围的MBR ;再往上的根节点则涵盖所有子节点的兴趣点。
[0036]本实施例所述预设插入原则是，选择「在插入新的兴趣点后，叶节点的MBR需扩张的范围最小者」进行插入。
[0037]步骤S03—检查插入该兴趣点的该叶节点是否已超出预设的兴趣点笔数，例如25笔，但不以此为限。若未超出，则进行步骤S04，往上更新父节点的MBR，直到根节点，且此兴趣点插入完成。若插入该兴趣点即超出预设笔数，例如26笔，则进行步骤S05。
[0038]步骤S05—依据一预设分割原则分割该叶节点。所述预设分割原则是，将该叶节点中的兴趣点重新分配，成为两个具有最小矩形的叶节点。
[0039]接下来，执行步骤S06判断该进行分割的叶节点是否同时也是根节点？若是(通常在建置空间数据库的初期)，则表示兴趣点的数据量已经增加到一定程度，可建立阶层，则执行步骤S07建立一新的根节点，并将前述分割得到的两个叶节点设定为该新的根节点的子节点，此兴趣点插入完成。
[0040]若前述进行分割的叶节点不是根节点，则执行步骤S08，检查分割后的两个叶节点的父节点是否已超出预设的子节点数目，例如10个，若是，例如分割后有11个子节点，则执行步骤S09将该父节点中的子节点重新分配，成为两个具有最小矩形的父节点。接着回到步骤S06，再次判断进行分割的父节点是否同时也是根节点？若是则应进一步建立阶层，则建立一新的根节点，并将前述分割得到的两个父节点设定为该新的根节点的子节点。
[0041]若父节点未超出预设子节点数目，则此兴趣点插入完成。擷取下一个兴趣点。
[0042]参阅图1及图5，当所有兴趣点皆插入完成，即完成该空间数据库2。当该行车记录装置1执行步骤S21，其卫星定位单元12接收一内容包含其GPS坐标的定位信息并传送至处理器11，处理器11读取并利用该空间数据库2而执行步骤S22~S29。
[0043]步骤S22—先设定一对应其GPS坐标的目标矩形；其尺寸视实际应用区域而异，例如为 0.3km X 0.2km。
[0044]步骤S23—接着，查询该树状数据结构中根节点的所有子节点，找出MBR与该目标矩形相交的子节点。本实施例是利用排除无相交的方式找出有相交者，具体来说，当下述任一条件成立，则判断两个矩形无相交:(i)其中一矩形的左缘坐标X值大于另一矩形的右缘坐标X值；(?)其中一矩形的下缘坐标Y值大于另一矩形的上缘坐标Y值。
[0045]再更具体来说，配合参阅图6，定义矩形A及B的左下角坐标与右上角坐标分别为(xaO, yaO)、(xal, yal)及(xbO, ybO)、(xbl, ybl)。当 xaO > xbl 或 xbO > xal 则无相交。当yaO > ybl或ybO > yal也无相交。
[0046]步骤S24—判断相交的子节点是否为叶节点，若是，即找到对应其GPS坐标的叶节点，接着进行步骤S25以下。若否，则执行步骤S29，针对相交的子节点往下进一步查询其子节点，找出MBR与该目标矩形相交的子节点，并回到步骤S24判断是否为叶节点，直到确认该子节点为叶节点。
[0047]步骤S25—查询该叶节点中落于该目标矩形中的兴趣点。若有兴趣点落于该目标矩形，例如「国一南下35.0k」、「国一南下35.1k」及「国一北上35.1k」三个兴趣点，则针对该等找到的兴趣点分别执行步骤S26确认方位，若无则表示附近无兴趣点，此笔定位信息对应的处理结束。但实作上不以此为限，若希望仍能有里程信息可输出，则亦可设计为:当无兴趣点落于该目标矩形，则求取该叶节点中所有Ρ0Ι进行S26及其接下来步骤的判断」，如同把目标矩形放大到跟叶节点MBR —样大的意思。如此一来，因为在步骤S27会筛选出最近者，所以搜寻结果不会「舍近求远」。
[0048]步骤S26—判断该兴趣点的方位角是否与该实际行车方向相符？在此须说明的是，该行车记录装置1还依据陆 续接收的定位信息判断一实际行车方向，本步骤需依据该实际行车方向进行判断，滤除搜寻结果中道路方向方位角与之相差超过例如正负20度之兴趣点，例如得到「国一南下35.0k」及「国一南下35.1k」。
[0049]步骤S27—针对行车方向相符的兴趣点，进一步筛选出最接近者，例如「国一南下35.lkjo
[0050]步骤S28—输出该兴趣点的道路名称及里程。所谓输出，例如显示于该行车记录装置1的显示屏幕(图未示)、以语音方式透过扬声器输出，及/或记录于内存(图未示)，藉此得以令人方便地了解车辆所在道路及其里程数。
[0051]综上所述，本发明建置了有关于道路里程的空间数据库2，且该空间数据库2的数据结构有别于一般图资的大量资料搜寻而耗时，有助于行车记录装置1有效率地找到所在位置的道路里程而予以显示及记录，故确实能达成本发明之目的。
[0052]以上所述，仅为本发明的【具体实施方式】，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。
【主权项】
1.一种建置空间数据库的方法，由一计算机装置执行，包含: (A)针对至少一道路建立多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标； 针对该等兴趣点逐一地执行以下步骤，直到所有兴趣点皆处理完毕； (B)依据该兴趣点的GPS坐标以及一预设插入原则，插入一树状数据结构的其中一叶节点中，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围； (C)检查插入该兴趣点的该叶节点是否已超出预设的兴趣点笔数，若是则进行步骤(D);及 (D)依据一预设分割原则分割该叶节点。2.如权利要求1所述的建置空间数据库的方法，其中，该步骤(B)的预设插入原则是，选择「在插入新的兴趣点后，叶节点的最小矩形需扩张的范围最小者」进行插入。3.如权利要求1所述的建置空间数据库的方法，其中，该步骤(D)的预设分割原则是，将该叶节点中的兴趣点重新分配，成为两个具有最小矩形的叶节点。4.如权利要求1所述的建置空间数据库的方法，还包含步骤(D)之后的步骤(E):检查分割后的两个叶节点的父节点是否已超出预设的子节点数目，若是，则将该父节点中的子节点重新分配，成为两个具有最小矩形的父节点。5.如权利要求4所述的建置空间数据库的方法，还包含一步骤(D)之后的步骤(F):判断该步骤(D)进行分割的叶节点是否同时也是根节点，若否才执行步骤(E)，若是则建立一新的根节点，并将该步骤⑶分割得到的两个叶节点设定为该新的根节点的子节点。6.如权利要求1至5中任一项所述的建置空间数据库的方法，其中，该步骤㈧所建立的该等兴趣点，内容还包括方位角，且该等兴趣点的方位角的建立方法包括以下子步骤: (A1)读取一路网数据，该路网数据内容包括多个位置点，以及两两位置点构成的路网线段，且各该路网线段记载了有关行车方向的道路属性； (A2)对每一兴趣点搜寻其最近的两个位置点Pn及Pn+1 ； (A3)当该二位置点Pn、Pn+l所构成的路网线段的行车方向，与该路网线段的数化方向相同，则以该位置点Pn+1相对于该位置点Pn的角度作为该兴趣点的方位角，反之，则以该位置点Pn相对于该位置点Pn+1作为该兴趣点的方位角。7.一种空间数据库之数据结构产品，该空间数据库供一行车记录装置读取利用，并包含: 至少一道路的多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；及 一树状数据结构，包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围； 当该行车记录装置接收一内容包含其GPS坐标的定位信息，读取并利用该空间数据库并执行以下步骤， (a)找到对应其GPS坐标的叶节点， (b)查询该叶节点中接近的兴趣点，及 (c)输出该兴趣点的道路名称及里程。8.如权利要求7所述的空间数据库之数据结构产品，其中，该树状数据结构还包括一根节点，该叶节点为该根节点的子节点； 当该行车记录装置接收该定位信息，执行的步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点；该步骤(b)是查询该叶节点中落于该目标矩形中的兴趣点。9.如权利要求8所述的空间数据库之数据结构产品，其中，该树状数据结构中，该叶节点为该根节点间接的子节点； 该行车记录装置执行的步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。10.如权利要求7至9中任一项所述的空间数据库之数据结构产品，其中，每一兴趣点内容还包括方位角；该行车记录装置还依据陆续接收的定位信息判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(C) ο11.一种行车记录装置，配合一空间数据库运作，该空间数据库包含至少一道路的多数个兴趣点及一树状数据结构，每一兴趣点内容包括道路名称、里程，及GPS坐标，该树状数据结构包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围，包含: 一卫星定位单元，接收一内容包含其GPS坐标的定位信息；及 一处理器； 当该卫星定位单元接收一内容包含其GPS坐标的定位信息并传送给该处理器，该处理器读取并利用该空间数据库并执行以下步骤， (a)找到对应其GPS坐标的叶节点， (b)查询该叶节点中最接近的兴趣点，及 (c)输出该兴趣点的道路名称及里程。12.如权利要求11所述的行车记录装置，其中，所述树状数据结构还包括一根节点，该叶节点为该根节点的子节点；该步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，及(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点。13.如权利要求12所述的行车记录装置，其中，所述树状数据结构中，该叶节点为该根节点间接的子节点；该步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。14.如权利要求12所述的行车记录装置，其中，该步骤(a2)是当下述任一条件成立，则判断两个矩形无相交: (i)其中一矩形的左缘坐标X值大于另一矩形的右缘坐标X值 '及 (?)其中一矩形的下缘坐标Y值大于另一矩形的上缘坐标Y值。15.如权利要求11至14中任一项所述的行车记录装置，其中，所述每一兴趣点内容还包括方位角；该处理器还依据该卫星定位单元陆续接收的定位信息，判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(C) ο
【专利摘要】一种空间数据库之数据结构产品，供一行车记录装置读取利用，并包含至少一道路的多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；及一树状数据结构，包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围。当该行车记录装置接收其GPS坐标，读取该树状数据结构并执行步骤(a)找到对应其GPS坐标的叶节点，(b)查询该叶节点中接近的兴趣点，及(c)输出该兴趣点的道路名称及里程。
【IPC分类】G06F17/30
【公开号】CN105488066
【申请号】CN201410482755
【发明人】张宏宇
【申请人】昆达电脑科技(昆山)有限公司, 神达电脑股份有限公司
【公开日】2016年4月13日
【申请日】2014年9月19日
【技术领域】
[0001]本发明是有关于一种数据结构产品，特别是指一种空间数据库之数据结构产品及其建置方法、应用方法。
【背景技术】
[0002]一般行车记录器可记录行车影像，以供日后纠纷举证或者违规检举时查阅。然而，大部分高速公路、快速道路四周景象无辨别性，因此难以从行车影像中辨识出车辆所在位置。
[0003]有关车辆所在位置的问题，目前市面上已出现可记录GPS坐标的行车记录器。但是就高速公路、快速道路的用路人来说，其熟悉的位置表示方式是例如某高速公路南下/北上几公里处(以下简称里程位置)，难以从GPS坐标转换为其熟悉的里程位置，因此使用上仍不方便。
【发明内容】
[0004]因此，本发明的目的，即在提供一种建置空间数据库的方法，该空间数据库供一行车记录装置使用，可有效率地显示及记录里程位置。
[0005]本发明的另一目的，在于提供一种空间数据库之数据结构产品，供行车记录装置应用，可有效率地显示及记录里程位置。
[0006]本发明的再一目的，在于提供一种行车记录装置，可利用前述空间数据库而有效率地显示及记录里程位置。
[0007]于是，本发明建置空间数据库的方法，由一计算机装置执行，包含:
(A)针对至少一道路建立多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；
针对该等兴趣点逐一地执行以下步骤，直到所有兴趣点皆处理完毕；
(B)依据该兴趣点的GPS坐标以及一预设插入原则，插入一树状数据结构的其中一叶节点中，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围；
(C)检查插入该兴趣点的该叶节点是否已超出预设的兴趣点笔数，若是则进行步骤(D);及
(D)依据一预设分割原则分割该叶节点。
[0008]较佳地，该步骤(B)的预设插入原则是，选择「在插入新的兴趣点后，叶节点的最小矩形需扩张的范围最小者」进行插入。
[0009]较佳地，该方法还包含步骤(D)之后的步骤(E):检查分割后的两个叶节点的父节点是否已超出预设的子节点数目，若是，则将该父节点中的子节点重新分配，成为两个具有最小矩形的父节点。进一步地，该方法还包含一步骤(D)之后的步骤(F):判断该步骤(D)进行分割的叶节点是否同时也是根节点，若否才执行步骤(E)，若是则建立一新的根节点，并将该步骤(D)分割得到的两个叶节点设定为该新的根节点的子节点。
[0010]较佳地，该步骤(A)所建立的该等兴趣点，内容还包括方位角，且该等兴趣点的方位角的建立方法包括以下子步骤:
(A1)读取一路网数据，该路网数据内容包括多个位置点，以及两两位置点构成的路网线段，且各该路网线段记载了有关行车方向的道路属性；
(A2)对每一兴趣点搜寻其最近的两个位置点Pn及Pn+1 ；
(A3)当该二位置点Pn、Pn+l所构成的路网线段的行车方向，与该路网线段的数化方向相同，则以该位置点Pn+1相对于该位置点Pn的角度作为该兴趣点的方位角，反之，则以该位置点Pn相对于该位置点Pn+1作为该兴趣点的方位角。
[0011]本发明空间数据库之数据结构产品，该空间数据库供一行车记录装置读取利用，并包含:
至少一道路的多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；及一树状数据结构，包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围；
当该行车记录装置接收一内容包含其GPS坐标的定位信息，读取并利用该空间数据库并执行以下步骤，
(a)找到对应其GPS坐标的叶节点，
(b)查询该叶节点中接近的兴趣点，及
(c)输出该兴趣点的道路名称及里程。
[0012]较佳地，该树状数据结构还包括一根节点，该叶节点为该根节点的子节点。当该行车记录装置接收该定位信息，执行的步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点；该步骤(b)是查询该叶节点中落于该目标矩形中的兴趣点。
[0013]更佳地，该树状数据结构中，该叶节点为该根节点间接的子节点。该行车记录装置执行的步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。
[0014]较佳地，每一兴趣点内容还包括方位角；该行车记录装置还依据陆续接收的定位信息判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(c)。
[0015]本发明行车记录装置，配合一空间数据库运作，该空间数据库包含至少一道路的多数个兴趣点及一树状数据结构，每一兴趣点内容包括道路名称、里程，及GPS坐标。该树状数据结构包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围。
[0016]该行车记录装置包含一接收一内容包含其GPS坐标的定位信息的卫星定位单元，及一处理器。
[0017]当该卫星定位单元接收一内容包含其GPS坐标的定位信息并传送给该处理器，该处理器读取并利用该空间数据库并执行以下步骤，
(a)找到对应其GPS坐标的叶节点，
(b)查询该叶节点中最接近的兴趣点，及 (c)输出该兴趣点的道路名称及里程。
[0018]较佳地,所述树状数据结构还包括一根节点，该叶节点为该根节点的子节点；该步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，及(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点。
[0019]更佳地，所述树状数据结构中，该叶节点为该根节点间接的子节点；该步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。
[0020]此外，该步骤(a2)是当下述任一条件成立，则判断两个矩形无相交:⑴其中一矩形的左缘坐标X值大于另一矩形的右缘坐标X值；(ii)其中一矩形的下缘坐标Y值大于另一矩形的上缘坐标Υ值。
[0021]较佳地，所述每一兴趣点内容还包括方位角；该处理器还依据该卫星定位单元陆续接收的定位信息，判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(c)。
[0022]本发明之功效在于建置了有关于道路里程的空间数据库，且该空间数据库的数据结构有助于行车记录装置有效率地找到所在位置的道路里程而予以显示及记录。
[0023]【【附图说明】】
本发明的其它特征及功效，将于参照图式的实施方式中清楚地呈现，其中:
图1是一方块图，说明本发明之行车记录器及其搭配之空间数据库的一种实施例；
图2是一流程图，说明本发明空间数据库的建置方法的一种实施例；
图3是一流程图，说明有关兴趣点的方位角的建立；
图4是一示意图，用于辅助说明有关兴趣点的方位角的建立；
图5是一流程图，说明应用该空间数据库的步骤；及图6是一示意图，用于辅助说明两矩形是否相交的条件。
[0024]【【具体实施方式】】
参阅图1，本发明之实施例是由一行车记录装置1搭配一空间数据库2运作。本发明所指行车记录装置1，可理解为任何可接收卫星定位讯号且 可对于行车相关信息进行记录的装置，本实施例是以安装于汽车且具有一处理器11、一卫星定位单元12及一影像录制单元13举例说明。该卫星定位单元12接收一内容包含其GPS坐标的定位信息，而该影像录制单元13用于录制行车过程的周遭影像。
[0025]本发明所指空间数据库2是指一种数据结构产品，可在网站、应用程序商店供下载而储存于该行车记录装置1的储存空间(图未示)，亦可储存于云端服务器的储存空间(图未示)，供行车记录装置1的处理器11实体连接或通讯连接而读取利用。
[0026]配合参阅图2，建置该空间数据库2的方法是由任何具有运算能力的计算机装置3执行，该计算机装置3例如为图资公司服务器或个人计算机。该方法包含以下步骤:
步骤S01—针对至少一道路建立多数个兴趣点(POI,point of interest),例如国道每
0.1公里建立一个兴趣点。每一兴趣点内容包括道路名称(例如1号国道)、里程(亦即几公里)、GPS坐标，及方位角(例如45度或180度，且定义正北为0度)。
[0027]参阅图3，本发明对于兴趣点的方位角，是利用以下方法流程建立。
[0028]步骤S11—读取一路网数据，该路网数据内容包括多个位置点，以及两两位置点构成的路网线段，且各该路网线段记载了有关行车方向的道路属性。
[0029]所谓路网数据包含的内容非常广泛，任何有关道路的信息都可能已经或在未来被纳入图资供应者的路网数据内。路网资料包含但不限于以下提及的项目:位置点、其坐标，及两两位置点构成的路网线段。有关于每个路网线段，还记载了它的位置与形状、路网线段的名称、所在的行政区、道路属性(车道数量、车道宽度、可以通行的方向、车道转弯限制、行车速限、允许行走的车辆种类等)、道路等级(国道、省道、县道、乡道、普通道路等)、道路功能(重要联信道路、一般道路、私人道路等)、道路材质(铺设道路、未铺设道路、碎石子路、鹅卵石路等)。
[0030]路网数据还包含两条以上的路网线段是透过哪一个位置点连接；某一路网线段上的车辆往某一位置点行进时，可以通往哪些路网线段及不能通往哪些路网线段。当许多的路网线段被集合起来，就成为路网资料。
[0031]步骤S12—如图4所示，对每一兴趣点搜寻其最近的两个位置点Pn及Pn+1。
[0032]步骤S13—接下来，判断该二位置点Pn、Pn+l所构成的路网线段的行车方向，与该路网线段的数化方向是否相同？所谓数化方向，是指该路网线段被数字化(digitized)时之线段方向，即由Pn往Pn+1之方向，以例如以45度、180度的形式记录(正北为0度)，此方向即为线段PnPn+1的数化方向。若大致相同(例如差值在10度内)，则进行步骤S14，以该位置点Pn+1相对于该位置点Pn的方位角作为该兴趣点的方位角，以图3举例来说，所谓该位置点Pn+1相对于该位置点Pn的方位角就是「Pn与正北之联机」及「Pn与Pn+1之联机」的夹角，为90度。反之,则进行步骤S15,以该位置点Pn相对于该位置点Pn+1作为该兴趣点的方位角。
[0033]再回到图2，针对该等兴趣点逐一地执行以下步骤，直到所有兴趣点皆处理完毕。
[0034]步骤S02—依据该兴趣点的GPS坐标以及一预设插入原则，插入一树状数据结构的其中一叶节点中。本实施例是以三层的树状数据结构简单举例说明，但当然不以此为限。本实施例之树状数据结构可看作倒挂的树型，包括一根节点(R)、以该根节点(R)做为父节点往下延伸的两个子节点(S)，及以各该子节点(S)作为父节点再往下延伸且没有再延伸子节点的叶节点(L)。
[0035]各该叶节点具有一由其所包含的兴趣点构成的最小矩形(Minimum BoundingRectangle,以下称MBR)范围；叶节点的父节点的MBR涵盖该叶节点甚至更多叶节点的所有兴趣点，因此是构成较大范围的MBR ;再往上的根节点则涵盖所有子节点的兴趣点。
[0036]本实施例所述预设插入原则是，选择「在插入新的兴趣点后，叶节点的MBR需扩张的范围最小者」进行插入。
[0037]步骤S03—检查插入该兴趣点的该叶节点是否已超出预设的兴趣点笔数，例如25笔，但不以此为限。若未超出，则进行步骤S04，往上更新父节点的MBR，直到根节点，且此兴趣点插入完成。若插入该兴趣点即超出预设笔数，例如26笔，则进行步骤S05。
[0038]步骤S05—依据一预设分割原则分割该叶节点。所述预设分割原则是，将该叶节点中的兴趣点重新分配，成为两个具有最小矩形的叶节点。
[0039]接下来，执行步骤S06判断该进行分割的叶节点是否同时也是根节点？若是(通常在建置空间数据库的初期)，则表示兴趣点的数据量已经增加到一定程度，可建立阶层，则执行步骤S07建立一新的根节点，并将前述分割得到的两个叶节点设定为该新的根节点的子节点，此兴趣点插入完成。
[0040]若前述进行分割的叶节点不是根节点，则执行步骤S08，检查分割后的两个叶节点的父节点是否已超出预设的子节点数目，例如10个，若是，例如分割后有11个子节点，则执行步骤S09将该父节点中的子节点重新分配，成为两个具有最小矩形的父节点。接着回到步骤S06，再次判断进行分割的父节点是否同时也是根节点？若是则应进一步建立阶层，则建立一新的根节点，并将前述分割得到的两个父节点设定为该新的根节点的子节点。
[0041]若父节点未超出预设子节点数目，则此兴趣点插入完成。擷取下一个兴趣点。
[0042]参阅图1及图5，当所有兴趣点皆插入完成，即完成该空间数据库2。当该行车记录装置1执行步骤S21，其卫星定位单元12接收一内容包含其GPS坐标的定位信息并传送至处理器11，处理器11读取并利用该空间数据库2而执行步骤S22~S29。
[0043]步骤S22—先设定一对应其GPS坐标的目标矩形；其尺寸视实际应用区域而异，例如为 0.3km X 0.2km。
[0044]步骤S23—接着，查询该树状数据结构中根节点的所有子节点，找出MBR与该目标矩形相交的子节点。本实施例是利用排除无相交的方式找出有相交者，具体来说，当下述任一条件成立，则判断两个矩形无相交:(i)其中一矩形的左缘坐标X值大于另一矩形的右缘坐标X值；(?)其中一矩形的下缘坐标Y值大于另一矩形的上缘坐标Y值。
[0045]再更具体来说，配合参阅图6，定义矩形A及B的左下角坐标与右上角坐标分别为(xaO, yaO)、(xal, yal)及(xbO, ybO)、(xbl, ybl)。当 xaO > xbl 或 xbO > xal 则无相交。当yaO > ybl或ybO > yal也无相交。
[0046]步骤S24—判断相交的子节点是否为叶节点，若是，即找到对应其GPS坐标的叶节点，接着进行步骤S25以下。若否，则执行步骤S29，针对相交的子节点往下进一步查询其子节点，找出MBR与该目标矩形相交的子节点，并回到步骤S24判断是否为叶节点，直到确认该子节点为叶节点。
[0047]步骤S25—查询该叶节点中落于该目标矩形中的兴趣点。若有兴趣点落于该目标矩形，例如「国一南下35.0k」、「国一南下35.1k」及「国一北上35.1k」三个兴趣点，则针对该等找到的兴趣点分别执行步骤S26确认方位，若无则表示附近无兴趣点，此笔定位信息对应的处理结束。但实作上不以此为限，若希望仍能有里程信息可输出，则亦可设计为:当无兴趣点落于该目标矩形，则求取该叶节点中所有Ρ0Ι进行S26及其接下来步骤的判断」，如同把目标矩形放大到跟叶节点MBR —样大的意思。如此一来，因为在步骤S27会筛选出最近者，所以搜寻结果不会「舍近求远」。
[0048]步骤S26—判断该兴趣点的方位角是否与该实际行车方向相符？在此须说明的是，该行车记录装置1还依据陆 续接收的定位信息判断一实际行车方向，本步骤需依据该实际行车方向进行判断，滤除搜寻结果中道路方向方位角与之相差超过例如正负20度之兴趣点，例如得到「国一南下35.0k」及「国一南下35.1k」。
[0049]步骤S27—针对行车方向相符的兴趣点，进一步筛选出最接近者，例如「国一南下35.lkjo
[0050]步骤S28—输出该兴趣点的道路名称及里程。所谓输出，例如显示于该行车记录装置1的显示屏幕(图未示)、以语音方式透过扬声器输出，及/或记录于内存(图未示)，藉此得以令人方便地了解车辆所在道路及其里程数。
[0051]综上所述，本发明建置了有关于道路里程的空间数据库2，且该空间数据库2的数据结构有别于一般图资的大量资料搜寻而耗时，有助于行车记录装置1有效率地找到所在位置的道路里程而予以显示及记录，故确实能达成本发明之目的。
[0052]以上所述，仅为本发明的【具体实施方式】，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。
【主权项】
1.一种建置空间数据库的方法，由一计算机装置执行，包含: (A)针对至少一道路建立多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标； 针对该等兴趣点逐一地执行以下步骤，直到所有兴趣点皆处理完毕； (B)依据该兴趣点的GPS坐标以及一预设插入原则，插入一树状数据结构的其中一叶节点中，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围； (C)检查插入该兴趣点的该叶节点是否已超出预设的兴趣点笔数，若是则进行步骤(D);及 (D)依据一预设分割原则分割该叶节点。2.如权利要求1所述的建置空间数据库的方法，其中，该步骤(B)的预设插入原则是，选择「在插入新的兴趣点后，叶节点的最小矩形需扩张的范围最小者」进行插入。3.如权利要求1所述的建置空间数据库的方法，其中，该步骤(D)的预设分割原则是，将该叶节点中的兴趣点重新分配，成为两个具有最小矩形的叶节点。4.如权利要求1所述的建置空间数据库的方法，还包含步骤(D)之后的步骤(E):检查分割后的两个叶节点的父节点是否已超出预设的子节点数目，若是，则将该父节点中的子节点重新分配，成为两个具有最小矩形的父节点。5.如权利要求4所述的建置空间数据库的方法，还包含一步骤(D)之后的步骤(F):判断该步骤(D)进行分割的叶节点是否同时也是根节点，若否才执行步骤(E)，若是则建立一新的根节点，并将该步骤⑶分割得到的两个叶节点设定为该新的根节点的子节点。6.如权利要求1至5中任一项所述的建置空间数据库的方法，其中，该步骤㈧所建立的该等兴趣点，内容还包括方位角，且该等兴趣点的方位角的建立方法包括以下子步骤: (A1)读取一路网数据，该路网数据内容包括多个位置点，以及两两位置点构成的路网线段，且各该路网线段记载了有关行车方向的道路属性； (A2)对每一兴趣点搜寻其最近的两个位置点Pn及Pn+1 ； (A3)当该二位置点Pn、Pn+l所构成的路网线段的行车方向，与该路网线段的数化方向相同，则以该位置点Pn+1相对于该位置点Pn的角度作为该兴趣点的方位角，反之，则以该位置点Pn相对于该位置点Pn+1作为该兴趣点的方位角。7.一种空间数据库之数据结构产品，该空间数据库供一行车记录装置读取利用，并包含: 至少一道路的多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；及 一树状数据结构，包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围； 当该行车记录装置接收一内容包含其GPS坐标的定位信息，读取并利用该空间数据库并执行以下步骤， (a)找到对应其GPS坐标的叶节点， (b)查询该叶节点中接近的兴趣点，及 (c)输出该兴趣点的道路名称及里程。8.如权利要求7所述的空间数据库之数据结构产品，其中，该树状数据结构还包括一根节点，该叶节点为该根节点的子节点； 当该行车记录装置接收该定位信息，执行的步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点；该步骤(b)是查询该叶节点中落于该目标矩形中的兴趣点。9.如权利要求8所述的空间数据库之数据结构产品，其中，该树状数据结构中，该叶节点为该根节点间接的子节点； 该行车记录装置执行的步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。10.如权利要求7至9中任一项所述的空间数据库之数据结构产品，其中，每一兴趣点内容还包括方位角；该行车记录装置还依据陆续接收的定位信息判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(C) ο11.一种行车记录装置，配合一空间数据库运作，该空间数据库包含至少一道路的多数个兴趣点及一树状数据结构，每一兴趣点内容包括道路名称、里程，及GPS坐标，该树状数据结构包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围，包含: 一卫星定位单元，接收一内容包含其GPS坐标的定位信息；及 一处理器； 当该卫星定位单元接收一内容包含其GPS坐标的定位信息并传送给该处理器，该处理器读取并利用该空间数据库并执行以下步骤， (a)找到对应其GPS坐标的叶节点， (b)查询该叶节点中最接近的兴趣点，及 (c)输出该兴趣点的道路名称及里程。12.如权利要求11所述的行车记录装置，其中，所述树状数据结构还包括一根节点，该叶节点为该根节点的子节点；该步骤(a)包括(al)先设定一对应其GPS坐标的目标矩形，及(a2)查询该根节点的子节点，找出最小矩形与该目标矩形相交的子节点。13.如权利要求12所述的行车记录装置，其中，所述树状数据结构中，该叶节点为该根节点间接的子节点；该步骤(a)还包括步骤(a3)，判断相交的子节点是否为叶节点，若是则完成找到对应其GPS坐标的叶节点；若否则进一步查询该相交的子节点的子节点，找出最小矩形与该目标矩形相交的子节点，直到该子节点为叶节点。14.如权利要求12所述的行车记录装置，其中，该步骤(a2)是当下述任一条件成立，则判断两个矩形无相交: (i)其中一矩形的左缘坐标X值大于另一矩形的右缘坐标X值 '及 (?)其中一矩形的下缘坐标Y值大于另一矩形的上缘坐标Y值。15.如权利要求11至14中任一项所述的行车记录装置，其中，所述每一兴趣点内容还包括方位角；该处理器还依据该卫星定位单元陆续接收的定位信息，判断一实际行车方向，该步骤(b)还包括判断该兴趣点的方位角是否与该实际行车方向相符，若相符才执行步骤(C) ο
【专利摘要】一种空间数据库之数据结构产品，供一行车记录装置读取利用，并包含至少一道路的多数个兴趣点，每一兴趣点内容包括道路名称、里程，及GPS坐标；及一树状数据结构，包括至少一依据该等兴趣点的GPS坐标而插入有其中至少一兴趣点的叶节点，该叶节点具有一由其所包含的兴趣点构成的最小矩形范围。当该行车记录装置接收其GPS坐标，读取该树状数据结构并执行步骤(a)找到对应其GPS坐标的叶节点，(b)查询该叶节点中接近的兴趣点，及(c)输出该兴趣点的道路名称及里程。
【IPC分类】G06F17/30
【公开号】CN105488066
【申请号】CN201410482755
【发明人】张宏宇
【申请人】昆达电脑科技(昆山)有限公司, 神达电脑股份有限公司
【公开日】2016年4月13日
【申请日】2014年9月19日
最新回复(0)