System and method for determining whether an object belongs to a target geo-fence

Patent metadata

Field	Value
Publication number	US-2020314589-A1
Application number	US-202016901043-A
Country	US
Kind code	A1
Filing date	Jun 15, 2020
Priority date	Nov 28, 2018
Publication date	Oct 1, 2020
Grant date	—

Abstract

Systems and methods for determining whether an object belongs to a target geo-fence are provided. The method may include: obtaining geographic coordinates corresponding to a geographic location of the object; determining information of a grid corresponding to the geographic coordinates; indexing the grid, based on the information of the grid, in a first grid database. The object may not belong to the target geo-fence if the indexed grid is not in the first grid database. The method may further include indexing the grid, based on the information of the grid, in a second grid database if the indexed grid is in the first grid database. The object may belong to the target geo-fence if the indexed grid is not in the second grid database. The method may further include determining whether the object belongs to the target geo-fence based on a relationship of the object and a local geo-fence if the indexed grid is in the second grid database.

First claim

1 . A system for determining whether an object belongs to a target geo-fence, comprising:
at least one storage device including one or more sets of instructions; at least one processor in communication with the at least one storage device, wherein when executing the one or more sets of instructions, the at least one processor is directed to:
obtain geographic coordinates corresponding to a geographic location of the object;
determine information of a grid corresponding to the geographic coordinates;
index the grid, based on the information of the grid, in a first grid database;
in response to a first negative result that the indexed grid is not in the first grid database:
determine that the object does not belong to the target geo-fence;

in response to a first positive result that the indexed grid is in the first grid database:
index the grid, based on the information of the grid, in a second grid database;
in response to a second negative result that the indexed grid is not in the second grid database:
determine that the object belongs to the target geo-fence; and

in response to a second positive result that the indexed grid is in the second grid database:
determine whether the object belongs to the target geo-fence based on a relationship of the object and a local geo-fence.

2 . The system of claim 1 , wherein the at least one processor is further directed to establish the first grid database, and
wherein to establish the first grid database, the at least one processor is further directed to:
obtain the target geo-fence;
obtain a plurality of grids corresponding to the target geo-fence, each of the plurality of grids including a polygon having a plurality of vertexes;
encode data corresponding to the plurality of grids into a first data structure, which includes identifiers of the plurality of grids and coordinates of the plurality of vertexes; and
write the encoded data in at least one non-transitory storage medium.

3 . The system of claim 2 , wherein the at least one processor is further directed to establish the second grid database, and
wherein to establish the second grid database, the at least one processor is further directed to:
obtain one or more border grids from the plurality of grids;
determine one or more local geo-fences based on the one or more border grids and the target geo-fence;
encode data corresponding to the one or more border grids and the one or more local geo-fences into a second data structure, which includes identifiers of the one or more border grids, identifiers of the one or more local geo-fences, coordinates of vertexes of each of the one or more border grids, and coordinates of vertexes of each of the one or more local geo-fences, wherein the vertexes of each of the one or more local geo-fences include one or more intersection points of the border grid and the local geo-fence; and
write the encoded data in the at least one non-transitory storage medium.

4 . The system of claim 3 , wherein to determine one or more local geo-fences based on the one or more border grids and the target geo-fence, the at least one processor is directed to:
for each of the one or more border grids,
determine a first linked list corresponding to the border grid and a second linked list corresponding to the target geo-fence respectively, wherein each node of either the first linked list or the second linked list corresponds to one vertex of the vertexes of the border grid or one vertex of the vertexes of the target geo-fence respectively;
determine the one or more of intersection points of the border grid and the target geo-fence;
update the first linked list and the second linked list based on the one or more intersection points; and
determine the one or more local geo-fences based on the updated first linked list and the updated second linked list.

5 . The system of claim 4 , wherein to determine the one or more local geo-fences based on the updated first linked list and the updated second linked list, the at least one processor is directed to:
for determining each of the one or more local geo-fences,
traverse the updated first linked list and the updated second linked list based on a predetermined traverse rule;
determine an intersection set of the border grid and the target geo-fence, the intersection set including the one or more intersection points of the border grid and the target geo-fence; and
determine the local geo-fence based on the intersection set.

6 . The system of claim 5 , wherein the predetermined traverse rule is associated with a starting point of the traverse, and a traverse sequence or a traverse switching order,
wherein the starting point of the traverse includes the vertex of the border grid that is outside of the target geo-fence or the vertex of the target geo-fence that is outside of the border grid; the traverse sequence includes a clockwise or a counterclockwise; and the traverse switching order includes alternate traversing the updated first linked list and the updated second linked list every time encountering an intersection point, excluding a first intersection point encountered.

7 . The system of claim 4 , wherein the first linked list and the second linked list are circular doubly linked lists.

8 . The system of claim 1 , wherein to determine whether the object belongs to the target geo-fence based on a relationship of the object and a local geo-fence, the at least one processor is further directed to:
determine that the object belongs to the local geo-fence if a ray, whose endpoint is the object, crosses an odd number of borders of the local geo-fence; and determine that the object does not belong to the local geo-fence if the ray, whose endpoint is the object, crosses an even number of borders of the local geo-fence.

9 . The system of claim 1 , wherein to determine whether the object belongs to the target geo-fence based on a relationship of the object and a local geo-fence, the at least one processor is further directed to:
determine a winding number associated with the object and the local geo-fence; determine that the object belongs to the local geo-fence if the winding number is unequal to zero; and determine that the object does not belong to the local geo-fence if the winding number is equal to zero.

10 . The system of claim 1 , wherein the grid has a shape of a regular hexagon.

11 . A method for determining whether an object belongs to a target geo-fence, the method implemented on a computing device having at least one processor and at least one computer-readable storage medium, the method comprising:
obtaining geographic coordinates corresponding to a geographic location of the object; determining information of a grid corresponding to the geographic coordinates; indexing the grid, based on the information of the grid, in a first grid database; in response to a first negative result that the indexed grid is not in the first grid database:
determining that the object does not belong to the target geo-fence;
in response to a first positive result that the indexed grid is in the first grid database:
indexing the grid, based on the information of the grid, in a second grid database;
in response to a second negative result that the indexed grid is not in the second grid database:
determining that the object belongs to the target geo-fence; and

in response to a second positive result that the indexed grid is in the second grid database:
determining whether the object belongs to the target geo-fence based on a relationship of the object and a local geo-fence.

12 . The method of claim 11 , wherein the method further comprises establish

Assignees

• Beijing Didi Infinity Technology & Dev Co Ltd

Inventors

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

Classifications

• H04W4/35

  for the management of goods or merchandise · CPC title

• G06F16/29

  Geographical information databases · CPC title

• H04W4/021 Primary

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

• H04W4/80 Primary

  Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication · CPC title

• H04W4/022 Primary

  with dynamic range variability · CPC title