Vehicle Route Representation Creation
AssigneeMicrosoft Corporation
InventorsJohn Krumm, Lili Cao
Life of this patent
Estimating the term…
Abstract
Techniques and systems are disclosed that provide for creating an accurate representation of a roadway network, such as for planning vehicle travel routes. Positioning data is obtained, such as GPS data points from a plurality of vehicles, which mark traces of vehicular travel. A location of a trace is clarified using adjustment forces that are related to the traces, for example, to form coherent groups of traces. From these groups of clarified traces, a graph line is created by merging the traces.
Claims20
A method for generating graph-line maps of vehicular routes, comprising:
- obtaining a plurality of positioning data marking traces of vehicular travel;
- clarifying a location of a trace;
- and
- merging related traces into a graph line.
A system for generating graph-line maps of vehicular routes, comprising:
- a data storage component configured to store a plurality of positioning data that marks traces of vehicular travel;
- a clarification component operably coupled to the data storage component, and configured to adjust a location of a trace;
- and
- a graph line producing component configured to merge related traces into a graph line.
A method for generating graph-line maps of vehicular routes, comprising:
- obtaining a plurality of global positioning satellite (GPS) data marking traces of vehicular travel, the traces comprising location nodes and edges between consecutive nodes, the nodes comprising GPS data points;
- clarifying a location of a trace using adjustment forces related to the trace to shift the location of the trace until a net force for the trace is balanced, comprising:
- shifting a location of a first trace based on an attraction force to a second trace;
- and
- shifting a location of the shifted trace based on an attraction force to its original location;
- clarifying a location of a trace comprising shifting a first trace based on a repelling force between a second trace and the first trace, where the second trace has different directionality than that of the first trace, using a function of the directionality of the first trace and the second trace to determine a magnitude of the repelling force;
- and
- merging related traces into a graph line comprising:
- determining whether a trace node should be merged with a first graph-line node;
- if the trace node is merged to a first graph-line node, creating an edge between the merged first graph-line node and a second graph-line node, if the second graph-line node is present and an edge between the nodes is not present;
- and
- if the trace node is not merged to the first graph-line node:
- adding the trace node to the graph line;
- and
- creating an edge between the added trace node and the second graph-line node if the second graph-line node is present.
Dependencies are inferred from the claim text.