Link-node maps based on open area maps

• US 8,417,446 B2
• Filed: 06/24/2010
• Issued: 04/09/2013
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq B.V.
• Inventors: Mays, Joseph P.
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US12/822,350
• Publication Number:
  US 20100299065A1
• Time in Patent Office: 1,020 Days
• Field of Search: 701/409, 701/410, 701/433, 701/25, 701/28, 701/737, 701/802, 382/100, 382/218, 382/113, 382/153
• US Class Current: 701/409
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G09B 29/003 Maps
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B

Abstract

Systems and methods for generating and using geographic data are disclosed. For example, one method comprises generating and/or identifying an open area map. A route is generated using the open area map. A path segment record and/or a node record is created based on the generated route. The path segment record and/or the node record may be stored in a geographic database.

Claims

1. A method of generating geographic data for navigation-related functions, the method comprising:

obtaining a pre-existing image of a layout, the layout representing a real-world area in which a person moves about and wherein the pre-existing image include walls;

using the pre-existing image to form a grid of contiguous tiles, wherein the grid has a shape that corresponds to a pedestrian-accessible contiguous sub-area within the real-world area and wherein the shape has a boundary that corresponds to the walls in the pre-existing image;

generating a routable open area map as a function of the grid of contiguous tiles, wherein the routable open area map is configured to be displayed via an end user device;

providing, via the end user device, an end user associated with the end user device with point-to-point routing within the routable open area map, wherein the point-to-point routing comprises calculating a route from one point corresponding to the pre-existing image to another point corresponding to the pre-existing image, the calculating of the route not being based on one or more path segments determined prior to the calculating;

creating a path segment record representing a portion of the generated route; and

storing the path segment record in a geographic database, the path segment record configured to be retrieved to form a navigation route.

2. The method of claim 1, wherein the path segment record comprises a data representation of a link having two endpoints.

3. The method of claim 2, wherein the two end points are each represented by respective node records.

4. The method of claim 1, further comprising:

determining a node record along the generated route by identifying an intersection between the calculated route and another calculated route.

5. The method of claim 4, wherein the node record corresponds to an endpoint of the path segment record.

6. The method of claim 4, further comprising:

converting the node record to a shape point attribute that is associated with the path segment record.

7. The method of claim 1, wherein the route from the one point to the other point comprises a route from an origin point to a destination point, and wherein the destination point is stored in the geographic database as a point-of-interest configured to be searched as a routable destination.

8. The method of claim 1, wherein the pre-existing image of the layout comprises an image of a building floor plan.

9. The method of claim 1, wherein the contiguous tiles are substantially uniform.

10. A computer-readable medium including computer-executable instructions for performing a method of generating a link-node map for an area, the method comprising:

overlaying an image of the area with a grid of tiles;

associating each tile that overlays a navigable portion of the image with a property that permits travel to another tile immediately adjacent thereto that overlays another navigable portion of the image;

generating a routable open area map as a function of the grid of tiles, the routable open area map configured to be displayed via an end user device;

providing, via the end user device, an end user associated with the end user device with point-to-point routing within the routable open area map, wherein the point-to-point routing comprises calculating a plurality of routes between a plurality of points of the image, the calculating not being dependent upon one or more path segments determined prior to the calculating;

creating node records that correspond to a plurality of points along the generated plurality of routes,

wherein link data records are formed as segments having two node records as respective endpoints.

11. The method of claim 10, wherein at least some of the plurality of points comprise intersection points between the calculated plurality of routes.

12. The method of claim 10, further comprising:

clustering the node records based on a spatial criteria;

reducing a number of the node records by combining at least some of the node records into a single node record as a function of the clustering; and

storing the reduced number of node records and the associated link data records in a navigation database.

13. The method of claim 10, further comprising:

converting at least some of the node records into shape point records corresponding to respective link data records, the shape point records identifying a certain shape of a portion of a path represented by the respective link data records.

14. The method of claim 10, further comprising:

for each of the points selected as a destination point when calculating the plurality of routes, generating a point-of-interest attribute; and

storing each point-of-interest attribute in a navigation database.

15. The method of claim 10, further comprising:

designating a non-navigable property to tiles corresponding to an obstruction in the image.

16. The method of claim 15, wherein the obstruction comprises a wall.

17. A navigation database for generating a route from an origin to a destination, the navigation database created from a method of generating navigation data from an open area mesh map, the method comprising:

identifying a routable map data structure including a grid of tiles corresponding to an image of an area, the tiles associated with navigable properties to generate routes from one portion of the grid associated with a point of the image to another portion of the grid associated with another point of the image, the routable map data structure configured to be displayed via an end user device;

providing, via the end user device, an end user associated with the end user device with point-to-point routing within the routable map data structure, wherein the point-to-point routing comprises calculating a route from an origin to a destination based on the routable map data structure, the calculating not being based on one or more path segments determined prior to the calculating;

creating node records corresponding to a plurality of points along the generated route; and

storing the node records to form the navigation database, the node records configured to be retrieved to form a navigation route.

18. The method of claim 17, further comprising:

creating path segment records representing portions of the calculated route, the node records corresponding to respective endpoints of the path segment records; and

storing the path segment records along with the node records to form the navigation database.

19. A method of routing from an origin to a destination using a link-node map on a navigation device, the method comprising:

receiving a selection input corresponding to a destination point; and

generating a route from an origin point to the destination point, wherein generating the route includes retrieving a first path segment record from a geographic database;

wherein the first path segment record is created from a method of generating navigation data from an open area mesh map comprising;

obtaining a routable map data structure including a grid of tiles corresponding to an image of an area, the tiles associated with navigable properties allowing for point-to-point routing, the routable map data structure configured to generate a plurality of routes from any portion of the grid associated with a navigable point of the image to any other portion of the grid associated with another navigable point of the image, the routable map data structure configured to be displayed via an end user device;

providing, via the end user device, an end user with point-to-point routing within the routable map data structure, wherein the point-to-point routing comprises calculating a route from a first point to a second point based on the routable map data structure, the calculating not being based on one or more path segments determined prior to the calculating;

creating a plurality of path segment data records corresponding to a plurality of portions along the generated route, the plurality of path segment records including the first path segment record; and

storing the plurality of path segment data records in the geographic database.

20. A method of generating geographic data for navigation-related functions, the method comprising:

identifying a routable map data structure including a grid of tiles corresponding to an image of an area, the tiles associated with navigable properties allowing for point-to-point routing, the routable map data structure configured to generate a plurality of routes from any portion of the grid associated with a navigable point of the image to any other portion of the grid associated with another navigable point of the image, the routable map data structure configured to be displayed via an end user device;

providing, via the end user device, an end user associated with the end user device with point-to-point routing within the routable map data structure, wherein the point-to-point routing comprises calculating a route from an origin point to a destination point based on the routable map data structure, the calculating not being based upon one or more path segments determined prior to the calculating;

creating path segment data records by dividing the generated route into a plurality of portions; and

storing the path segment data records in a navigation database, the path segment data records configured to be retrieved to form a navigation route.

21. The method of claim 20, wherein each path segment data record is associated with node data records, the node data records corresponding to endpoints of the path segment data records.

22. The method of claim 20, wherein the routable map data structure does not include path segment records.