Method and apparatus for determining index grids of geo-fence

1. A method for determining index grids of a geo-fence, comprising:

determining a circumscribed grid of the geo-fence, the circumscribed grid being a smallest single grid in a pre-defined granularity system that can contain the geo-fence;

with the circumscribed grid as a starting point, subdividing one or more grids containing a boundary of the geo-fence into finer-grained grids level by level until an index accuracy of a subdivided grid set is not lower than a predetermined precision threshold, the grid set being composed of grids within the geo-fence and grids containing the boundary of the geo-fence, the index accuracy being a ratio of an area of the geo-fence to a sum of areas of all the grids in the grid set; and

taking the grids in the grid set as index grids of the geo-fence,

wherein the method further comprises:

if the index accuracy of the grid set is higher than the predetermined precision threshold, merging part of the grids in the grid set into one or more coarser-grained grids containing the boundary of the geo-fence so that the index accuracy after merging is not lower than the predetermined precision threshold, wherein the merging includes taking an optimal solution to a knapsack problem as a result of the merging by:

constructing a tree hierarchy of items of the knapsack problem, a parent item in the tree hierarchy being merged from its child items;

enumerating all knapsack states of the knapsack problem under a constraint condition that items with a parent-child relationship cannot exist in one knapsack at the same time; and

solving an answer to each knapsack state, and taking an optimal one in all the answers as the optimal solution to the knapsack problem; and

updating the grid set according to the result of the merging and taking grids in the updated grid set as index grids of the geo-fence.

2. The method according to claim 1 , further comprising:

generating the knapsack problem in which a merged grid containing the boundary of the geo-fence is considered as an item, an increase in an area outside the geo-fence when the item is used as an index grid in comparison with the area outside the geo-fence before merging is considered as a weight of the item, a reduction in a number of grids when the item is used as the index grid in comparison with a number of grids before merging is considered as a price of the item, and an area outside the geo-fence corresponding to an exceedance of the index accuracy of the grid set relative to the predetermined precision threshold before merging is considered as a limited total weight.

3. The method according to claim 1 , wherein the constructing a tree hierarchy of items of the knapsack problem comprises:

with a lower-limit granularity as a starting point of a current granularity, merging grids of the current granularity in the grid set into one or more coarser-grained grids level by level;

with each merged grid as an item, determining a weight and a price of the item until all grids are merged into the circumscribed grid; and

generating the tree hierarchy of items according to the parent-child relationship between the items, wherein the lower-limit granularity is a granularity of densest grids in the grid set before merging.

4. The method according to claim 1 , wherein the enumerating all knapsack states of the knapsack problem under a constraint condition that items with the parent-child relationship cannot exist in one knapsack at the same time comprises:

determining the knapsack state of each item functioning as a leaf node of the tree hierarchy; and

with child items functioning as leaf nodes as a starting point and an intersection of a Cartesian product of knapsack states of all the child items of the parent item and the parent item itself as the knapsack state of the parent item, performing iteration until the knapsack states of the circumscribed grid corresponding to a root node in the tree hierarchy are obtained, wherein the knapsack states of the circumscribed grid are all the knapsack states of the knapsack problem.

5. A device for determining index grids of a geo-fence, comprising:

a processor; and

a memory for storing instructions executable by the processor;

wherein the processor is configured to:

determine a circumscribed grid of the geo-fence, the circumscribed grid being a smallest single grid in a pre-defined granularity system that can contain the geo-fence;

with the circumscribed grid as a starting point, subdivide one or more grids containing a boundary of the geo-fence into finer-grained grids level by level until an index accuracy of a subdivided grid set is not lower than a predetermined precision threshold, the grid set being composed of grids within the geo-fence and grids containing the boundary of the geo-fence, the index accuracy being a ratio of an area of the geo-fence to a sum of areas of all the grids in the grid set; and

take the grids in the grid set as index grids of the geo-fence,

wherein the processor is further configured to:

if the index accuracy of the grid set is higher than the predetermined precision threshold, merge part of the grids in the grid set into one or more coarser-grained grids containing the boundary of the geo-fence so that the index accuracy after merging is not lower than the predetermined precision threshold, wherein merging part of the grids includes taking an optimal solution to a knapsack problem as a result of the merging by:

constructing a tree hierarchy of items of the knapsack problem, a parent item in the tree hierarchy being merged from its child items;

enumerating all knapsack states of the knapsack problem under a constraint condition that items with a parent-child relationship cannot exist in one knapsack at the same time; and

solving an answer to each knapsack state, and taking an optimal one in all the answers as the optimal solution to the knapsack problem; and

update the grid set according to the result of the merging and take grids in the updated grid set as index grids of the geo-fence.

6. The device according to claim 5 , wherein the processor is further configured to:

generate the knapsack problem in which a merged grid containing the boundary of the geo-fence is considered as an item, an increase in an area outside the geo-fence when the item is used as an index grid in comparison with the area outside the geo-fence before merging is considered as a weight of the item, a reduction in a number of grids when the item is used as the index grid in comparison with a number of grids before merging is considered as a price of the item, and an area outside the geo-fence corresponding to an exceedance of the index accuracy of the grid set relative to the predetermined precision threshold is before merging considered as a limited total weight.

7. The device according to claim 5 , wherein the processor is further configured to:

with a lower-limit granularity as a starting point of a current granularity, merge grids of the current granularity in the grid set into one or more coarser-grained grids level by level;

with each merged grid as an item, determine a weight and a price of the item until all grids are merged into the circumscribed grid; and

generate the tree hierarchy of items according to the parent-child relationship between the items, wherein the lower-limit granularity is a granularity of the densest grids in the grid set before merging.

8. The device according to claim 5 , wherein the processor is further configured to:

determine the knapsack state of each item functioning as a leaf node of the tree hierarchy; and

with child items functioning as leaf nodes as a starting point and an intersection of a Cartesian product of knapsack states of all the child items of the parent item and the parent item itself as the knapsack state of the parent item, perform iteration until the knapsack states of the circumscribed grid corresponding to a root node in the tree hierarchy are obtained, wherein the knapsack states of the circumscribed grid are all the knapsack states of the knapsack problem.

9. A computer-readable storage medium, having stored thereon a computer program, wherein when the computer program is executed by a processor of a device, the computer program causes the device to perform a method for determining index grids of a geo-fence, the method comprising:

determining a circumscribed grid of the geo-fence, the circumscribed grid being a smallest single grid in a pre-defined granularity system that can contain the geo-fence;

with the circumscribed grid as a starting point, subdividing one or more grids containing a boundary of the geo-fence into finer-grained grids level by level until an index accuracy of a subdivided grid set is not lower than a predetermined precision threshold, the grid set being composed of grids within the geo-fence and grids containing the boundary of the geo-fence, the index accuracy being a ratio of an area of the geo-fence to a sum of areas of all the grids in the grid set; and

taking the grids in the grid set as index grids of the geo-fence,

wherein the method further comprises:

if the index accuracy of the grid set is higher than the predetermined precision threshold, merging part of the grids in the grid set into one or more coarser-grained grids containing the boundary of the geo-fence so that the index accuracy after merging is not lower than the predetermined precision threshold, wherein the merging includes taking an optimal solution to a knapsack problem as a result of the merging by:

constructing a tree hierarchy of items of the knapsack problem, a parent item in the tree hierarchy being merged from its child items;

enumerating all knapsack states of the knapsack problem under a constraint condition that items with a parent-child relationship cannot exist in one knapsack at the same time; and

solving an answer to each knapsack state, and taking an optimal one in all the answers as the optimal solution to the knapsack problem; and

updating the grid set according to the result of the merging and taking grids in the updated grid set as index grids of the geo-fence.

10. The computer-readable storage medium according to claim 9 , wherein the method further comprises:

generating the knapsack problem in which a merged grid containing the boundary of the geo-fence is considered as an item, an increase in an area outside the geo-fence when the item is used as an index grid in comparison with the area outside the geo-fence before merging is considered as a weight of the item, a reduction in a number of grids when the item is used as the index grid in comparison with a number of grids before merging is considered as a price of the item, and an area outside the geo-fence corresponding to an exceedance of the index accuracy of the grid set relative to the predetermined precision threshold before merging is considered as a limited total weight.

11. The computer-readable storage medium according to claim 9 , wherein the constructing a tree hierarchy of items of the knapsack problem comprises:

with a lower-limit granularity as a starting point of a current granularity, merging grids of the current granularity in the grid set into one or more coarser-grained grids level by level;

with each merged grid as an item, determining a weight and a price of the item until all grids are merged into the circumscribed grid; and

generating the tree hierarchy of items according to the parent-child relationship between the items, wherein the lower-limit granularity is a granularity of densest grids in the grid set before merging.

12. The computer-readable storage medium according to claim 9 , wherein the enumerating all knapsack states of the knapsack problem under a constraint condition that items with the parent-child relationship cannot exist in one knapsack at the same time comprises:

determining the knapsack state of each item functioning as a leaf node of the tree hierarchy; and

with child items functioning as leaf nodes as a starting point and an intersection of a Cartesian product of knapsack states of all the child items of the parent item and the parent item itself as the knapsack state of the parent item, performing iteration until the knapsack states of the circumscribed grid corresponding to a root node in the tree hierarchy are obtained, wherein the knapsack states of the circumscribed grid are all the knapsack states of the knapsack problem.