Resolving label collisions on a digital map

• US 9,448,754 B2
• Filed: 05/15/2013
• Issued: 09/20/2016
• Est. Priority Date: 05/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baxter, William V., Davidson, Michael P.
• Primary Examiner(s): Amini, Javid A
• Application Number:
  US13/895,135
• Publication Number:
  US 20150187337A1
• Time in Patent Office: 1,224 Days
• Field of Search: 345/660
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06F 2203/04805 Virtual magnifying lens, i.e. window or frame movable on top of displayed information to enlarge it for better reading or selection
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• 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: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G09B 29/005 Map projections or methods associated specifically therewith
• CPC Class Codes: G09G 2340/045 Zooming at least part of an image, i.e. enlarging it or shrinking it
• CPC Class Codes: G09G 2340/14 Solving problems related to the presentation of information to be displayed

Abstract

A technique for displaying labels on a digital map comprise displaying the digital map via a user interface at a first zoom level, including displaying non-overlapping labels. The method also comprises receiving, via the user interface, a request to zoom out from the digital map to a second zoom level, where the second zoom level corresponds to smaller magnification than the first zoom level, and where the plurality of labels have the same size at the first zoom level and the second zoom level. Still further, the method includes resolving collisions among the plurality of labels at the second zoom level in response to receiving the request and prior to zooming out from the first zoom level, and zooming out from the digital map at the first zoom level to the second zoom level via at least one intermediate zoom level.

Claims

1. A method in a computing device for displaying labels on a digital map, the method comprising:

displaying the digital map via a user interface at a first zoom level, including displaying a plurality of labels at respective locations without overlaps;

receiving, via the user interface, a request to zoom out from the first zoom level to a second zoom level, wherein the second zoom level corresponds to smaller magnification than the first zoom level, and wherein the plurality of labels are displayed at the same size at the first zoom level and the second zoom level;

in response to receiving the request and prior to zooming out from the first zoom level;

determining that at least some of the plurality of labels overlap at the second zoom level when displayed at their respective locations, and

resolving collisions among the plurality of labels at the second zoom level to generate a modified set of labels that do not overlap; and

zooming out from the digital map at the first zoom level to the second zoom level via at least one intermediate zoom level between the first zoom level and the second zoom level, including displaying the digital map at the least one intermediate zoom level with the modified set of labels.

2. The method of claim 1, wherein resolving the collisions among the plurality of labels includes:

for each collision between two or more labels, comparing priority of the colliding labels, and

removing labels having lower priority.

3. The method of claim 1, wherein displaying the digital map includes render content defined in a vector graphics format.

4. The method of claim 1, wherein the plurality of labels is defined in a raster format.

5. The method of claim 4, wherein the plurality of labels identify at least some of (i) neighborhoods, (ii) cities, and (iii) counties.

6. The method of claim 1, wherein the first zoom level and the second zoom levels are discrete zoom levels.

17. The method of claim 1, wherein resolving collisions among the plurality of labels at the second zoom level includes removing one or more of the plurality of labels.

18. The method of claim 1, wherein resolving collisions among the plurality of labels at the second zoom level includes changing transparency of one or more of the plurality of labels.

19. The method of claim 1, wherein resolving collisions among the plurality of labels at the second zoom level includes removing portions of one or more of the plurality of labels.

20. The method of claim 2, wherein resolving the collisions among the plurality of labels further includes:

for a pair of colliding labels that identify respective neighborhoods, determine which of the pair of neighborhoods has a lower population density, and remove the label corresponding to the neighborhood with the lower population density.

7. A non-transitory computer-readable medium storing thereon instructions executable on one or more processors, wherein the instructions, when executed one or more processors, cause the one or more processors to:

display a digital map via the user interface at a first zoom level, wherein the digital map includes (i) a plurality of elements scalable between the first zoom level and a second zoom level and (ii) a plurality of labels that do not scale between the first zoom level and the second zoom level, including displaying the plurality labels at respective locations without overlaps;

receive, via the user interface, a request to display the digital map at the second zoom level;

prior to zooming out from the first zoom level, (i) determine that at least some of the plurality of labels overlap at the second zoom level when displayed at t respective locations, and (ii) remove one or more labels from the plurality of labels, so that the remaining ones of the plurality of labels do not overlap at the second zoom level to generate a reduced set of labels; and

after the one or more labels have been removed, begin to change the zoom level of the digital map from the first zoom level to the second zoom level, including display the digital map at an intermediate zoom level between the first zoom level and the second zoom level with the reduced set of labels.

8. The computer-readable medium of claim 7, wherein the instructions cause the one or more processors to progress from the first zoom level to the second zoom level via a plurality of intermediate levels.

9. The computer-readable medium of claim 7, wherein to remove the one or more labels, the instructions compare priority of the overlapping labels.

10. The computer-readable medium of claim 7, wherein the plurality of elements scalable between the first zoom level and a second zoom level are defined in a vector graphics format.

11. A computing device comprising:

a user interface;

one or more processors; and

a computer-readable memory storing thereon instructions that, when executed on the one or more processors, cause the computing device to;

display a digital map via the user interface at a first zoom level, including display a plurality of labels at respective locations,

receive, via the user interface, a request to zoom out from the digital map to a second zoom level, wherein the second zoom level corresponds to smaller magnification than the first zoom level, and wherein the plurality of labels have the same size at the first zoom level and the second zoom level,

in response to receiving the request and prior to zooming out from the first zoom level, (i) determine that at least some of the plurality of labels overlap at the second zoom level when displayed at t respective locations, and (ii) resolve collisions among the plurality of labels at the second zoom level to generate a modified set of labels that do not overlap, and

zoom out from the digital map at the first zoom level to the second zoom level via at least one intermediate zoom level, including display the digital map at the least one intermediate zoom level with the modified set of labels.

12. The computing device of claim 11, wherein to resolve the collisions among the plurality of labels, the instructions cause the one or more processors to:

for each collision between two or more labels, compare priority of the colliding labels, and

remove labels having lower priority.

13. The computing device of claim 11, wherein to display the digital map, the instructions cause the one or more processors to render content defined in a vector graphics format.

14. The computing device of claim 11, wherein the plurality of labels is defined in a raster format.

15. The computing device of claim 14, wherein the plurality of labels identify at least some of (i) neighborhoods, (ii) cities, and (iii) counties.

16. The computing device of claim 11, wherein the first zoom level and the second zoom levels are discrete zoom levels.