表示位置内容管理系统中的线性特征的方法

摘要

公开了表示位置内容管理系统中的线性特征的方法。使用通过路由点在地图上进行路由时定义唯一路径的这些路由点的序列来表示线性特征。路由点包括纬度、经度以及可选的堆叠地点。堆叠地点定义了双层桥梁或者道路的上层或下层。表示线性特征的数据被存储在地理数据库之外。

说明书

相关申请的交叉引用

本专利申请涉及同日提交的同时待审的以下专利申请：序列号12/362,734、题为“METHOD AND SYSTEM FOR ASSESSING QUALITY OFLOCATION CONTENT”；序列号12/362751、题为“METHOD AND SYSTEMFOR MANAGING RELATIONSHIPS BETWEEN LOCATION IDENTIFIERS”；序列号12/362,767、题为“METHOD AND SYSTEM FOR REFRESHINGLOCATION CODE DATA”；以及序列号12/362,807名称“METHOD ANDSYSTEM FOR EXCHANGING LOCATION CONTENT DATA IN DIFFERENTDATA FORMATS”。

技术领域

本发明总体上涉及基于位置的服务，更具体地，涉及如何表示不依赖于地理数据库中存储的各线性特征的线性特征。

背景技术

已经开发了提供有关导航和有关地图的服务的各种技术。例如，车辆导航系统可以确定车辆位于什么地方，并且提供用于行进(travel)到期望目的地的方向。此外，如下这样的因特网站点是可用的，该因特网站点提供：地图，用于从指定的开始点行进到期望目的地的方向，以及其他有关地图的服务。进一步，可确定某人的地点并提供某人周围环境的地图的手持设备是可用的。

为了提供这些和其他有关地图的功能和特征，导航系统使用地理数据。地理数据可以是一个或多个地理数据库的形式，所述一个或多个地理数据库包括表示地理区域中的物理特征的数据。地理数据库包括关于所表示的地理特征(诸如单行线、道路的地点、沿着道路部分的限速、沿着道路部分的地址范围、道路交叉点处的转弯限制、诸如单行线之类的方向限制等等)的信息。另外，地理数据可以包括感兴趣的点，诸如饭店、酒店、机场、加油站、体育场、警察局等。

可以将该地理数据存储在地理数据库中，诸如由伊利诺伊州芝加哥的NAVTEQ North America，LLC出版的地理数据库。除了地图供应商获得的数据之外，内容源还具有关于地理区域中的位置的数据。内容源可以将其数据提供给地图供应商以将其包括到地理数据库中。例如，连锁饭店的所有者可以向地图供应商提供所有其位置的当前列表，并且对于每个位置，该列表可以包括地址、电话号码、营业时间、菜单、网页地址以及关于位置的其他信息。

随着在地理数据库中存储的信息量增加，地图供应商变得更加难以将第三方数据添加到地理数据库。结果，已经开发了允许多方提供有关位置的数据(其有时称为“位置内容”或简称为“内容”)的位置内容管理系统。位置内容管理系统提供了位置内容和与该内容相关联的地理位置之间的链接。该链接是位置内容管理系统分配给位置的位置代码。

可以将位置代码分配给人员可以行进到的任何位置。例如，人员可能想要行进到地理区域中特定建筑物的特定楼层上的特定办公室。使用此示例，位置内容管理系统将位置代码分配给办公室、楼层和建筑物中的每一个。如果该楼层不是在该建筑物的地面上，则位置内容管理系统还可以将位置代码分配给楼梯和/或电梯。通过以此方式分配位置代码，导航系统可以为用户提供用于行进到该建筑物内的办公室的路线向导。

尽管位置内容管理系统提供了多方提供关于位置的内容的方式，但是在位置内容管理系统中继续有新特征和改进的空间。改进的一个领域是如何表示位置内容管理系统中的线性特征。位置代码参考纬度和经度在最低限度上识别出的点位置。然而，在某些情形下，位置代码参考线性特征将是有益的。

如同点位置代码那样，由于线性位置代码必然保留在地理数据库的外部，因此线性对象的地理数据库两种表示，链接和绞合(strand)不适于表示位置内容管理系统中的线性特征。链接是具有两个节点(参考节点和非参考节点)以及零个或多个中间形状点的地理对象。绞合是地理数据库中定义的条件所使用的链接的直接序列。链接遭受由于属性要求而被分离(split)和合并的问题，而绞合遭受如此紧密地被耦合到条件以致该绞合只能被该条件所参考的问题。由此，线性位置代码需要以克服了与链接和绞合相关联的问题的方式来表示线性特征。

发明内容

公开了用于表示位置内容管理系统中的线性特征的方法。所述方法为线性特征定义线性位置代码。线性位置代码包括路由点的序列，其中路由点包括当通过这些点在地图上路由时定义唯一路径的纬度、经度以及可选的堆叠(stack)位置(例如，L为较低的而U为较高的)或者高度。堆叠位置用于消除垂直堆叠的道路的歧义，诸如双层桥梁(例如，旧金山/奥克兰湾大桥)或者具有上部和下部的街道(例如，芝加哥的密歇根大街和Wacker Drive)。有益地，该方法独立于地理数据库中所存储的链接和绞合对象而表示线性特征。

通过在适当的情况下参考附图阅读以下详细描述，这些以及其它方面和优点对于本领域技术人员来说将变得显而易见。此外，应理解，该发明内容仅仅是示例，并且不旨在限制所要求保护的发明的范围。

附图说明

下面结合附图描述当前的优选实施例，其中，在各图中，相同参考标号指代相同要素，并且其中：

图1是根据一示例的基于位置的系统的框图；

图2是根据一示例的线性位置代码的数据结构的框图；

图3是根据一示例的路由点的数据结构的框图；

图4A和图4B是一示例线性特征的图形表示；

图5是根据一示例的、在图4B中描绘的线性特征的数据结构的框图；

图6是根据一示例的、表示两个火车站的两个点位置代码与车站之间的路线的图形表示；

图7是根据一示例的、表示在图6中描绘的相同两个车站与车站之间的路线的线性位置代码的图形表示；

图8是根据一示例的、现有的折线(polyline)位置对象和潜在的新的折线位置对象的图形表示；以及

图9是根据一示例的、用于确定是否向图8中描绘的潜在的新的折线位置对象分配线性位置代码的匹配例程的流程图。

具体实施方式

图1是示出基于位置的系统100的框图。基于位置的系统100包括内容源102、位置内容管理系统104以及内容接收器106。位置内容管理系统104从内容源102获得内容。位置内容管理系统104向内容接收器106提供内容。在某些情形下，内容源102和内容接收器106可以是相同的实体。

内容是与位置相关联的任何信息。该信息可以是静态内容(即，不频繁变化)，诸如街道地址、电话号码、传真号码以及营业时间。该信息可以是动态内容(即，频繁变化)，诸如油价、天气报告、航班状态以及交通报告。该信息可以是包括文本、二维图像、三维图像、视频、多媒体等在内的任何格式。

内容源102是向位置内容管理系统104提供内容的任何实体。例如，内容源102可以是地图供应商、位置所有者/运营者、政府机构、商业协会(chamber of commerce)、个人或任何其它方。尽管在图1中描绘了一个内容源102，但应理解，位置内容管理系统104从许多内容源获得内容。

内容接收器106是从位置内容管理系统104访问内容的任何实体。内容接收器106可以是最终用户设备，诸如个人计算机、移动电话以及便携式手持设备。另外，内容接收器106可以是向最终用户设备分发位置内容的中间设备。尽管在图1中描绘了一个内容接收器106，但应理解，位置内容管理系统104向许多内容接收器提供内容。

位置内容管理系统104是硬件、软件和/或固件的组合，其收集、处理并递送位置内容。位置内容管理系统104包括内容上载服务器108、内容存储装置110、位置参考系统112、内容质量系统114以及内容递送服务器116。位置内容管理系统104还可以包括其它实体。

内容上载服务器108可以显示用于向位置内容管理系统104提供位置内容的用户界面。该用户界面允许内容源102在自助环境(self-serveenvironment)下输入、管理并定位其内容。该用户界面可以包括用于输入位置信息的工具，该位置信息包括与存储在简档(profile)中的数据相对应的字段。该用户界面允许内容源102输入文本并附上文件(诸如文档、图像文件、视频文件、声音文件等等)。

另外或可替代地，内容上载服务器108可以提供用于在网络上支持机器到机器的交互的网络服务。该网络服务可以支持任何协议。内容源102可以使用该网络服务以便经由大容量载入(bulk load)来添加或修改位置内容。

内容上载服务器108还验证内容源102。内容上载服务器108可以利用包括(但不限于)双重选择性加入例程(double opt-in routine)、公众验证(community validation)、人工验证(manual validation)以及合作伙伴验证(partner validation)在内的任何合适的方法或以上方法的组合来验证个人、商业和/或组织。

内容上载服务器108将内容存储在内容存储装置110中。内容存储装置110可以是允许读/写访问的任何类型的存储器。内容上载服务器108还可以在内容存储装置110或分离存储器设备中存储关于使用什么验证方法来验证内容源102的指示。例如，该指示可以是用于识别验证方法的二进制标志、缩放因子或者文字。

位置参考系统112提供位置内容和与该内容相关联的地理位置之间的链接。当从地理数据库中解耦位置内容(即，不包括在地理数据库中)时需要该链接。为了从地理数据库中解耦内容，位置参考系统112向一个或多个位置分配位置标识符，并且在内容存储装置110中存储该位置标识符。位置标识符可以是点位置代码或者线性位置代码。

点位置代码参考点特征(例如，道路上的点、建筑物的地点、建筑物内的点)。由纬度和经度属性最低限度地表示点位置代码。还可以将点位置代码与允许点位置代码被地理编码(geocode)到地理数据库链接的地址相关联。地理编码是将地理数据库之外的实体(例如，位置代码)与地理数据库内的地图对象地理性地相关联的处理。

线性位置代码参考诸如一部分道路网络或者一部分步行路线之类的线性特征。线性位置代码包括路由点的序列，其定义了当通过这些点在地图上路由时的唯一路径。路由点具有纬度、经度、以及可选的用于具有两层(即，上层和下层)的道路和桥梁的堆叠地点。另外或可替代地，路由点可以具有高度。例如，路由点可以具有相对于海平面的高度、相对于地面的高度、或者相对于另一参考面的高度。

可以通过定义路由点的标准(即，归一化)表示来获得路由点的序列。例如，标准表示(canonical representation)可以使用关键决定点。作为另一示例，该标准表示可以使用两个关键决定点之间中途的段点(segment point)。关键决定点是司机必须转弯或者否则在两个或更多个可选方案之间进行选取的点(例如道路的分叉口)。还可以使用其他的标准形式。标准表示对于给定的线性特征来说是唯一的，而不管使用什么中间点来初始地定义线性位置代码。参照图4进一步描述路由点的标准表示。

线性位置代码可以参考线、折线或者多边形对象。线位置代码表示由一条直线段组成的连续线并且由两个路由点来定义。折线位置代码表示由两个或者更多个的直线段组成的连续线，并且由三个或者更多个路由点来定义。多边形位置代码表示由三个或者更多个的直线段组成的封闭路径，并且由三个或者更多个路由点来定义。参照图2进一步描述线性位置代码属性。

位置参考系统112可以随机地向位置分配位置标识符。可替代地，位置参考系统112可以以数字顺序或者以任何其它组织方式分配位置标识符。位置标识符可以是数字值。例如，位置标识符可以是16比特数字、32比特数字、64比特数字等。可替代地，位置标识符可以包括数字、字母和/或字符的组合。

在向线性特征分配位置标识符之前，位置参考系统112可以首先确定线性特征是否已经与线性位置代码相关联。对于线位置代码，位置参考系统112确定与线特征相关联的两个路由点是否在与之前创建的线位置代码相关联的两个路由点的预定半径(例如，1米)之内。如果存在匹配，则不创建新的线位置代码。否则，向线性特征分配新的线位置代码。

对于折线或者多边形位置代码，匹配算法考虑现有的线性位置代码与新的线性位置代码之间的路由点数目是否相同。当新的线性位置代码具有与现有的折线或者多边形位置代码相同数目的路由点时，匹配算法使用围绕每一个现有路由点的预定半径来识别匹配。该过程与具有更多个路由点的线位置代码匹配算法类似。

当路由点的数目不相同时，则匹配算法确定与预先存在的点不匹配的路由点是否在距线段预定的正交距离内。如果额外的点在预定的正交距离内，则认为这些点是定义线性位置代码所不需要的中间点。在该情况下，找到了匹配并且不会创建新的线性位置代码。关于图8和图9进一步描述该处理。

内容质量系统114评估在内容存储装置110中存储的位置内容的质量。该评估可以基于内容拥有者是否可信赖、位置数据是否准确、内容是否充分完备和/或内容是否是相对当前的。内容质量系统114在内容存储装置110或者其它存储器设备中存储对于内容的质量评分。内容质量系统114可以在每当内容变化时，以规律的间隔、应内容源102和/或内容接收器106的请求、或者在任何其它时间重新评估内容质量。内容质量系统114可以存储对于内容的历史质量评分，以便内容源102和/或内容接收器106可以检索评分趋势报告。

内容递送服务器116显示用于从位置内容管理系统104检索位置内容的用户界面。该用户界面可以是与内容源102所使用的相同的用户界面，或者是独立的用户界面。另外或者可替代地，内容递送服务器116可以以与内容上载服务器108类似的方式提供网络服务。用户界面/网络服务允许内容接收器106在自助环境下获得位置内容。用户界面/网络服务还允许内容接收器106从位置内容管理系统104接收与所获得的内容相关联的一个或多个质量评分。

图2是线性位置代码记录200的数据结构。图2中描绘的数据属性包括代码标识202、两个或多个路由点204、206以及焦点208。线性位置代码记录200还可以具有其他属性。

线性位置代码记录200包括由位置参考系统112所分配的唯一代码标识202。路由点204、206定义了当通过这些点在地图上路由时的唯一路径。当线性位置代码记录200包括两个路由点时，线性位置代码表示由一个直线段组成的连续线。当线性位置代码记录200包括三个或者更多个路由点时，线性位置代码表示折线或者多边形。折线是由两个或者更多个直线段组成的连续线。多边形是由三个或者更多个直线段组成的封闭路径。线、折线和多边形位置代码中的每一个都被视作单个对象。

焦点208是区域中用于对位置代码的请求进行响应的点。对于线位置代码，焦点208是线段的中心点。对于折线或多边形位置代码，焦点208是连接段的质心(centroid)。质心是对象内所有点的平均位置。可以由位置参考系统112自动地计算焦点208。例如，位置参考系统112可以使用Oracle 11g中的SDO_CENTROID功能。还可以手动地定义和/或由最终用户调整焦点208。

图3是路由点记录300的数据结构。图3中描绘的数据属性包括纬度302、经度304和堆叠306。堆叠306用于消除垂直堆叠的道路(诸如双层桥梁(例如，旧金山/奥克兰湾大桥)或者具有上层和下层的街道(例如，芝加哥的Upper andLower Wacker Drive))的歧义。由于这对于路由记录300的所有数据属性来说不是穷尽性列表，因此，图3还描绘了其它属性308。例如，路由点记录300还可以包括高度(例如，绝对的或相对的)、街道地址等等的属性。另外，可以由高度属性来取代堆叠属性306。

图4是示例线性特征400(以虚线加重)的图形表示。线性特征400是通过俄亥俄州街道匝道(ramp)至芝加哥的往南的肯尼迪高速公路的路径。线性特征400具有开始点402和结束点406。线性特征400还具有两个关键决定点403、405。

如图4A所示，可以使用位于开始点402、结束点406以及两个关键决定点403、405这四个路由点(即，关键决定点标准形式)来唯一地定义线性特征400。可替代地，如图4B所示，可以使用位于开始点402、结束点406、以及位于两个关键决定点403、405之间中途的段点404(即，两个关键决定点之间中途的段点标准形式)这三个路由点来唯一地定义线性特征400。如图4A和图4B所示，还可以通过焦点408来定义线性特征400。

图5描绘了可以表示线性特征400的线性位置代码500。在该示例中，线性位置代码500包括如下这样的数据，该数据使用了如图4B中所描绘的在两个关键决定点之间中途的段点标准形式。包括使用关键决定点标准形式的数据的、表示线性特征400的线性位置代码将包括另外的路由点。虽然线性位置代码500不取决于地理数据库中所存储的对象(例如，链接、绞合)，但与代码500相关联的数据是可地理编码的。

使用反向地理编码将线性位置代码的路由点匹配(捕捉)到地理数据库中的数据。反向地理编码是将纬度/经度地点分解(resolve)到地理数据库中的链接上的位置的处理。反向地理编码处理使用一组规则。例如，如果路由点在节点的预定距离(例如，5m)内，则将路由点捕捉到节点并且识别出对于该节点的最近链接参考。作为另一示例，如果反向地理编码不能在预定的距离(例如，50m)内找到链接地点，则不将线性位置代码捕捉到链接。

反向地理编码处理允许路由算法通过被捕捉到道路链接的路由点来确定链接的序列。虽然可以使用任何合适的路由算法，但线性位置代码对象的有限大小意味着不需要诸如双星(double-star)路由算法之类的复杂路由算法。

图6是表示两个火车站的两个点位置代码601、602和所述两个车站之间的路线605的图形表示。由于基于点的位置参考机制的限制，在图6中仅仅隐含地定义了路线信息。点位置代码601、602与在位置内容存储装置110中存储的位置内容604相关联。位置内容604可以包括营运时间、电话号码、票价、火车时刻表以及车站建筑物、轨道和铁路客车的图像。可以将位置内容604限制到距车站的半径距离603。在图6中描绘的点位置代码示例中，距火车站相关联的点位置代码601、602的两个半径距离603之间的位置内容是不可用的。

图7是表示与图6中描绘的相同的两个火车站的线性位置代码701的图形表示。在该示例中，位置内容与线性位置代码701相关联。具有手持设备703的人员702正向两个火车站之间的点704移动以确定位置。手持设备703包括定位系统，该定位系统可利用GPS类型的技术、航位推测法(deadreckoning)类型的系统或者这些或其他系统的组合。定位系统可以包括测量行进距离速度、方向、方位等等的适合的感测设备。

利用手持设备对设备的位置(纬度、经度、高度)、速度(v)以及朝向线性特征的方向(罗盘读数，α)的确定，设备703可以获得该人员行进具体的位置内容，而这在图6中所描绘的示例中是不可得到的。例如，设备703可以获得反映在该人员行走时的该人员的视图的图像。另外，如果设备703得知了日期和时间，则设备703还可以提供关于下一趟火车将何时通过点704的内容。

还可以使用线性位置代码来更容易地表示之前存储在地理数据库内的特征。例如，将图像文件与通过公路出口决定点的路径相关联的接合点(junction)视图条件可以被地理数据库之外定义的接合点视图对象所代替。接合点视图对象将线性位置代码与一组图像文件相关联。作为另一示例，可以通过使用线性位置代码而不是将链接拆散来形成条件绞合，以对在一条链接的中间开始并且在另一链接的某个地方结束的非通过区(No passing zone)进行建模。存储在地理数据库中的诸如疏散(evacuation)或者雪天路线之类的其他特征也可以受益于使用线性位置代码在地理数据库之外的建模。

图8是现有的折线位置对象802和潜在的新的折线位置对象804的图形表示。现有的折线位置对象802具有三个路由点806，而潜在的新的折线位置对象804具有八个路由点808。图9是可以用于确定是否向潜在的新的折线位置对象804分配新的线性位置代码的匹配例程900的流程图。

在块902处，例程900接收新对象804的数据。该数据包括用于定义新对象804的路由点808中每一个的纬度、经度以及可选的堆叠层(stack level)或者高度。在块904处，例程900对用于定义新对象804的路由点808的数目进行计数。在图8所示的示例中，例程900计数了八个路由点808。

在块906处，例程900搜索在距定义新对象804的第一路由点的预定半径距离(r)内具有路由点的现有位置代码。例如，该预定距离可以是三米。如果在块908处识别到没有现有的线性位置代码，则在块920处，例程900创建新的线性位置代码。

如果在块908处识别到现有的线性位置代码，则在块910处，例程900确定在块908处评估的各路由点之间的距离(d_n)。在块912处，例程900确定该距离是否小于或等于预定的半径距离(d_n≤r)。如果该距离大于半径距离(d_n＞r)，则例程900在块920处创建新的线性位置代码。

如果该距离小于或者等于预定的半径距离(d_n≤r)，则例程900在块914处确定在下一路由点与现有线性位置代码所表示的线性特征之间的正交距离(d_i)。在块916处，例程900确定该正交距离是否小于或者等于预定的半径距离(d_n≤r)。如果该距离大于正交距离(d_n＞r)，则例程900在块920处创建新的线性位置代码。

如果该正交距离小于或者等于预定的半径距离(d_n≤r)，则例程900在块918处确定是否存在要评估的任何另外的路由点808。如果存在另外的路由点808，则例程900返回到块914以评估该路由点。例程900持续，直到在块920处创建了新的线性位置代码或者找到了与现有的线性位置代码的匹配为止。如果找到了匹配，则例程900不创建新的线性位置代码。

上述详细描述旨在被视为说明性的而非限制性的，并且应理解，包括所有等同形式的以下权利要求书旨在限定本发明的范围。权利要求书不应当被理解为限于所描述的顺序或者要素，除非声明如此。因此，所有落入以下权利要求书及其等同形式的范围和精神内的所有实施例都被请求作为本发明而保护。