Systems and methods for identifying grids of geographical region in map

Patent metadata

Field	Value
Publication number	US-11526536-B2
Application number	US-202015931520-A
Country	US
Kind code	B2
Filing date	May 13, 2020
Priority date	Jun 6, 2018
Publication date	Dec 13, 2022
Grant date	Dec 13, 2022

Abstract

The present disclosure includes artificial intelligence systems and methods for identifying grids for a geofence in an area in a map that includes a plurality of independently indexed regions of grids. The map is gridded into a plurality of grids and divided into a plurality of partitions. The methods include obtaining information of the geofence in the map, and determining a boundary grid series of the geofence from the plurality of grids. The methods include identifying at least one enclosed area in the geographical region, and upon determining that an enclosed area crosses two or more partitions, segmenting the enclosed area into two or more sub-areas. The methods also include determining boundary grids for each sub-area, and identifying internal grids in the sub-area for each sub-area. The methods further include identifying grids in the geographical region by collecting the boundary grids and the internal grids.

First claim

We claim:

1. An artificial intelligent system configured to identify grids for a geofence in an area in a map that includes a plurality of independently indexed regions of grids, comprising:
at least one storage medium storing the map and a set of instructions for identifying a geographical region;
at least one processor in communication with the at least one storage medium, wherein when executing the set of instructions, the at least one processor is directed to:
load at least part of a map from the at least one storage medium to at least one cache circuit;
generate a presentation of the at least part of the map, wherein the map is gridded into a plurality of grids and is divided into a plurality of partitions, each grid of the plurality of grids in the map is associated with a grid index, and grids in each partition are independently indexed;
obtain information of a geofence of a geographical region in the map;
determine a boundary grid series of the geofence from the plurality of grids;
identify at least one enclosed area in the geographical region based on the boundary grid series;
upon determining that an enclosed area of the at least one enclosed area crosses two or more partitions of the plurality of partitions, segment the enclosed area into two or more sub-areas so that each sub-area of the two or more sub-areas locates in only one partition of the plurality of partitions;
determine boundary grids for each of the two or more sub-areas;
for each of the two or more sub-areas, identify, from the plurality of grids, internal grids in the sub-area based on the boundary grids of the sub-area and an index of the partition in which the sub-area locates; and
identify grids in the geographical region by collecting the boundary grids of the two or more sub-areas and the internal grids in the two or more sub-areas.

2. The artificial intelligent system of claim 1 , wherein the information of the geofence includes a set of coordinate pairs corresponding to a plurality of boundary points; and
to determine the boundary grid series of the geofence, the at least one processor is further directed to:
identify, from the plurality of grids, the boundary grid series corresponding to the plurality of boundary points; and
conduct one or more operations including following steps:
obtaining two adjacent boundary points from the plurality of boundary points,
determining whether the two adjacent boundary points correspond to a same grid;
in response to a determination that the two adjacent boundary points correspond to the same grid, removing one of the two adjacent boundary points;
in response to a determination that the two adjacent boundary points correspond to two different grids, interpolating a boundary point between the two adjacent boundary points; and
updating the boundary grid series corresponding to the plurality of boundary points.

3. The artificial intelligent system of claim 1 , wherein
the boundary grid series includes grids from the plurality of grids of the map that the geofence passes through; and
to identify the at least one enclosed area, the at least one processor is further directed to:
determine whether the boundary grid series includes one or more pivot grids, wherein a pivot grid corresponds to at least two same grid indices; and
in response to a determination that the boundary grid series includes the one or more pivot grids, for each of the one or more pivot grids, identify an area in the geographical region on one side of the pivot grid as a first enclosed area and an area in the geographical region on the other side of the pivot grid as a second enclosed area different from the first enclosed area.

4. The artificial intelligent system of claim 3 , wherein to identify the at least one enclosed area, the at least one processor is further directed to:
generate an empty stack and an empty auxiliary map;
for each grid of the boundary grid series;
sequentially obtain the grid from the boundary grid series;
determine whether a grid index corresponding to the grid is in the auxiliary map;
in response to a determination that the grid index is not in the auxiliary map, push the grid index in the stack and input the grid index in the auxiliary map;
in response to a determination that the grid index is in the auxiliary map, designate the grid corresponding to the grid index as a pivot grid of the one or more pivot grids, designate the grid index as a pivot grid index, pop grid indices that are in the stack from the stack until the grid index in the top of the stack is the same as the pivot grid index, and designate girds corresponding to the popped grid indices as boundary grids of the first enclosed area; and

designate grids corresponding to grid indices remaining in the stack as boundary grids of the second enclosed area.

5. The artificial intelligent system of claim 1 , wherein the geofence is determined based on a circle defined by a center and a radius and
to identify the at least one enclosed area in the geographical region, the at least one processor is further directed to:
sample a plurality of sample points on the circle with a predetermined sample interval; and
determine boundary grids of the at least one enclosed area in the geographical region based on the plurality of sample points.

6. The artificial intelligent system of claim 5 , wherein the predetermined sample interval is associated with the radius of the circle and a resolution relating to a grid of the plurality of grids.

7. The artificial intelligent system of claim 5 , wherein the at least one processor is further directed to:
upon determining that two or more sample points of the plurality of sample points correspond to a same grid, remove one or more sample points from the two or more sample points so that there is only one sample point corresponding to the grid.

8. The artificial intelligent system of claim 1 , wherein after the segmenting of the at least one enclosed area into two or more sub-areas, the at least one processor is directed to:
determine overlapped edge grids where the two or more sub-areas intersect with one or more edges of the plurality of partitions; and
add the overlapped edge grids to the two or more sub-areas as the boundary grids of the two or more sub-areas.

9. The artificial intelligent system of claim 1 , wherein to identify, from the plurality of grids, internal grids in the sub-area, the at least one processor is directed to:
initialize a scanning matrix, wherein the scanning matrix includes a plurality of cells and each cell of the scanning matrix has a first value;
perform a first updating on the scanning matrix by filling a second value to each of a first plurality of cells of the scanning matrix, the first plurality of cells corresponding to the boundary grids of the sub-area;
for each cell of the scanning matrix after the first updating that has the first value, determine whether a grid corresponding to the cell is in the geographical region;
in response to a determination that the grid corresponding to the cell is in the geographical region,
perform a second updating on the scanning matrix by filling a third value to the cell of the scanning matrix; and
designate grids corresponding to the cells with the third value as the internal grids in the sub-area.

10. The artificial intelligent system of claim 9 , wherein the second value and third value are the same as each other.

11. A method for identifying grids for a geofence in an area in a map that includes a plurality of independently indexed regions of grids, implemented on a computing device having at least one storage medium storing the map and a set of instructions for identifyi

Assignees

• Beijing Didi Infinity Technology & Dev Co Ltd

Inventors

• Huang Zexiang
• Sheng Kehua
• Zhang Zhen
• Wang Yue
• Jiang Taixu
• Rao Quancheng

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G08G1/13

  the indicator being in the form of a map · CPC title

• H04W4/021

  Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences · CPC title

• G01C21/3889 Primary

  Transmission of selected map data, e.g. depending on route · CPC title

• G06F16/9574

  of access to content, e.g. by caching · CPC title