VIRTUAL GEOGRAPHIC PERIMETERS MADE UP OF MULTIPLE COMPONENT SHAPES

• US 20150230054A1
• Filed: 02/10/2015
• Published: 08/13/2015
• Est. Priority Date: 02/11/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Myllymaki, Jussi, Mantri, Anup, Thota, Chandrasekhar
• Granted Patent: US 9,668,097 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination

Abstract

A computing device includes one or more processors, a user interface, and a non-transitory computer-readable medium storing instructions for determining whether a certain geographic location is within a virtual perimeter of a geographic place. The instructions, when executed on the one or more processors, cause the computing device to determine multiple component shapes that approximately make up a geometry of the geographic place, determine whether the certain geographic location is within at least one of the component shapes, generate an indication that the geographic location is within the virtual perimeter if the geographic location is within at least one of the component shapes, and provide the indication via the user interface.

Claims

1. A computing device comprising:

one or more processors;

a user interface;

a non-transitory computer-readable medium storing thereon instructions for determining whether a certain geographic location is within a virtual perimeter of a geographic place, wherein the instructions, when executed on the one or more processors, cause the computing device to;

determine a plurality of component shapes that approximately make up a geometry of the geographic place,

determine whether the certain geographic location is within at least one of the plurality of component shapes,

generate an indication that the geographic location is within the virtual perimeter if the geographic location is within at least one of the plurality of component shapes, and

provide the indication via the user interface.

2. The computing device of claim 1, further comprising:

a network interface to couple the computing device to a map data server via a communication network;

wherein the instructions further cause the computing device to;

receive an indication of the geometry of the geographic place from the map data server, and

determine the plurality of component shapes based on the geometry of the geographic place.

3. The computing device of claim 2, wherein to determine the plurality of component shapes, the instructions cause the computing device to:

determine a bounding rectangle for the geometry,

determine a plurality of non-overlapping circles that fill the bounding rectangle, and

eliminate, from the plurality of non-overlapping circles, circles that are entirely outside the geometry;

wherein the remaining non-overlapping circles define the plurality of component shapes that approximately make up a geometry of the geographic place.

4. The computing device of claim 2, wherein to determine the plurality of component shapes, the instructions cause the computing device to:

determine a plurality of contiguous cells, each of which is at least partially covered by the geometry, and

for each of the plurality of contiguous cells, determine a respective circle that completely covers the cell;

wherein the circles define the plurality of component shapes that approximately make up a geometry of the geographic place.

5. The computing device of claim 1, further comprising:

a network interface to couple the computing device to a map data server via a communication network, wherein the indication of the plurality of component shapes is received from the map data server.

6. The computing device of claim 1, wherein the instructions cause the computing device to select each of the plurality of component shapes from a set of scaleable basic two-dimensional (2D) shapes including a circle and a rectangle.

7. The computing device of claim 1, wherein the instructions cause the computing device to select each of the plurality of component shapes from a set of scaleable basic three-dimensional (3D) shapes including a sphere and a rectangular cuboid.

9. The method of claim 1, wherein:

the indication of the geometry describes a polygon;

the set includes a circle; and

generating the approximate representation of the geometry includes determining a plurality of instances of the circle that approximately make up the geometry.

10. The method of claim 9, the method further comprising:

determining a bounding rectangle for the geometry;

determining an initial plurality of non-overlapping instances of the circle that fill the bounding rectangle, and

eliminating, from the initial plurality, instances that are entirely outside the geometry to generate the plurality of instances of the circle that make up the geometry.

8. A method for generating virtual perimeters of geographic places, the method comprising:

receiving, by one or more computing devices, an indication of a geometry of a geographic place;

receiving, by the one or more computing devices, a limited set of one or more shapes;

generating, by the one or more computing devices, an approximate representation of the geometry as a plurality of component shapes, each selected from the limited set of shapes; and

using, by the one or more computing devices, the approximate representation of the geometry as a virtual perimeter of the geographic place.

11. The method of claim 8, wherein generating the approximate representation of the geometry includes

determining a plurality of contiguous cells, each of which is at least partially covered by the geometry,

determining a respective circle that completely covers the cell;

wherein the circles define the plurality of component shapes that approximately make up a geometry of the geographic place.

12. The method of claim 8, wherein the limited set of shapes includes one or more of (i) a hexagon, (ii) a triangle, (iii) a rectangle, (iv) a parallelogram, or (v) a circle.

13. The method of claim 8, wherein:

the indication of the geometry describes a 3D outline, and

the limited set of shapes includes one or more 3D solids.

14. The method of claim 8, wherein using the approximate representation of the geometry as the virtual perimeter of the geographic place includes:

determining whether a geographic point is within the virtual perimeter, and

generating an indication of whether the geographic point is within the virtual perimeter.

15. The method of claim 8, wherein the virtual perimeter of the geographic place is an interior virtual perimeter of the geographic place;

the method further comprising;

receiving, by the one or more computing devices, an indication of geometries of a plurality of features adjacent to the geographic place;

generating, by the one or more computing devices, an approximate representation of the geometry of the geographic place along with the geometries of the plurality of features as a second plurality of component shapes, each selected from the limited set of shapes, wherein the second plurality of component shapes corresponds to an exterior virtual perimeter of the geographic place.

16. A portable computing device comprising:

a positioning module configured to determine a current location of the computing device; and

processing hardware coupled to the positioning module and configured to;

receive an indication of a virtual perimeter of a geographic place, including a plurality of component shapes that approximately make up the geometry of the geographic place,

determine whether a geometric point corresponding to the current location of the portable computing device is within one or more of the plurality of component shapes, and

in response to determining that the geometric point is within at least one of the plurality of component shapes, generate an indication that the portable computing device is within the virtual perimeter of the geographic place.

17. The portable computing device of claim 16, wherein the virtual perimeter is an interior perimeter, the processing hardware further configured to:

receive an indication of an exterior perimeter of the geographic place, including a second plurality of component shapes that approximately make up the geometry of the geographic place along with geometries of a plurality of features adjacent to the geographic place,

determine whether the geometric point corresponding to the current location of the portable computing device is within one or more of the second plurality of component shapes, and

in response to determining that the geometric point is within at least one of the second plurality of component shapes, generate an indication that the portable computing device is within the exterior perimeter of the geographic place.

18. The portable device of claim 16, wherein the plurality of component shapes includes a plurality of instances of a circle.

19. The portable device of claim 16, wherein each of the plurality of component shapes is selected from a set including (i) a hexagon, (ii) a triangle, (iii) a rectangle, (iv) a parallelogram, and (v) a circle.

20. The portable device of claim 16, wherein the virtual perimeter is a 3D outline, and wherein each of the plurality of component shapes is a 3D solid.