METHOD AND APPARATUS FOR GENERATING A COMPOSITE INDEXABLE LINEAR DATA STRUCTURE TO PERMIT SELECTION OF MAP ELEMENTS BASED ON LINEAR ELEMENTS

• US 20170186225A1
• Filed: 03/14/2017
• Published: 06/29/2017
• Est. Priority Date: 05/20/2014
• Status: Abandoned Application

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Barnes, Craig R.
• Application Number:
  US15/458,503
• Publication Number:
  US 20170186225A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2210/12 Bounding box

Abstract

A method, apparatus and computer program product are provided for generating a composite indexable linear data structure to permit selection of map elements based on linear elements. In the context of a method, map data and a selected linear element indication are received. The map data comprises a list of map elements. The method also includes extracting map elements within a bounding box, and indexing the extracted map elements. The indexing is spatial indexing. The method also includes correlating the indexed map elements with a plurality of sub segments of the linear element, and generating a composite indexable linear data structure based on the correlation of map elements with the plurality of sub-segments of the linear element.

Claims

1. A method comprising:

receiving map data and one or more selected linear element indications, wherein the map data comprises a list of map elements;

extracting, by a processor, map elements within a bounding box;

indexing, by the processor, the extracted map elements, wherein the indexing comprises spatial indexing;

searching the spatial index for map elements within a predetermined distance from the one or more selected linear elements;

generating a composite indexable linear data structure based on the correlation of map elements with the one or more selected linear elements; and

using the composite indexable linear data structure, providing for presentation of a map rendering, wherein the map elements corresponding to the composite indexable linear data structure are visually distinguished and enhanced with one or more of building footprint data or three-dimensional building mesh data.

2. The method of claim 1, wherein extracting map elements comprises:

extracting map elements from a spatial database.

3. The method of claim 1, wherein the extracted map elements comprise one or more of relational data, shape data, or keyhole markup language file data.

4. The method of claim 1, wherein the composite indexable linear data structure comprises a list of indexed map elements, wherein the list of indexed map elements comprises vector, hash table, or linked list elements.

5. The method of claim 1, further comprising:

sorting an indexable linear data structure by distance from a respective one of the one or more linear elements.

6. The method of claim 1, wherein each of the one or more linear elements is a street, path, or trail.

7. The method of claim 1, further comprising:

segmenting the one or more selected linear elements into a plurality of sub-segments;

searching the spatial index for map elements within a predetermined distance from the sub-segment; and

correlating the indexed map elements with a respective one of the one or more selected linear elements.

8. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processor, cause the apparatus to at least:

receive map data and one or more selected linear element indications, wherein the map data comprises a list of map elements;

extract map elements within a bounding box;

index the extracted map elements, wherein the indexing comprises spatial indexing;

search the spatial index for map elements within a predetermined distance from the one or more selected linear elements;

generate a composite indexable linear data structure based on the correlation of map elements with the one or more selected linear elements; and

use the composite indexable linear data structure, providing for presentation of a map rendering, wherein the map elements corresponding to the composite indexable linear data structure are visually distinguished and enhanced with one or more of building footprint data or three-dimensional building mesh data.

9. The apparatus of claim 8, wherein causing the apparatus to extract map elements comprises causing the apparatus to:

extract map elements from a spatial database.

10. The apparatus of claim 8, wherein the extracted map elements comprise one or more of relational data, shape data, or keyhole markup language file data.

11. The apparatus of claim 8, wherein the composite indexable linear data structure comprises a list of indexed map elements, wherein the list of indexed map elements comprises vector, hash table, or linked list elements.

12. The apparatus of claim 8, wherein the at least one memory and the computer program code are further configured to cause the apparatus to:

sort an indexable linear data structure by distance from a respective one of the one or more linear elements.

13. The apparatus of claim 8, wherein each of the one or more linear elements is a street, path, or trail.

14. The apparatus of claim 8, wherein the at least one memory and the computer program code are further configured to cause the apparatus to:

segment the one or more selected linear elements into a plurality of sub-segments;

search the spatial index for map elements within a predetermined distance from the sub-segment; and

correlate the indexed map elements with a respective one of the one or more selected linear elements.

15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions configured to:

receive map data and one or more selected linear element indications, wherein the map data comprises a list of map elements;

extract map elements within a bounding box;

index the extracted map elements, wherein the indexing comprises spatial indexing;

search the spatial index for map elements within a predetermined distance from the one or more selected linear elements;

generate a composite indexable linear data structure based on the correlation of map elements with the one or more selected linear elements; and

use the composite indexable linear data structure, providing for presentation of a map rendering, wherein the map elements corresponding to the composite indexable linear data structure are visually distinguished and enhanced with one or more of building footprint data or three-dimensional building mesh data.

16. The computer program product of claim 15, wherein the program code instructions to extract map elements comprise program code instructions to:

extract map elements from a spatial database.

17. The computer program product of claim 15, wherein the extracted map elements comprise one or more of relational data, shape data, or keyhole markup language file data.

18. The computer program product of claim 15, wherein the composite indexable linear data structure comprises a list of indexed map elements, wherein the list of indexed map elements comprises vector, hash table, or linked list elements.

19. The computer program product of claim 15, wherein the computer-executable program code portions further comprise program code instructions configured to:

sort an indexable linear data structure by distance from a respective one of the plurality of sub segments of the linear element.

20. The computer program product of claim 15, wherein the computer-executable program code portions further comprise program code instructions configured to:

segment the one or more selected linear elements into a plurality of sub-segments;

search the spatial index for map elements within a predetermined distance from the sub-segment; and

correlate the indexed map elements with a respective one of the one or more selected linear elements.