System and method for creating and organizing node records for a cartographic data map

• US 6,909,965 B1
• Filed: 12/28/2001
• Issued: 06/21/2005
• Est. Priority Date: 12/28/2001
• Status: Expired due to Term

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Beesley, Darin J.
• Primary Examiner(s): Cuchlinski, William
• Assistant Examiner(s): Tran, Dalena
• Application Number:
  US10/036,216
• Time in Patent Office: 1,271 Days
• Field of Search: 701/209, 701/206, 701/208, 701/207, 701/210, 701/200, 701/212, 340/990, 340/988, 340/995, 340/980
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures

Abstract

A method for organizing roadway network data in a memory storage device is provided. A data set indicative of a roadway network is provided. Proximity criteria for intersection nodes between the roads in the roadway network is identified. The intersection nodes are grouped into a node block based on the proximity criteria. Node records which contain data indicative of the nodes are stored as a group in the node block in contiguous memory.

Claims

1. A method for organizing roadway network data in a memory storage device, comprising:

providing a data set indicative of a roadway network;

identifying proximity criteria for intersections between roads in said roadway network, wherein each of said intersections is indicative of a node;

grouping said nodes into a node block based on said proximity criteria using a Hilbert space filling curve; and

storing node records containing data indicative of said nodes, said node records being stored as a group in said node block in contiguous memory.

2. A method for calculating a navigation route between first and second geographic locations, comprising:

providing a data set comprised of node blocks of data, said data indicative of a roadway network of roads intersecting at intersection nodes, wherein said data includes proximity criteria indicative of said intersection nodes;

accessing a first node record including data indicative of a single first node at a first geographic location, said first node record included in a first node block, said first node record containing adjacency information indicative of an estimated location of only adjacent nodes directly connected to said first node;

calculating a bearing direction from said first geographic location towards a second geographic location based on said adjacency information included in said first node record;

accessing one of a header or footer included in said first node block, said header or footer including common feature data indicative of traffic characteristics for said roads; and

accessing a second node record included in said first node block, said second node record including data indicative of a navigation route, said navigation route contiguous from said first node record.

3. The method of claim 2, wherein said first and second node records are stored contiguously in a memory storage device.

4. The method of claim 2, wherein said proximity criteria includes at least one of a latitude coordinate and a longitude coordinate for each of said node block.

5. The method of claim 2, wherein the calculating step further comprises:

identifying at least one adjacent node from a list of adjacent nodes, said list stored in said first node record;

identifying at least one of a bearing component and a distance component for each said adjacent node; and

choosing a next node from said adjacent nodes based on at least one of said proximity criteria and said common feature data.

6. The method of claim 2, further comprising choosing a next node based on at least one of a bearing component and a scale factor.

7. The method of claim 2, wherein said common feature data further comprises data indicative of at least road level and speed data.

8. The method of claim 2, further comprising calculating a cost from said first geographic location to a next node, said cost based on said common feature data.

9. The method of claim 2, wherein each said node block includes up to 255 intersection nodes.

10. The method of claim 2, wherein each said node block further comprising a group of node records based on said proximity criteria.

11. A data structure embodied on a computer readable medium for defining a roadway network having road segments intersecting at nodes, the data structure comprising:

node records containing data indicative of corresponding nodes in a roadway network, a first node record corresponding to a single first node and containing adjacency information indicative of an estimated location of only adjacent nodes directly connected to said first node, said estimated location being determined with respect to said first node, wherein said node records further comprise fields storing bearing data indicative of directions in which corresponding road segments extend from said corresponding nodes.

12. The data structure of claim 11, wherein said node records further comprise a list of sub-records, each of said sub-records containing data indicative of said estimated location for a corresponding one of said adjacent nodes.

13. The data structure of claim 11, wherein said node records further comprise fields storing distance data indicative of distances between adjacent nodes.

14. The data structure of claim 11, wherein said node records further comprise fields storing data indicative of outgoing and straight-line bearings between two nodes, said outgoing bearing representing a direction of travel from one of said two nodes over a road segment to another of said two nodes, said straight-line bearing representing a direction of a straight line connecting said two nodes.

15. The data structure of claim 11, further comprising a table containing data indicative of features describing road segments in a roadway network, each of said node records containing a field storing an index into said table, said index identifying a corresponding one of said features describing a road segment intersecting a corresponding node.

16. The data structure of claim 11, further comprising a node block record associated with a group of nodes that are geographically proximate one another, said node block record containing data indicative of geographic coordinates for a center of said group of nodes.

17. The data structure of claim 11, wherein said node records further comprising fields containing data indicative of a relative offset between geographic coordinates of each node and a predefined geographic reference point within the roadway network.

18. The data structure of claim 11, wherein said node records are ordered on the computer readable medium based on a geographic location of each node relative to geographic locations of surrounding nodes such that node records of geographically proximate nodes are stored near one another on the computer readable medium.

19. A navigation system comprising:

a first memory storing data sets indicative of roadway networks, said data sets stored in blocks of data wherein said blocks of data include geographical data indicative of nodes, said geographical data being stored as node records, each node record corresponding to a single node and containing adjacency information indicative of an estimated location of only adjacent nodes directly connected to said corresponding node, wherein said blocks of data include a plurality of said nodes in an equal plurality of said node records, said node records including a distance component and at least one bearing component associated with at least one adjacent node;

a second memory storing at least one said blocks of data temporarily;

a route calculation module calculating a planned route over the roadway network between source and destination locations based on the data stored in the second memory; and

a display displaying said route calculated by said route calculation module.

20. The navigation system of claim 19, wherein said blocks of data include at least one of a block header and block footer comprising characteristic information describing at least one road segment feature descriptive of roadway segments leading to at least two nodes in said blocks of data.

21. The navigation system of claim 19, wherein said blocks of data include a plurality of said nodes in an equal plurality of said node records, said plurality of said node records stored in adjacent memory locations.

22. The navigation system of claim 19, wherein said blocks of data include a table associated with a plurality of node records stored in said blocks of data, said table containing a list of features descriptive of road segments interconnecting said nodes, at least one node record containing an index into said table identifying a feature representative of a node associated with at least one node record.

23. The navigation system of claim 19, wherein said blocks of data include a single latitude and a single longitude coordinate based on said geographical data indicative of said nodes.

24. The navigation system of claim 19, wherein said node records are ordered on said first memory based on a geographic location of each node relative to geographic locations of surrounding nodes such that node records of geographically proximate nodes are stored near one another on said first memory.

25. A method for organizing roadway network data in a memory storage device, comprising:

providing a data set indicative of a roadway network containing roads and intersections between roads, said intersections representing nodes distributed in a multi-dimension array, said data set including node records uniquely associated with corresponding nodes;

assigning a unique number from a one-dimension array to each said node record based on a geographic location of a corresponding node relative to geographic locations of surrounding nodes such that geographically close nodes are assigned close unique numbers from the one-dimension array;

reordering said node records into a node list based on said unique numbers;

dividing said node list into at least first and second node blocks by grouping consecutively numbered node records proximate one another in said first and second node blocks; and

storing node records in said first node block in contiguous memory.

26. The method of claim 25, wherein said reordering step reorders said nodes into a one dimensional array of nodes based on said unique numbers.

27. The method of claim 25, wherein said storing step includes storing data indicative of a plurality of said nodes in an equal plurality of said node records, and storing said plurality of said node records in adjacent memory locations.

28. The method of claim 25, wherein said storing step stores said first node block in a long-term memory as a contiguous memory section having a length configured to be loaded into a work-space memory as a single, unitary block of node records.

29. The method of claim 25, further comprising storing with said first node block at least one of a block header and block footer comprising characteristic information describing at least one road segment feature descriptive of roadway segments leading to at least two nodes in said first node block.

30. The method of claim 25, further comprising storing a table associated with said node records grouped in said first node block, said table containing a list of features descriptive of road segments interconnecting said nodes, at least one node record containing an index into said table identifying a feature representative of a node associated with said at least one node record.

31. The method of claim 25, wherein said proximity criteria comprises at least one of a latitude coordinate and a longitude coordinate for each of said intersections.

32. The method of claim 25, further comprising:

for a first node in said data set, identifying an adjacent node and a road segment connecting said first node and said adjacent node;

identifying for said adjacent node a bearing component and a distance component representative of a direction of travel along, and length of, said road segment; and

storing said bearing and distance components in a node record associated with said first node.

33. The method of claim 25, further comprising:

identifying an outgoing bearing and a straight-line bearing between two nodes in said data set, said two nodes being connected by a road segment and by a straight line, said outgoing bearing representing a direction at which said road segment extends from one of said two nodes, said straight-line bearing representing a direction at which said straight line extends from said one of said two nodes.

34. The method of claim 25, further comprising:

identifying adjacency information for nodes directly connected to a first node and storing adjacency information for each of said nodes in a list of sub-records.

35. The method of claim 25, further comprising:

identifying a geographic center of said nodes grouped in said node block and storing said geographic center with said first node block.

36. The method of claim 25, further comprising:

identifying a relative offset between a geographic location of a first node in said first node block and a geographic center associated with said first node block, and storing said relative offset in a node record associated with said first node.

37. The method of claim 25, further comprising:

storing a table of features descriptive of road segments interconnecting nodes grouped in said first node block, and storing in each node record an offset to a location in memory at which said table is stored.