System and Method for Multi-Plane Routing

• US 20130311089A1
• Filed: 05/16/2012
• Published: 11/21/2013
• Est. Priority Date: 05/16/2012
• Status: Active Grant

• Current Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Original Assignee: Primordial Performance LLC
• Inventors: Freed, Erik Stephen, Estes, Kyle Kenneth, Milbert, Randy Len
• Granted Patent: US 10,345,108 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• 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 method of representing discrete and sparsely-connected three-dimensional structures in a two-dimensional raster for purposes of route planning, the method comprising:

configuring each bit of each pixel of a raster to encode a multitude of planes;

configuring each bit of each pixel of the raster to encode a multitude of categories; and

configuring each bit of each pixel of the raster to encode a multitude of inter-plane connections.

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

3. The method of claim 2 further comprising generating a route using said graph.

4. The method of claim 1, wherein the step for configuring the bits of each raster pixel to encode a multitude of planes, categories, and inter-plane connections comprises:

configuring the bits of each said raster pixel to encode zero or more planes,

configuring the bits of each said raster pixel to encode zero or more categories,

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

determining the subset of raster pixels corresponding to the current shape,

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

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

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

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

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

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

associating said node with said category,

connecting said node to each adjacent intra-plane node, and

connecting said node to each adjacent inter-plane node.

6. The method of claim 5, wherein the step for determining a category for each non-empty pixel on each plane of said raster comprises decoding 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 whether said decoded category is empty, and if so, finding the nearest intra-plane pixel having an inter-plane connection to a pixel whose bits encode a non-empty category, and

decoding said non-empty category.

8. A system for representing discrete and sparsely-connected three-dimensional structures in a two-dimensional raster for purposes of route planning, comprising:

a pixel encoder for configuring each bit of each pixel of a raster to encode a multitude of planes;

the pixel encoder configuring each bit of each pixel of the raster to encode a multitude of categories; and

the pixel encoder configuring each bit of each pixel of the raster to encode a multitude of inter-plane connections.

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

10. The system of claim 9 further comprising a route generator for generating routes using said graph.

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 tangible computer-readable medium and configured to cause one or more computer processors to perform the steps of:

configuring each bit of each pixel of a raster to encode a multitude of planes;

configuring each bit of each pixel of the raster to encode a multitude of categories; and

configuring each bit of each pixel of the raster to encode a multitude of inter-plane connections.

12. The computer program product of claim 11 further comprising transforming said raster into a graph.

13. The computer program product of claim 12 further comprising generating a route using said graph.