US 10,008,110 B1Granted

Detecting restrictions on turning paths in digital maps

AssigneeMapbox, Inc.

InventorsMorgan Herlocker, Camille Teicheira

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method comprises identifying, in an electronic map, road data and intersection data, wherein the intersection data specifies an approach and two or more exits from the approach, bounding the approach using a bounding box around the entrance to an approach, identifying, using the bounding box, traces associated with the approach, wherein each trace identifies a path of a vehicle on one or more of the roads, for each trace of the plurality of traces, identifying which of the two or more exits most closely matches the particular trace, generating histograms based on a time period and which of the two or more exits most closely matches each trace of the plurality of traces, determining, using the histograms, whether one or more threshold values associated with one of the two or more exits is satisfied, sending a notification signal when the one or more threshold values is satisfied.

Claims24

Dependent claims

A data processing method providing an improvement in signaling a notification when movement signals from vehicles are inconsistent with digitally stored map data, the method comprising:

identifying, in an electronic map comprising road data specifying a plurality of roads, intersection data specifying an intersection where two or more of the roads share a vertex, wherein the intersection data comprises (1) approach data specifying an approach that is an entrance for a vehicle into the intersection and (2) exit data specifying two or more exits from the approach;
accessing a stored data structure comprising a plurality of bounding boxes comprising data values in memory representing points or lines that surround the approach, one of the bounding boxes being associated with the approach;
identifying a plurality of traces;
determining a map region associated with each of the plurality of traces based on a R-tree search of the plurality of bounding boxes;
based on the determining, identifying a subset of the traces that cross the bounding box of the approach, and wherein each of the plurality of traces identifies a path of a vehicle on one or more of the plurality of roads;
for each trace of the plurality of traces that cross the bounding box of the approach, identifying which of the two or more exits from the approach most closely matches the particular trace;
generating histogram data comprising a plurality of histograms based on a time period and which of the two or more exits from the approach most closely matches each trace of the plurality of traces;
determining, using the histogram data, whether one or more threshold values associated with one of the two or more exits is satisfied;
and
sending a notification signal when the one or more threshold values is satisfied.

7 more elements

A system comprising:

a database;
one or more servers communicatively connected to the database, the one or more servers comprising one or more processors and electronic digital memory storing one or more sequences of instructions which, when executed by the one or more processors, cause the one or more processors to perform:
identifying, in an electronic map comprising road data specifying a plurality of roads, intersection data specifying an intersection where two or more of the roads share a vertex, wherein the intersection data comprises (1) approach data specifying an approach that is an entrance for a vehicle into the intersection and (2) exit data specifying two or more exits from the approach;
accessing a stored data structure comprising a plurality of bounding boxes comprising data values in memory representing points or lines that surround the approach, one of the bounding boxes being associated with the approach;
identifying a plurality of traces;
determining a map region associated with each of the plurality of traces based on a R-tree search of the plurality of bounding boxes;
based on the determining, identifying a subset of the traces that cross the bounding box of the approach, and wherein each of the plurality of traces identifies a path of a vehicle on one or more of the plurality of roads;
for each trace of the plurality of traces that cross the bounding box of the approach, identifying which of the two or more exits from the approach most closely matches the particular trace;
generating histogram data comprising a plurality of histograms based on a time period and which of the two or more exits from the approach most closely matches each trace of the plurality of traces;
determining, using the histogram data, whether one or more threshold values associated with one of the two or more exits is satisfied;
and
sending a notification signal when the one or more threshold values is satisfied.

9 more elements

Dependencies are inferred from the claim text.