System and method for multi-plane routing

• US 10,345,108 B2
• Filed: 05/16/2012
• Issued: 07/09/2019
• Est. Priority Date: 05/16/2012
• Status: Active Grant

• Current Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Original Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Inventors: Freed, Erik Stephen, Estes, Kyle Kenneth, Milbert, Randy Len
• Primary Examiner(s): Smith, Isaac G
• Application Number:
  US13/472,866
• Publication Number:
  US 20130311089A1
• Time in Patent Office: 2,610 Days
• Field of Search: 701533, 701416, 701461, 701 3, 709203, 709246, 345441, 345581, 345600
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport

Abstract

A computer-implemented system and method distilling three-dimensional structure to a two-dimensional raster with multiple discrete planes for purposes of safe and accurate route planning including a map generator (100), pixel encoder (102), map transformer (106), and route generator (108). The map generator (100) generates a raster map by populating a blank map canvas with raster and vector data on a per-pixel basis and obtains values for pixels from the pixel encoder (102). The pixel encoder (102) encodes type, plane, and elevator information of features into pixels. The map transformer (106) converts the map produced by the map generator (100) into a weighted graph of nodes and edges suitable for route generation. The route generator (108) generates routes using the graph produced by the map transformer (106).

Claims

1. A computer-implemented method of representing discrete and sparsely-connected three-dimensional structures in a two-dimensional raster for purposes of route planning, the raster including a plurality of pixels, and each pixel including a plurality of bits, the method comprising:

configuring with a computer a first subset of bits in the plurality of pixels of the raster to encode a two-dimensional coordinate plane that each pixel occupies;

configuring with the computer a second subset of bits in the plurality of pixels of the raster to encode a plurality of categories indicating a type of land cover or structure the pixel represents;

configuring with the computer a third subset of bits in the plurality of pixels of the raster to encode a plurality of inter-plane connections between adjacent two-dimensional coordinate planes;

receiving, with the computer, a user request for a route from a start point to an end point; and

generating with the computer, using at least some of the configured first subset of bits, the configured second subset of bits, and the configured third subset of bits, a route from the start point to the end point for one or both of vehicle navigation and pedestrian navigation.

2. The method of claim 1 further comprising transforming with the computer said raster into a graph.

3. The method of claim 2 wherein the step of generating with the computer, using at least some of the configured first subset of bits, the configured second subset of bits, and the configured third subset of bits, the route from the start point to the end point includes generating with the computer the route using said graph.

4. The method of claim 1, further comprising:

iterating with the computer through one or more vector shapes, each shape specifying a plane and a category,

determining with the computer a subset of raster pixels corresponding to a current shape,

configuring with the computer the first subset of bits of each said raster pixel in said subset of raster pixels to encode said current shape'"'"'s plane,

configuring with the computer the second subset of bits of each said raster pixel in said subset of raster pixels to encode said current shape'"'"'s category, and

configuring with the computer the third subset of bits of each said raster pixel in said subset of raster pixels representing a shape endpoint to encode a connection from said current shape'"'"'s plane to another plane.

5. The method of claim 2, wherein transforming with the computer said raster into a graph comprises:

determining with the computer a category for each non-empty pixel on each plane of said raster,

creating with the computer a node for each said non-empty pixel on each said plane of said raster,

associating with the computer said node with said category,

connecting with the computer said node to each adjacent intra-plane node, and

connecting with the computer said node to each adjacent inter-plane node.

6. The method of claim 5, wherein determining with the computer a category for each non-empty pixel on each plane of said raster comprises decoding with the computer a category from the bits of each non-empty pixel on each plane of said raster.

7. The method of claim 6 further comprising:

determining with the computer whether said decoded category is empty, and if so, finding with the computer the nearest intra-plane pixel having an inter-plane connection to a pixel whose bits encode a non-empty category, and decoding with the computer said non-empty category.

17. The computer-implemented method of claim 1, wherein the start point and the end point correspond to two different locations represented within the raster.

8. A computer-implemented system for representing discrete and sparsely-connected three-dimensional structures in a two-dimensional raster for purposes of route planning, the raster including a plurality of pixels, each pixel including a plurality of bits, the system comprising:

a pixel encoder for configuring with a computer a first subset of bits in the plurality of pixels of the raster to encode a two-dimensional coordinate plane that each pixel occupies;

the pixel encoder configuring with the computer a second subset of bits in the plurality of pixels of the raster to encode a plurality of categories indicating a type of land cover or structure the pixel represents;

the pixel encoder configuring with the computer a third subset of bits in the plurality of pixels of the raster to encode a plurality of inter-plane connections between adjacent two-dimensional coordinate planes; and

a route generator which receives user input identifying a start point and an end point and generates with the computer a route, using at least some of the configured first subset of bits, the configured second subset of bits, and the configured third subset of bits, between the start point and the end point for one or both of vehicle navigation and pedestrian navigation.

9. The system of claim 8 further comprising a map transformer for transforming with the computer said raster into a graph.

10. The system of claim 9 wherein the route generator generates the route with the computer using said graph.

14. The system of claim 8, wherein the map transformer transforms the raster into a graph by:

determining with the computer a category for each non-empty pixel on each plane of said raster,

creating with the computer a node for each said non-empty pixel on each said plane of said raster,

associating with the computer said node with said category,

connecting with the computer said node to each adjacent intra-plane node, and

connecting with the computer said node to each adjacent inter-plane node.

15. The system of claim 14, wherein the map transformer determines the category for each non-empty pixel on each plane of said raster by decoding with the computer a category from the bits of each non-empty pixel on each plane of said raster.

16. The system of claim 15, wherein the map transformer further determines with the computer whether said decoded category is empty, and if so, finds with the computer the nearest intra-plane pixel having an inter-plane connection to a pixel whose bits encode a non-empty category, and then decodes with the computer said non-empty category.

18. The computer-implemented system of claim 8, wherein the start point and the end point correspond to two different locations represented within the raster.

11. A computer program product for representing discrete and sparsely-connected three-dimensional structures in a two-dimensional raster for purposes of route planning and including one or more computer-readable instructions embedded on a non-transitory computer-readable medium and configured to cause one or more computer processors to:

configure a first subset of bits in the plurality of pixels of the raster to encode a two-dimensional coordinate plane that each pixel occupies;

configure a second subset of bits in the plurality of pixels of the raster to encode a plurality of categories indicating a type of land cover or structure the pixel represents;

configure a third subset of bits in the plurality of pixels of the raster to encode a plurality of inter-plane connections between adjacent two-dimensional coordinate planes;

identify a start point and an end point based on input from a user; and

generate with the one or more computer processors a route between the start point and the end point using at least some of the configured first subset of bits, the configured second subset of bits, and the configured third subset of bits for one or both of vehicle navigation and pedestrian navigation.

12. The computer program product of claim 11 further comprising transforming with the one or more computer processors said raster into a graph.

13. The computer program product of claim 12 wherein the one or more computer processors generate the route using said graph.

19. The computer program product of claim 11, wherein the start point and the end point correspond to two different locations represented within the raster.