Density smoothing a display of points-of-interest displayable on a map based on relative prominence

• US 8,830,271 B1
• Filed: 01/07/2011
• Issued: 09/09/2014
• Est. Priority Date: 01/07/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Seefeld, Bernhard, Jordan, Myles
• Primary Examiner(s): Xiao, Ke
• Assistant Examiner(s): Craddock, Robert
• Application Number:
  US12/986,497
• Time in Patent Office: 1,341 Days
• Field of Search: 345/611, 345/660
• US Class Current: 345/660
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G06F 3/14 Digital output to display device ; Cooperation and interconnection of the display device with other functional units
• CPC Class Codes: G09G 2340/045 Zooming at least part of an image, i.e. enlarging it or shrinking it
• CPC Class Codes: G09G 2354/00 Aspects of interface with display user
• CPC Class Codes: G09G 2370/022 Centralised management of display operation, e.g. in a server instead of locally
• CPC Class Codes: G09G 2370/027 Arrangements and methods specific for the display of internet documents

Abstract

A density smoothing server determines the zoom level at which one or more points-of-interest are to be displayed on an electronic map. The density smoothing server may be in communication with a global points-of-interest database, where the global points-of-interest database includes previously ranked points-of-interest. The density smoothing server selects a group of points-of-interest as local points-of-interest and extracts the local points-of-interest, along with corresponding prominence values, from the global points-of-interest database. Using a centroid determination manager and a centroid surface manager, the density smoothing server determines a number of centroids for the surface of the electronic map and then constructs centroid surfaces based on the determined centroids. A zoom level is assigned to each of the extracted local points-of-interest based on a comparison of the prominence values for the local points-of-interest with the constructed centroid surfaces.

Claims

1. An apparatus for density smoothing of points-of-interest displayable on an electronic map, the apparatus comprising:

a computer-readable medium operative to store;

a plurality of predefined zoom levels for viewing a surface;

a plurality of divisions that divide the surface; and

a plurality of executable instructions that define a plurality of managers, the plurality of managers comprising;

a local point-of-interest extraction manager;

a centroid determination manager;

a centroid surface manager; and

a zoom level assignment manager; and

a processor in communication with the computer-readable medium and operative to execute the executable instructions that, when executed, cause;

the local point-of-interest extraction manager to;

extract a plurality of local points-of-interest from a global points-of-interest database for each division of the plurality of divisions; and

extract a plurality of prominence values from the global points-of-interest database, wherein each prominence value of the plurality of prominence values corresponds to a local point-of-interest from the plurality of local points-of-interest;

the centroid determination manager to;

determine a plurality of centroid values from the plurality of prominence values for each division from the plurality of divisions stored in the computer readable medium, wherein;

each centroid value is determined as a function of the plurality of predefined zoom levels stored in the computer readable medium; and

the plurality of centroid values are grouped according to the plurality of predefined zoom levels;

the centroid surface manager to construct a plurality of centroid surfaces from the plurality of centroid values determined by the centroid determination manager; and

the zoom level assignment manager to assign a predefined zoom level from the plurality of predefined zoom levels stored in the computer-readable medium to each local point-of-interest extracted by the local point-of-interest extraction manager based on a comparison of the prominence value corresponding to the local point-of-interest with a centroid surface from the plurality of centroid surfaces determined by the centroid surface manager.

2. The apparatus of claim 1, wherein the computer-readable medium is further operative to store:

a local points-of-interest database operative to store the extracted plurality of local points-of-interest and the extracted plurality of prominence values extracted by the local point-of-interest extraction manager;

a centroid database operative to store the plurality of centroid values determined by the centroid determination manager; and

a zoom level assignment database operative to store the assignments of the plurality of predefined zoom levels to the plurality of local points-of-interest determined by the zoom level assignment manager.

3. The apparatus of claim 1, wherein execution of the executable instructions further causes the local point-of-interest extraction manager to extract the plurality of local points-of-interest from the global points-of-interest database based on a provided characteristic for the plurality of local points-of-interest.

4. The apparatus of claim 1, wherein execution of the executable instructions further causes the centroid determination manager to determine the plurality of centroid values from each plurality of prominence values for each division from the plurality of divisions based on the density of the local points-of-interest occurring within each division.

5. The apparatus of claim 1, wherein each centroid value of the plurality of centroid values corresponds to a predefined zoom level of the plurality of predefined zoom levels.

6. The apparatus of claim 1, wherein execution of the executable instructions further causes the zoom level assignment manager to determine the displayability of a selected local point-of-interest from the plurality of local points-of-interest based on a predefined zoom level assigned to the selected local point-of-interest.

7. The apparatus of claim 1, wherein:

a first local point-of-interest of the plurality of local points-of-interest corresponds to a first prominence value;

a second local point-of-interest of the plurality of local points-of-interest corresponds to a second prominence value having an approximate value as the first prominence value; and

execution of the executable instructions further causes the zoom level assignment manager to;

assign the first local point-of-interest a first predefined zoom level from the plurality of predefined zoom levels; and

assign the second local point-of-interest a second predefined zoom level different than the first predefined zoom level from the plurality of predefined zoom levels.

8. The apparatus of claim 1, wherein:

the predefined zoom levels comprise;

a low zoom level corresponding to a first height furthest from the surface;

a high zoom level corresponding to a second height closest to the surface; and

a middle zoom level corresponding to a third height that is less than the first height but greater than the second height; and

execution of the executable instructions further causes the centroid surface manager to construct;

a low level centroid surface corresponding to the low zoom level;

a middle level centroid surface corresponding to the middle zoom level; and

a high level centroid surface corresponding to the high zoom level.

9. The apparatus of claim 1, wherein each centroid value for a given one of the plurality of divisions is determined according to an exponential increase in the number of local points-of-interest displayable at a predefined zoom level for the given division.

10. The apparatus of claim 1, wherein the predefined zoom level is assigned to the local point-of-interest when the prominence value corresponding to the local point-of-interest exceeds the centroid surface value corresponding to the predefined zoom level.

11. A method for density smoothing of points-of-interest displayable on an electronic map, the method comprising:

storing in a computer-readable medium a plurality of predefined zoom levels for viewing a surface and a plurality of divisions that divide the surface;

extracting with a processor a plurality of local points-of-interest from a global points-of-interest database for each division of the plurality of divisions;

extracting a plurality of prominence values from the global points-of-interest database, wherein each prominence value corresponds to a local point-of-interest from the plurality of local points-of-interest;

determining a plurality of centroid values from the plurality of prominence values for each division from the plurality of divisions, wherein;

each centroid value is determined as a function of the plurality of predefined zoom levels; and

the plurality of centroid values are grouped according to the plurality of predefined zoom levels;

constructing a plurality of centroid surfaces from the plurality of centroid values; and

assigning a predefined zoom level from the plurality of predefined zoom levels to each local point-of-interest based on a comparison of the prominence value corresponding to the local point-of-interest with a centroid surface from the plurality of surface.

12. The method of claim 11, further comprising establishing, in the computer-readable medium:

a local points-of-interest database operative to store the extracted plurality of local points-of-interest and the extracted plurality of prominence values;

a centroid database operative to store the plurality of centroid values; and

a zoom level assignment database operative to store the assignments of the plurality of predefined zoom levels to the plurality of local points-of-interest.

13. The method of claim 11, further comprising extracting the plurality of local points-of-interest from the global points-of-interest database based on a provided characteristic for the plurality of local points-of-interest.

14. The method of claim 11, further comprising determining the plurality of centroid values from the plurality of prominence values for each division from the plurality of divisions based on the density of the local points-of-interest occurring within each division.

15. The method of claim 11, wherein each centroid value of the plurality of centroid values corresponds to a predefined zoom level of the plurality of predefined zoom levels.

16. The method of claim 11, further comprising determining the display ability of a selected local point-of-interest from the plurality of local points-of-interest based on a predefined zoom level assigned to the selected local point-of-interest.

17. The method of claim 11, wherein:

a first local point-of-interest of the plurality of local points-of-interest corresponds to a first prominence value;

a second local point-of-interest of the plurality of local points-of-interest corresponds to a second prominence value having an approximate value as the first prominence value; and

the method further comprises;

assigning the first local point-of-interest a first predefined zoom level from the plurality of predefined zoom levels; and

assigning the second local point-of-interest a second predefined zoom level different than the first predefined zoom level from the plurality of predefined zoom levels.

18. The method of claim 11, wherein:

the predefined zoom levels comprise;

a low zoom level corresponding to a first height furthest from the surface;

a high zoom level corresponding to a second height closest to the surface; and

a middle zoom level corresponding to a third height that is less than the first height but greater than the second height; and

the method further comprises;

constructing a first centroid surface corresponding to the low zoom level;

constructing a second of centroid surface corresponding to the middle zoom level; and

constructing a third centroid surface corresponding to the high zoom level.

19. The method of claim 11, wherein each centroid value for a given one of the divisions is determined according to an exponential increase in the number of local points-of-interest displayable at a predefined zoom level for the given division.

20. The method of claim 11, wherein the predefined zoom level is assigned to the local point-of-interest when the prominence value corresponding to the local point-of-interest exceeds the centroid surface corresponding to the predefined zoom level.