Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-13
2002-04-02
Von Buhr, Maria N. (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C701S200000, C345S442000
Reexamination Certificate
active
06366927
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to navigation systems and in particular to geographic data sets for use in navigation systems.
Computer-based navigation systems for use on land have become available in a variety of forms and provide for a variety of useful features. One exemplary type of navigation system uses (1) one or more detailed data sets that represent one or more geographic areas or regions, (2) a navigation application program, (3) appropriate computer hardware, such as a microprocessor, memory, and data storage, and, optionally, (4) a positioning system.
Referring to
FIG. 1
, there is a diagram illustrating a configuration of an exemplary navigation system
10
. The navigation system
10
is a combination of hardware and software components which can be implemented in various different kinds of environments or on different platforms. For example, the navigation system
10
may be located in an automobile
12
. In an exemplary embodiment, the navigation system
10
includes appropriate hardware
14
which may include a GPS system
16
, an antenna
18
, sensors
20
coupled to sense the vehicle speed and distance traveled, and a compass
22
to sense the vehicle direction. In addition, the navigation system includes an appropriate computer
24
, including a CPU
26
and memory
28
as well as other appropriate hardware.
Included as part of the navigation system
10
is a drive
30
(or other suitable peripheral device) into which a data storage medium
32
can be installed. One or more geographic data sets
34
are stored on the storage medium
32
. In one embodiment, the storage medium
32
is a CD-ROM disc. In another alternative embodiment, the storage medium
32
may be a PCMCIA card in which case the drive
30
would be substituted with a PCMCIA slot. Various other storage media may be used, including fixed or hard disks, DVD (digital video disks) or other currently available storage media, as well as storage media that may be developed in the future. The embodiments disclosed herein may be used in other types of navigation systems, as explained below.
The navigation system
10
also includes a user interface
40
coupled to the computer
24
. The user interface
40
includes appropriate means for receiving instructions and input from an end-user as well as means for providing information back to the end-user. For example, the user interface
40
may include an input panel or keyboard into which an end-user may indicate a selection of a destination. The user interface
40
may also include a display or speakers (including speech synthesis hardware and software) by which the user can be informed of navigation information. For visual navigation information, the user interface
40
may provide features allowing the user to zoom a display in on or out of a particular geographic area to alternately display a larger geographic area or more detailed geographic information.
The positioning system may employ any of several well-known technologies to determine or approximate the end-user's physical locations in a geographic region. For example, the positioning system may employ a GPS-type system (global positioning system), a dead reckoning-type system, or combinations of these, or other systems, all of which are well-known in the art.
All of the components described above may be conventional (or other than conventional) and the manufacture and use of these components are known to those of skill in the art.
The navigation system
10
includes another data storage device
36
(or ROM) which is used to store a navigation application program
38
. (Alternatively, the application program
38
may be provided on the same storage device or medium
32
as the geographic data sets
34
.) The navigation application program
38
is a software program that uses the geographic data set
34
and the positioning system (when employed). The navigation application program
38
may include separate applications (or subprograms). These subprograms provide various navigation features to the end-user of the navigation system
10
. These features may include route calculation functions, maneuver generation functions, map display functions, vehicle positioning functions, destination resolution capabilities, and so on. The navigation features are provided to the end-user (e.g., the vehicle driver) by means of the user interface
40
. The navigation application program
38
may be written in a suitable computer programming language such as C, although other programming languages are also suitable.
During a typical usage of the navigation system
10
of
FIG. 1
, the navigation application program
38
is loaded from the ROM
36
into the memory
28
associated with the processor
26
. The computer
24
receives input from the user interface
40
. The input may include a request for navigation information. The computer
24
receives information from the positioning system hardware
14
. The information from the hardware
14
is used by the navigation application software
38
to determine the location, direction, speed, etc., of the vehicle
12
. The navigation application program
38
may provide the end-user with a graphical display (e.g. a “map”) of the end-user's specific location in the geographic region. In addition, the navigation application program may provide the end-user with specific directions to locations in the geographic area from wherever the end-user is located.
To provide these various navigation application features, the navigation system
10
uses the geographic data
34
stored on the storage medium
32
, optionally in conjunction with the output from the positioning system hardware
14
. The geographic data
34
may be in the form of one or more computer-readable files or databases that enable the navigation application program
38
to provide the supported features. For example, to enable the calculation of a route between two locations in the geographic region, the geographic data
34
may include route calculation data that includes the positions of roads and intersections in the geographic region, information about one-way streets, turn restrictions, stop signs, stop lights, speed limits, and so on.
When performing a map display function with the navigation system, the sizes, shapes, and relative positions of geographic features in a portion of a geographic region are portrayed on the display of the user interface
40
. These geographic features may include roads, intersections, and points-of-interest, as well as other features, such as lakes, railroad tracks, buildings, airports, stadiums, parks, mountain ranges, docks, ferries, tunnels, bridges, and so on. To provide this map display function, the geographic data set
34
may include cartographic data which allows the navigation application program
38
to display maps illustrating the size, shape, position, and character of these various geographic features on an attached display device. Zooming and panning of the displayed areas may also be supported.
Referring to
FIG. 2
, there is a diagram illustrating an exemplary configuration of a cartographic data set
34
(carto) used for map display. The data set
34
(carto) is part of the geographic data set
34
of
FIG. 1
which may include other kinds of data sets used for route calculation, maneuver generation, and other navigation functions. In
FIG. 2
, the data set
34
(carto) includes a (sub)set
42
of road segment data entities, e.g. seg(
1
), seg(
2
) . . . seg(n). Each road segment data entity represents a portion of a roadway in the geographic region. Associated with each road segment data entity record, seg( ), are data (such as nodes and attributes
46
(
1
),
46
(
2
) . . .
46
(n)) that facilitate portraying the respective represented road portions on the computer display device. The road segment data entities, seg(
1
), seg(
2
) . . . seg(n), may be implemented using standard types of data structures used in database construction.
Referring to
FIG. 3
, there is a map diagram illustrating a portion of the geographic regi
Ashby Richard A.
Lampert David S.
Meek James A.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corp.
Von Buhr Maria N.
LandOfFree
Method and system for representation and use of shape... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for representation and use of shape..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for representation and use of shape... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2904905