Location-based information determination
First Claim
1. A method for a computing system to determine location-related information for points of interest, the method comprising:
- obtaining map information for a geographic area of interest;
determining polygon-based information for the geographic area that represents actual travel distances in the geographic area by,decomposing the geographic area into a plurality of smaller areas based at least in part on the obtained map information, the smaller areas represented with a first polygon layer that includes a plurality of non-overlapping adjacent polygons of substantially similar size, and determining an associated approximate actual travel distance in the geographic area that the polygons of the first polygon layer each represent based on an average diameter of the polygons of the first polygon layer; and
automatically generating a hierarchy of polygon layers that includes the first polygon layer as a lowest level of the hierarchy and that includes one or more additional polygon layers for the geographic area that are successively higher in the hierarchy, each of the additional polygon layers including successively larger polygons that each include multiple polygons from a next lower polygon layer in the hierarchy, and associating an approximate actual travel distance with each of the polygons of the additional polygon layers based on the approximate actual travel distances of at least some of the multiple polygons from the next lower polygon layer that are included in the polygon; and
for each of multiple search requests for points of interest in the geographic area that are within an indicated distance from an indicated origination point,automatically using the hierarchy of polygon layers to identify a search area for the search request that approximates a subset of the geographic area within the indicated distance of the indicated origination point, the identified search area being one or more polygons from at least one of the polygon layers of the hierarchy that are selected based at least in part on the approximate actual travel distances associated with the selected one or more polygons; and
providing search results for the search request by identifying points of interest that are present in the one or more selected polygons.
5 Assignments
0 Petitions
Accused Products
Abstract
Techniques are described for determining and providing location-based information, including based on decomposing a geographic area into numerous smaller areas and using one or more layers of polygons to represent various of the smaller areas. In some situations, location-based information for a geographic area is determined efficiently and accurately to reflect actual travel distances and/or times, such as for use in identifying one or more points of interest that are sufficiently proximate to an indicated location (e.g., a current location of a user), and/or to determine actual travel distances and/or times between two or more indicated locations of interest. The location-based information determination may in some situations be performed in a realtime or near-realtime manner after a request is received from a user, such as to interactively provide results to the user that include or are based at least in part on the determined location-based information.
-
Citations
36 Claims
-
1. A method for a computing system to determine location-related information for points of interest, the method comprising:
-
obtaining map information for a geographic area of interest; determining polygon-based information for the geographic area that represents actual travel distances in the geographic area by, decomposing the geographic area into a plurality of smaller areas based at least in part on the obtained map information, the smaller areas represented with a first polygon layer that includes a plurality of non-overlapping adjacent polygons of substantially similar size, and determining an associated approximate actual travel distance in the geographic area that the polygons of the first polygon layer each represent based on an average diameter of the polygons of the first polygon layer; and automatically generating a hierarchy of polygon layers that includes the first polygon layer as a lowest level of the hierarchy and that includes one or more additional polygon layers for the geographic area that are successively higher in the hierarchy, each of the additional polygon layers including successively larger polygons that each include multiple polygons from a next lower polygon layer in the hierarchy, and associating an approximate actual travel distance with each of the polygons of the additional polygon layers based on the approximate actual travel distances of at least some of the multiple polygons from the next lower polygon layer that are included in the polygon; and for each of multiple search requests for points of interest in the geographic area that are within an indicated distance from an indicated origination point, automatically using the hierarchy of polygon layers to identify a search area for the search request that approximates a subset of the geographic area within the indicated distance of the indicated origination point, the identified search area being one or more polygons from at least one of the polygon layers of the hierarchy that are selected based at least in part on the approximate actual travel distances associated with the selected one or more polygons; and providing search results for the search request by identifying points of interest that are present in the one or more selected polygons. - View Dependent Claims (2, 3, 4)
-
-
5. A computer-implemented method for determining location-related information for points of interest, the method comprising:
-
determining information about subareas of a geographic area, the subareas represented using a hierarchy of polygon layers, the hierarchy including a lowest first polygon layer with a plurality of non-overlapping adjacent polygons, the hierarchy further including one or more successively higher additional polygon layers that each have a plurality of polygons larger than the polygons of a next lower polygon layer of the hierarchy, the polygons of the additional polygon layers each including multiple polygons from the next lower polygon layer; associating an approximate average distance in the geographic area with each of the polygons of the first polygon layer based on an average size of the polygon, and associating an approximate average distance in the geographic area with each of the polygons of the additional polygon layers based on the approximate average distances of at least some of the multiple polygons from the next lower polygon layer that are included in the polygon; automatically determining information about distance in the geographic area based on the hierarchy of polygon layers, by; determining one or more polygons of one or more polygon layers of the hierarchy that include at least one of first and second points of interest; and determining an approximate actual distance between the first and second points based at least in part on the average distances associated with the determined polygons; and providing an indication of the determined approximate actual distance to reflect actual travel between the first and second points. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A non-transitory computer-readable medium whose contents enable a computing device to determine location-related information of interest, by performing a method comprising:
-
obtaining information about a geographic area, the obtained information including at least a first polygon layer with a plurality of polygons such that each of the polygons represents a subarea of the geographic area, each of the polygons of the first polygon layer having an associated value for a measurement of travel through the subarea that corresponds to the polygon; automatically determining approximate travel information for the geographic area based on the plurality of polygons, by; determining one or more of the polygons that include at least one of multiple locations of interest; and determining an approximate value of a measurement of travel between at least two of the multiple locations based at least in part on the associated travel measurement values for at least one of the determined polygons; and providing an indication of the determined approximate travel measurement value to reflect approximate actual travel between the at least two locations. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
34. A computing system configured to determine location-related information of interest, comprising:
-
one or more memories; and a location-based information provider system that is configured to determine location-related information of interest, by; obtaining information about a plurality of polygons that each represent a distinct subarea of a geographic area, the plurality of polygons being part of a hierarchy of polygon layers that includes a lowest first polygon layer with multiple of the plurality of polygons and that further includes one or more successively higher additional polygon layers that each have multiple of the plurality of polygons that are larger than the polygons of a next lower polygon layer of the hierarchy, the polygons of the additional polygon layers each including one or more polygons from the next lower polygon layer, each of the polygons of the first polygon layer having an associated average distance to reflect actual travel of one or more travel types through the subarea that the polygon represents, and each of the polygons of the additional polygon layers having an associated average distance based at least in part on the average distances of at least some of the one or more polygons from the next lower polygon layer that are included in the polygon; determining one or more polygons of one or more polygon layers of the hierarchy that include at least one of multiple locations of interest; determining an actual distance between at least two of the multiple locations based at least in part on the average distances associated with the determined polygons; and providing an indication of the determined actual distance to reflect actual travel between the at least two locations. - View Dependent Claims (35, 36)
-
Specification