Method and system of polyline generation for rendering a richly attributed representation of a geographic region

• US 7,096,117 B1
• Filed: 01/20/2004
• Issued: 08/22/2006
• Est. Priority Date: 01/20/2004
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navteq North America LLC (HERE Holding Corporation)
• Inventors: Gale, William, McDonough, William
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WEISKOPF, MARIE
• Application Number:
  US10/760,993
• Time in Patent Office: 945 Days
• Field of Search: 701/208, 701/212, 707/102, 707/104.1, 342/357.13, 340/995.18
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system of polyline generation for rendering a representation of a geographic region is provided. Within a database containing geographic data, polyline data entities represent geographic features. Each polyline data entity is associated with a drawcode that defines attributes of the data entity, and organized within the database based on the drawcode. During a rendering process, a processor can read a group of data from a database stored on a disc that is organized to contain all polyline data entities associated with the same drawcode. The processor can then render all geographic features in an area that are similar using one or a minimum number of disc reads.

Claims

1. A computer-readable medium having computer readable data structure stored thereon for representing geographic features in a geographic region, the computer readable data structure comprising:

data entities that represent geographic features located in the geographic region; and

a plurality of drawcodes, wherein each drawcode represents a unique combination of attributes associated with the geographic features represented by the data entities, and wherein each of the data entities that represent the geographic features is associated with one of the drawcodes, and wherein each drawcode is associated with information that identifies drawing characteristics for rendering the geographic features represented by the data entities associated therewith.

2. The computer-readable medium of claim 1, wherein the data entities are organized on the computer-readable medium based on the drawcode of each data entity.

3. The computer-readable medium of claim 1, wherein each drawcode represents a collection of database attributes associated with the data entities.

4. The computer-readable medium of claim 1, further comprising header data that identifies the geographic region.

5. The computer-readable medium of claim 1, wherein the data entities are grouped into a plurality of parcels based on geographic location of the geographic features represented by the data entities and further wherein the data entities within each parcel are sorted by drawcode.

6. The computer-readable medium of claim 1, wherein the data entities are grouped into a plurality of parcels based on geographic location of the geographic features represented by the data entities.

7. The computer-readable medium of claim 1, wherein the data entities are organized into groups based on the drawcode of each data entity such that data entities that have the same drawcode are grouped together.

8. The computer-readable medium of claim 1, wherein the data entities are sorted on the computer-readable medium by drawcode such that data entities that have the same drawcode are stored adjacent to each other.

9. The computer-readable medium of claim 1, wherein each drawcode is associated with a unique combination of rank, road type, and road attribute associated with the data entities that represent geographic features.

10. The computer-readable medium of claim 1 wherein the geographic features represented by the data entities include roads.

11. The computer-readable medium of claim 1 wherein the geographic features represented by the data entities include 2-dimensional and 3-dimensional geographic features.

12. A method of producing a geographic database comprising:

identifying combinations of attributes associated with geographic features located in a geographic region that are in common among the geographic features;

associating drawcodes with the combinations of attributes, wherein each drawcode is associated with a distinct combination of attributes; and

storing data entities in the geographic database to represent the geographic features, wherein data entities having the same drawcode are stored together in groups.

13. The method of claim 12, wherein storing the data entities comprises storing data entities having the same drawcode adjacent to each other on a computer-readable medium.

14. The method of claim 12, wherein storing data entities in the geographic database to represent the geographic features comprises storing data entities having the same drawcode adjacent to each other in the geographic database.

15. The method of claim 12, wherein storing data entities in the geographic database to represent the geographic features comprises:

sorting the data entities by drawcode; and

storing the sorted data entities in the geographic database.

16. The method of claim 12, wherein storing data entities in the geographic database to represent the geographic features comprises storing the data entities in spatially organized parcels and sorted by drawcode when stored in each parcel.

17. The method of claim 12, further comprising creating a drawcode table that indicates definitions of each drawcode.

18. The method of claim 17, further comprising storing the drawcode table within a header in the geographic database.

19. The method of claim 17, wherein the drawcode table correlates drawcodes with combinations of geographic features found in the geographic region.

20. The method of claim 17, wherein the drawcode table includes information selected from the group consisting of a rank, a road type, and a road attribute.

21. The method of claim 12, wherein associating drawcodes with the combinations of attributes comprises assigning up to about 256 drawcodes.

22. The method of claim 12 wherein the geographic features represented by the data entities include roads.

23. The method of claim 12 wherein the geographic features represented by the data entities include 2-dimensional and 3-dimensional geographic features.

24. A method for storing computer readable data for representing geographic features in a geographic region, wherein the computer readable data includes a plurality of data entities, each data entity representing a geographic feature located in the geographic region, the method comprising;

associating each data entity with a drawcode, wherein each drawcode defines a distinct set of attributes associated with the geographic features;

sorting the plurality of data entities into groups by drawcode; and

storing in a computer-readable database, the sorted plurality of data entities.

25. The method of claim 24, wherein associating each data entity with a drawcode comprises assigning a drawcode to each data entity.

26. The method of claim 24, wherein the drawcode represents a collection of underlying database attributes used to form a polyline.

27. The method of claim 24, wherein associating each data entity with a drawcode comprises assigning up to about 256 drawcodes.

28. The method of claim 24, wherein storing in the computer-readable database the sorted plurality of data entities comprises storing the data entities in a sequential manner based on the drawcode of each data entity.

29. The method of claim 24, wherein sorting the plurality of data entities into groups by drawcode comprises sorting the plurality of data entities in groups having data entities associated with the same drawcode adjacent to each other in the computer-readable database.

30. A computer readable medium having stored therein instructions for causing a processing unit to execute the method of claim 24.

31. The method of claim 24 wherein the geographic features represented by the data entities include roads.

32. The method of claim 24 wherein the geographic features represented by the data entities include 2-dimensional and 3-dimensional geographic features.

33. A method for displaying images of portions of a geographic region on a computer display, wherein the images portray geographic features located in the geographic region, the method comprising:

reading from a computer readable database stored on a computer readable medium a group of data entities, wherein the data entities represent the geographic features, and wherein each data entity in the group has an associated drawcode which defines a combination of attributes associated with the represented geographic feature, the drawcode being associated with information that identifies drawing characteristics for rendering the represented geographic feature; and

rendering on the computer display images of the geographic features that correspond to the data entities in the group.

34. The method of claim 33, further comprising determining a portion of the geographic region to be displayed.

35. The method of claim 33, further comprising locating the group of data entities on the computer readable database.

36. The method of claim 35, wherein reading from the computer readable database stored on the computer readable medium the group of data entities comprises reading data associated with the geographic features and reading the associated drawcodes.

37. The method of claim 36, further comprising determining attributes of the geographic features represented by the data entities from the associated drawcodes.

38. The method of claim 37, wherein determining geographic features associated with the group of data entities comprises referencing a drawcode table to identify the geographic features associated with the group of data entities based on the associated drawcode of each data entity.

39. A computer readable medium having stored therein instructions for causing a processing unit to execute the method of claim 33.

40. The method of claim 33 wherein the geographic features represented by the data entities include roads.

41. The method of claim 33 wherein the geographic features represented by the data entities include 2-dimensional and 3-dimensional geographic features.

42. A system comprising:

a geographic data set stored on a computer readable medium, the geographic data set including data entities representative of geographic features in a geographic region, wherein each of the data entities is associated with one of a plurality of drawcodes, each of which represents a unique combination of attributes associated with a represented geographic feature;

a navigation application for providing navigation features to an end user; and

a processor operable to access the geographic data set to read a group of data entities and to execute the navigation application to display images on a computer display, wherein geographic features represented by data entities having the same drawcode are rendered with lines having the same color and thickness.

43. The system of claim 42, further comprising a positioning system for determining a location in the geographic region, and wherein the processor accesses the geographic data set to retrieve data associated with the location.

44. The system of claim 42, further comprising a user interface coupled to the processor and operable to receive an input from a user.

45. The system of claim 42 wherein the geographic features represented by the data entities include roads.

46. The system of claim 42 wherein the geographic features represented by the data entities include 2-dimensional and 3-dimensional geographic features.