公开(公告)号：US06366927B1

公开(公告)日：2002-04-02

申请号：US09460454

申请日：1999-12-13

申请人： James A. Meek ,  Richard A. Ashby ,  David S. Lampert

发明人： James A. Meek ,  Richard A. Ashby ,  David S. Lampert

IPC分类号： G06F1730

CPC分类号： G01C21/32 ,  Y10S707/92 ,  Y10S707/99943 ,  Y10S707/99945 ,  Y10S707/99948

摘要： A system and method for storing data to represent other-than-straight map features in a computer-readable geographic database for use in a navigation system. For geographic features that are other-than-straight, a curve generated by a computable function is fitted to an image of the other-than-straight map feature. The computable function may be a polynomial equation whose shape is defined by its coefficients. In one embodiment, the polynomial equation is a type of spline curve, in particular a Bezier curve whose shape is defined by control points. The coefficients of the polynomial equation are associated with data representing the other-than-straight feature. In the case in which the polynomial equation is a Bezier curve, the control points for generating the Bezier curve are associated with the data representing the other-than-straight feature. These control points are stored in the geographic database and are used in displaying the other-than-straight geographic feature. Use of a computable function to generate other-than-straight geographic features and storing parameters to be used by the computable function has the potential for significantly reducing the storage requirements for representing other-than-straight features in a geographic database. According to a further aspect, normalized control point pairs are stored in a data structure and an index reference into the data structure is associated with data used to represent the other-than-straight geographic features, thereby resulting in further reduction in data storage requirements.

摘要翻译： 一种用于存储数据以表示用于导航系统的计算机可读地理数据库中的非直线地图特征的系统和方法。 对于不同于直线的地理要素，由可计算函数生成的曲线适用于其他直线地图特征的图像。 可计算函数可以是其形状由其系数定义的多项式方程。 在一个实施例中，多项式方程式是一种样条曲线，特别是其形状由控制点定义的贝塞尔曲线。 多项式方程的系数与表示不同于直线特征的数据相关联。 在多项式方程为贝塞尔曲线的情况下，生成贝塞尔曲线的控制点与表示其他直线特征的数据相关联。 这些控制点存储在地理数据库中，用于显示不同于其他地理特征。 使用可计算函数生成不同于其他地理特征并存储要由可计算函数使用的参数，这有可能显着降低存储要求，以便在地理数据库中表示其他非直线特征。 根据另一方面，归一化控制点对存储在数据结构中，并且到数据结构中的索引引用与用于表示不同于平行的地理特征的数据相关联，从而进一步减少数据存储要求。

公开(公告)号：US07197500B1

公开(公告)日：2007-03-27

申请号：US10007910

申请日：2001-10-22

申请人： Vijaya S. Israni ,  Richard A. Ashby ,  Paul M. Bouzide ,  John C. Jasper ,  Robert P. Fernekes ,  Gregory M. Nyczak ,  Nicholas E. Smith ,  David S. Lampert ,  James A. Meek ,  Aaron I. Crane

发明人： Vijaya S. Israni ,  Richard A. Ashby ,  Paul M. Bouzide ,  John C. Jasper ,  Robert P. Fernekes ,  Gregory M. Nyczak ,  Nicholas E. Smith ,  David S. Lampert ,  James A. Meek ,  Aaron I. Crane

IPC分类号： G06F17/30

CPC分类号： G01C21/32 ,  Y10S707/92

摘要： An improved method and system for storage of data that represent geographic features in a region. The data are organized into parcels each of which contains data that represent those geographic features that are located within a separate one of a plurality of rectangular areas into the region is divided. The method identifies linearly extending features that extend across multiple rectangular areas so that data representing the linearly extending feature can be included in each parcel that contains data that represents a rectangular area in which the linearly extending feature extends at least in part.

摘要翻译： 用于存储表示区域中的地理特征的数据的改进的方法和系统。 数据被组织成包裹，每个包裹中的每一个包含表示那些位于多个矩形区域中的单独的一个区域内的区域的那些地理特征的数据。 该方法识别延伸跨越多个矩形​​区域的线性延伸特征，使得表示线性延伸特征的数据可以被包括在每个宗地中，其中包含表示线性延伸特征至少部分地延伸的矩形区域的数据。

公开(公告)号：US6029173A

公开(公告)日：2000-02-22

申请号：US979211

申请日：1997-11-26

申请人： James A. Meek ,  Richard A. Ashby ,  David S. Lampert

发明人： James A. Meek ,  Richard A. Ashby ,  David S. Lampert

IPC分类号： G09B29/00 ,  G01C21/00 ,  G01C21/32 ,  G06T11/60 ,  G06G6/00

CPC分类号： G01C21/32 ,  Y10S707/92 ,  Y10S707/99943 ,  Y10S707/99945 ,  Y10S707/99948

摘要： A system and method for storing data in a computer-readable database to represent curved geographic features. The database can be used in a navigation system. A computable function is used to define a curved line that represents the curved geographic feature. The computable function may be a polynomial equation whose shape is defined by its coefficients. In one embodiment, the polynomial equation is a type of spline curve, in particular a Bezier curve whose shape is defined by control points. The coefficients of the polynomial equation are associated with data representing the curved geographic feature. In the case in which the polynomial equation is a Bezier curve, the control points for generating the Bezier curve are associated with the data representing the curved geographic feature. These control points are stored in the database and are used in displaying the curved geographic feature. Use of a computable function to represent curved geographic features and storing parameters to be used by the computable function has the potential for significantly reducing the storage requirements for representing curved geographic features in a database. According to a further aspect, data identifying the normalized control points are stored in a data array and references into the data array are associated with data representing the curved geographic features, thereby enabling curved geographic features to be represented in space efficient manner.

摘要翻译： 一种用于将数据存储在计算机可读数据库中以表示弯曲地理特征的系统和方法。 数据库可以在导航系统中使用。 可计算函数用于定义表示曲面地理特征的曲线。 可计算函数可以是其形状由其系数定义的多项式方程。 在一个实施例中，多项式方程式是一种样条曲线，特别是其形状由控制点定义的贝塞尔曲线。 多项式方程的系数与表示弯曲地理特征的数据相关联。 在多项式方程为贝塞尔曲线的情况下，用于生成贝塞尔曲线的控制点与表示弯曲地理特征的数据相关联。 这些控制点存储在数据库中，用于显示弯曲的地理特征。 使用可计算函数来表示曲面地理特征并存储要由可计算函数使用的参数，这有可能显着降低在数据库中表示曲面地理特征的存储要求。 根据另一方面，标识归一化控制点的数据被存储在数据阵列中，并且数据阵列的引用与表示弯曲地理特征的数据相关联，从而使得能够以空间有效的方式表示弯曲的地理特征。

公开(公告)号：US07266560B2

公开(公告)日：2007-09-04

申请号：US09016002

申请日：1998-01-30

申请人： David S. Lampert ,  Richard A. Ashby ,  Robert Fernekes ,  James A. Meek ,  John Jaugilas

发明人： David S. Lampert ,  Richard A. Ashby ,  Robert Fernekes ,  James A. Meek ,  John Jaugilas

IPC分类号： G06F17/30 ,  G01C21/00 ,  G01C21/30 ,  G08G1/23

CPC分类号： G01C21/32 ,  Y10S707/99942

摘要： A navigable map database, stored on a computer-readable medium and used with a navigation application program, includes data which are spatially parcelized into a plurality of parcels. Associated with each of the plurality of parcels is a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area. Also associated with each of the parcels is a second index associating each of the data in the parcel with at least one of the sub-areas. Further disclosed is a method for producing a navigable map database which is parcelized into a plurality of parcels, wherein each of the plurality of parcels includes a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area and a second index associating each of the data in the parcel with at least one of the sub-areas. Also further disclosed are a program and method for finding data in one or more parcels that match a spatial search criterion using a navigable map database that is parcelized into a plurality of parcels, wherein each of the plurality of parcels includes a first index which associates the area represented by the data in the parcel with a plurality of sub-areas formed of the area and a second index associating each of the data in the parcel with at least one of the sub-areas. The program and method use the first and second indices to identify which of the data in at least one of the plurality of parcels satisfy the spatial search criterion.

摘要翻译： 存储在计算机可读介质上并与导航应用程序一起使用的导航地图数据库包括空间包装成多个包裹的数据。 与多个宗地中的每一个相关联的是将由包裹中的数据表示的区域与由该区域形成的多个子区域相关联的第一索引。 还与每个宗地相关联的是将宗地中的每个数据与至少一个子区域相关联的第二索引。 进一步公开的是一种生产导航地图数据库的方法，该导航地图数据库被包裹成多个宗地，其中多个宗地中的每一个宗地都包括第一索引，该索引将包裹中的数据表示的区域与形成的多个子区域相关联 以及将所述包裹中的每个数据与所述子区域中的至少一个相关联的第二索引。 还进一步公开的是一种用于使用包裹成多个宗地的可导航地图数据库来查找与空间搜索准则匹配的一个或多个宗地中的数据的程序和方法，其中所述多个宗地中的每一个包括第一索引， 由包括由该区域形成的多个子区域的包裹中的数据表示的区域和将包裹中的每个数据与至少一个子区域相关联的第二索引。 程序和方法使用第一和第二索引来识别多个宗地中的至少一个宗地中的哪一个数据满足空间搜索准则。

公开(公告)号：US5968109A

公开(公告)日：1999-10-19

申请号：US740295

申请日：1996-10-25

申请人： Vijaya S. Israni ,  Richard A. Ashby ,  Paul M. Bouzide ,  John C. Jasper ,  Robert P. Fernekes ,  Gregory M. Nyczak ,  Nicholas E. Smith ,  David S. Lampert ,  James A. Meek ,  Aaron I. Crane

发明人： Vijaya S. Israni ,  Richard A. Ashby ,  Paul M. Bouzide ,  John C. Jasper ,  Robert P. Fernekes ,  Gregory M. Nyczak ,  Nicholas E. Smith ,  David S. Lampert ,  James A. Meek ,  Aaron I. Crane

IPC分类号： G01C21/00 ,  G01C21/32 ,  G06F17/30 ,  G06T11/60 ,  G08G1/0968 ,  G08G1/0969 ,  G09B29/10

CPC分类号： G08G1/096827 ,  G01C21/32 ,  G06F17/30241 ,  G08G1/0969 ,  G09B29/106 ,  Y10S707/99943

摘要： An improved method and system for storage of geographic data on physical storage media. The geographic data are stored in a manner that facilitates and enhances use and access of the data by various navigation application functions in navigation systems that use the data. The geographic data includes a parcelization that separates the geographic data into parcels having less than or equal to a maximum parcel size but having at least a desired fill percentage. The parcelization method also provides for a division arrangement that facilitates addressing and identification of the parcels. According to a further aspect, the geographic data includes special nodal entities that are used to collapse complex intersections, such as roundabouts, cloverleaves, and divided highways, into simpler data representations. The special nodal entities are associated with road segment data entities and used in a route calculation program in place of regular node entities. Further, the geographic data include a normalized attribute array that includes reoccurring combinations of certain selected attributes of the geographic data. Indices to the array are included in place of data corresponding to the selected attributes. When a navigation application program requests data, an entry in the normalized attribute table pointed to by an index in the data is used to return the requested data in the particular combination of attributes from the normalized attribute array. The geographic data is compiled by a method that facilitates access to the data on a physical medium. According to the compilation method, data files to be stored on the medium are organized into parcels. The data records within the data files are identified by the parcel in which they are located. An arrangement of all the data files on the medium is determined and a parcel identification related to the medium is assigned to each parcel. Cross references between data records are updated to include the assigned parcel identifications and the parcels are stored on the medium.

公开(公告)号：US6038559A

公开(公告)日：2000-03-14

申请号：US39583

申请日：1998-03-16

申请人： Richard A. Ashby ,  Paul M. Bouzide ,  Srinivasa Doddapaneni ,  Robert P. Fernekes ,  Matthew Friederich ,  Vijaya S. Israni ,  John C. Jasper ,  Asta Kavakh ,  William McDonough ,  James A. Meek ,  Senthil K. Natesan ,  Nicholas E. Smith

发明人： Richard A. Ashby ,  Paul M. Bouzide ,  Srinivasa Doddapaneni ,  Robert P. Fernekes ,  Matthew Friederich ,  Vijaya S. Israni ,  John C. Jasper ,  Asta Kavakh ,  William McDonough ,  James A. Meek ,  Senthil K. Natesan ,  Nicholas E. Smith

IPC分类号： G09B29/00 ,  G01C21/00 ,  G01C21/32 ,  G06F17/30 ,  G06T11/60 ,  G08G1/0969

CPC分类号： G01C21/32 ,  Y10S707/99932 ,  Y10S707/99934 ,  Y10S707/99945 ,  Y10S707/99948

摘要： A geographic database for use with a navigation application program that provides navigation features to an end-user. The geographic database includes data entities that represent segments of roads and additionally includes data entities that represent aggregations of segments of roads. The data entities that represent aggregations of segments of roads are used during a route calculation by the navigation application to suppress evaluation of roads of lesser functional rank thereby enhancing performance of the navigation system. According to one aspect, each of the data entities that represent segments of roads that represents a segment of a road that together with at least one other segment of a road forms part of an aggregation which is represented by one of the data entities that represent aggregations of segments of roads includes a reference thereto. According to another aspect, each of the data entities that represent aggregations of segments of roads refers to data entities that are abbreviated representations of the segments of roads included in the represented aggregation. Each of the data entities that are abbreviated representations of the segments of roads refers to a corresponding one of the data entities that represent segments of roads that represents the same respective segment of road. According to this aspect, at least some of the data entities that represent aggregations of segments of roads are stored separately from the data entities that are abbreviated representations of the segments of roads included in the represented aggregation. According to a further aspect, the navigation application program uses the references between the data entities that represent segments of roads, the data entities that represent aggregations of segments of roads, and the data entities that are abbreviated representations of the segments of roads included in the represented aggregation to provide navigation features, including evaluating which data entities to use for route calculation and ascertaining whether a solution route has been found.

公开(公告)号：US06473770B1

公开(公告)日：2002-10-29

申请号：US10044580

申请日：2001-10-23

申请人： Michael Livshutz ,  Vijaya S. Israni ,  Richard A. Ashby ,  Paul M. Bouzide ,  Srinivasa Doddapaneni ,  Robert P. Fernekes ,  Matthew Friederich ,  John C. Jasper ,  Asta Kavakh ,  William McDonough ,  James A. Meek ,  Senthil K. Natesan ,  Nicholas E. Smith

发明人： Michael Livshutz ,  Vijaya S. Israni ,  Richard A. Ashby ,  Paul M. Bouzide ,  Srinivasa Doddapaneni ,  Robert P. Fernekes ,  Matthew Friederich ,  John C. Jasper ,  Asta Kavakh ,  William McDonough ,  James A. Meek ,  Senthil K. Natesan ,  Nicholas E. Smith

IPC分类号： G06F1730

CPC分类号： G01C21/32 ,  Y10S707/99931 ,  Y10S707/99934 ,  Y10S707/99935 ,  Y10S707/99944

摘要： A geographic database for use with a navigation application program that provides navigation features to an end-user. The geographic database includes a plurality of data records of a first type and a plurality of data records of a second type. The plurality of records of the first type are organized into a plurality of parcels, each of which includes a plurality of data records of the first type and the plurality of records of the second type are organized into a plurality of parcels, each of which includes a plurality of data records of the second type. The parcels of data records of the first type are interleaved with the parcels of data records of the second type. This interleaving enables navigation functions that use these different types to access these different types more quickly and efficiently, thereby enhancing navigation system performance. Also disclosed is a method for forming a geographic database that includes a plurality of data records that represent geographic features and which can be used in a navigation system. The method includes the step of interleaving parcels containing pluralities of data records of a first type with parcels containing pluralities of data records of a second type.

摘要翻译： 用于与最终用户提供导航功能的导航应用程序一起使用的地理数据库。 地理数据库包括第一类型的多个数据记录和第二类型的多个数据记录。 第一类型的多个记录被组织成多个包裹，每个包裹包括第一类型的多个数据记录，并且第二类型的多个记录被组织成多个包裹，每个包裹包括 第二类型的多个数据记录。 第一类型的数据记录的包裹与第二类型的数据记录的包裹交织。 该交错使得能够使用这些不同类型的导航功能更快更有效地访问这些不同类型，从而增强导航系统的性能。 还公开了一种用于形成包括表示地理特征并且可以在导航系统中使用的多个数据记录的地理数据库的方法。 该方法包括将包含第一类型的多个数据记录的包裹交织到包含多个第二类型的数据记录的包裹的步骤。

公开(公告)号：US06507850B1

公开(公告)日：2003-01-14

申请号：US09467276

申请日：1999-12-20

申请人： Michael Livshutz ,  Richard A. Ashby ,  Paul M. Bouzide ,  Srinivasa Doddapaneni ,  Robert P. Fernekes ,  Matthew Friederich ,  Vijaya S. Israni ,  John C. Jasper ,  Asta Kavakh ,  William McDonough ,  James A. Meek ,  Senthil K. Natesan ,  Nicholas E. Smith

发明人： Michael Livshutz ,  Richard A. Ashby ,  Paul M. Bouzide ,  Srinivasa Doddapaneni ,  Robert P. Fernekes ,  Matthew Friederich ,  Vijaya S. Israni ,  John C. Jasper ,  Asta Kavakh ,  William McDonough ,  James A. Meek ,  Senthil K. Natesan ,  Nicholas E. Smith

IPC分类号： G06F1730

CPC分类号： G01C21/32 ,  Y10S707/99932 ,  Y10S707/99934 ,  Y10S707/99945 ,  Y10S707/99948

摘要： A geographic database for use with a navigation application program that provides navigation features to an end-user. The geographic database includes a plurality of data records of a first type and a plurality of data records of a second type. The plurality of records of the first type are organized into a plurality of parcels, each of which includes a plurality of data records of the first type and the plurality of records of the second type are organized into a plurality of parcels, each of which includes a plurality of data records of the second type. The parcels of data records of the first type are interleaved with the parcels of data records of the second type. This interleaving enables navigation functions that use these different types to access these different types more quickly and efficiently, thereby enhancing navigation system performance. Also disclosed is a method for forming a geographic database that includes a plurality of data records that represent geographic features and which can be used in a navigation system. The method includes the step of interleaving parcels containing pluralities of data records of a first type with parcels containing pluralities of data records of a second type.

公开(公告)号：US06362779B1

公开(公告)日：2002-03-26

申请号：US09660329

申请日：2000-09-12

申请人： James A. Meek ,  Paul Crowley ,  Paul M. Bouzide

发明人： James A. Meek ,  Paul Crowley ,  Paul M. Bouzide

IPC分类号： G01S502

CPC分类号： G01C21/26

摘要： A system and method for providing updated geographic data for use by a navigation application program. The navigation application program is at a first version level and uses geographic data in a geographic database. An updated geographic database is provided to the navigation application program. The updated geographic database is at a second version level which is later than the first version level. Also provided to the navigation application program are one or more replacement routines. These replacement routines may be stored with the updated geographic database on a computer-readable medium or may be provided separately. The one or more replacement routines are used by the navigation application program either at initialization or during runtime. The one or more replacement routines are called to access or use the data in the updated geographic database. The one or more replacement routines are preferably in an interpretive language and executed by a virtual processor. The virtual processor may be part of the navigation application program. The one or more replacement routines can be used by the navigation application program thereby enabling the navigation application program which is at the first version level to use the updated geographic data which is at second version level.

摘要翻译： 一种用于提供更新的地理数据以供导航应用程序使用的系统和方法。 导航应用程序处于第一版本级别，并使用地理数据库中的地理数据。 更新的地理数据库被提供给导航应用程序。 更新的地理数据库处于比第一版​​本级别晚的第二版本级别。 还提供给导航应用程序的是一个或多个替换程序。 这些替换例程可以与更新的地理数据库一起存储在计算机可读介质上，或者可以单独提供。 导航应用程序在初始化或运行时都使用一个或多个替换程序。 调用一个或多个替换例程来访问或使用更新的地理数据库中的数据。 一个或多个替换例程优选地是解释语言并由虚拟处理器执行。 虚拟处理器可以是导航应用程序的一部分。 导航应用程序可以使用一个或多个替换例程，从而使处于第一版本级别的导航应用程序能够使用处于第二版本级别的更新的地理数据。

公开(公告)号：US06121924A

公开(公告)日：2000-09-19

申请号：US570

申请日：1997-12-30

申请人： James A. Meek ,  Paul Crowley ,  Paul M. Bouzide

发明人： James A. Meek ,  Paul Crowley ,  Paul M. Bouzide

IPC分类号： G01C21/26 ,  H04B7/185 ,  G01S5/02

CPC分类号： G01C21/26

摘要： A system and method for providing updated geographic data for use by a navigation application program. The navigation application program is at a first version level and uses geographic data in a geographic database. An updated geographic database is provided to the navigation application program. The updated geographic database is at a second version level which is later than the first version level. Also provided to the navigation application program are one or more replacement routines. These replacement routines may be stored with the updated geographic database on a computer-readable medium or may be provided separately. The one or more replacement routines are used by the navigation application program either at initialization or during runtime. The one or more replacement routines are called to access or use the data in the updated geographic database. The one or more replacement routines are preferably in an interpretive language and executed by a virtual processor. The virtual processor may be part of the navigation application program. The one or more replacement routines can be used by the navigation application program thereby enabling the navigation application program which is at the first version level to use the updated geographic data which is at second version level.