Virtual geographic perimeters made up of multiple component shapes

Patent metadata

Field	Value
Publication number	US-9668097-B2
Application number	US-201514618653-A
Country	US
Kind code	B2
Filing date	Feb 10, 2015
Priority date	Feb 11, 2014
Publication date	May 30, 2017
Grant date	May 30, 2017

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.

First claim

What is claimed:

1. A mobile computing device comprising:
one or more processors;
a user interface;
a network interface to couple the mobile computing device to a map data server via a wireless communication network;
a non-transitory computer-readable medium storing thereon instructions for determining whether a certain geographic location, corresponding to a current location of the mobile computing device, is within a virtual perimeter of a geographic place, wherein the instructions, when executed on the one or more processors, cause the mobile computing device to:
receive, from the map data server, a single complex shape that describes a geometry of the geographic place,
determine a plurality of component shapes that approximately make up the geometry of the geographic place, wherein each of the plurality of component shapes is selected from a limited set of scaleable basic shapes, including:
determine a bounding shape for the geometry,
determine a plurality of non-overlapping basic shapes that fill the bounding shape, and
eliminate, from the plurality of non-overlapping basic shapes, the basic shapes that are entirely outside the geometry; wherein the remaining non-overlapping shapes define the 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 mobile computing device of claim 1 , wherein
the bounding shape for the geometry is a bounding rectangle, and wherein the plurality of non-overlapping basic shapes is a plurality of non-overlapping circles that fill the bounding rectangle.

3. The mobile computing device of claim 1 , wherein to determine the plurality of component shapes, the instructions cause the mobile 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.

4. The mobile computing device of claim 1 , wherein the limited set of scaleable basic shapes is a set of two-dimensional (2D) shapes including a circle and a rectangle.

5. The mobile computing device of claim 1 , wherein the limited set of scaleable basic shapes is a set of three-dimensional (3D) shapes including a sphere and a rectangular cuboid.

6. The mobile computing device of claim 1 , wherein the instructions further cause the mobile computing device to display a digital map on the user interface, wherein the digital map includes the single complex shape that describes the geometry of the geographic place.

7. The mobile computing device of claim 1 , wherein the instructions further cause the mobile computing device to display at least one of an advertisement, an offer, or a coupon if the geographic location is within at least one of the plurality of component shapes.

8. A method for generating virtual perimeters of geographic places on mobile computing devices, the method comprising:
receiving, at a mobile computing device from a map data server via a wireless communication network a single complex shape that describes a geometry of a geographic place;
obtaining, at the mobile computing device, a limited set of one or more scaleable basic shapes;
generating, at the mobile computing device, an approximate representation of the geometry as a plurality of component shapes, each selected from the limited set of scaleable basic shapes, including:
determining a bounding shape for the geometry,
determining a plurality of non-overlapping basic shapes that fill the bounding shape, and
eliminating, from the plurality of non-overlapping basic shapes, the basic shapes that are entirely outside the geometry; wherein the remaining non-overlapping shapes define the plurality of component shapes that approximately make up a geometry of the geographic place;

using, at the mobile computing device, the approximate representation of the geometry as a virtual perimeter of the geographic place; including:
determining whether a geographic point, corresponding to a current location of the mobile computing device, is within the virtual perimeter, and
generating an indication of whether the geographic point is within the virtual perimeter.

9. The method of claim 8
wherein the bounding shape for the geometry is a bounding rectangle, and wherein the plurality of non-overlapping basic shapes is plurality of non-overlapping instances of the circle that fill the bounding rectangle.

10. 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.

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

12. The method of claim 8 , wherein:
the single complex shape that describes the geometry describes a 3D outline, and
the limited set of shapes includes one or more 3D solids.

13. 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, a description 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.

14. 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, via a network interface which couples the mobile computing device to a map data server via a wireless communication network, a description of a virtual perimeter of a geographic place, including a plurality of component shapes that approximately make up the geometry of the geographic place, wherein the component shapes are selected from a limited set of one or more scalabeable basic shapes by (i) determining a bounding shape for the geometry, (ii) determine a plurality of non-overlapping basic shapes that fill the bounding shape, and (iii) eliminating, from the plurality of non-overlapping basic shapes, the basic shapes that are entirely outside the geometry, wherein the remaining non-overlapping shapes define the plurality of component shapes that approximately make up a 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 on

Assignees

• Google Inc

Inventors

• Myllymaki Jussi
• Mantri Anup
• Thota Chandrasekhar

Classifications

• H04W64/006

  with additional information processing, e.g. for direction or speed determination · CPC title

• H04W4/021 Primary

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