System and method for multi-plane routing
First Claim
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 Assignments
0 Petitions
Accused Products
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).
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 17)
-
-
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. - View Dependent Claims (9, 10, 14, 15, 16, 18)
-
-
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. - View Dependent Claims (12, 13, 19)
-
Specification