Label positioning technique to reduce crawling during zoom activities

• US 8,237,745 B1
• Filed: 09/26/2011
• Issued: 08/07/2012
• Est. Priority Date: 09/26/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cornell, Brian, Maurer, Jennifer
• Primary Examiner(s): Martello, Edward
• Application Number:
  US13/244,742
• Time in Patent Office: 316 Days
• Field of Search: 345/660
• US Class Current: 345/660
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names

Abstract

A graphics or image rendering system, such as a map image rendering system, receives image data from an image database in the form of vector data that defines various features of the map, such as roads, boundaries, etc., in addition to text strings or symbols to be displayed with the features to provide, for example, labels for the features. The label positioning technique generally divides the displayed road feature into a number of road segments and then labels each road segment in a sequence based on an ordered set of labels and a position of each road segment.

Claims

1. A computer-implemented method for rendering a map on a display device comprising:

determining, using a computer device, a road feature to be displayed on a viewing window at a first zoom level, the road feature having a first and a second endpoint;

determining, using the computer device, an ordered set of labels to be displayed with respect to the road feature;

labeling, using the computer device, the road feature by;

1) determining a segment of the road feature to apply a label, the segment having a length;

2) placing a next label from the ordered set of labels at the center of the determined segment if a length of the next label is less than the length of the determined segment;

3) determining a pair of resultant segments produced by placing the label on the determined segment on which the label is placed with a first one of the pair of resultant segments being on one side of the label along the determined segment and a second one of the pair of resultant segments being on the opposite side of the label with respect to the one side of the label along the determined segment; and

for each resultant segment produced, repeating steps 1, 2, and 3 until a stop condition is reached.

2. The computer-implemented method of claim 1, wherein determining, using the computer device, the segment of the road feature to apply the label includes determining which resultant segment of each pair of resultant segments is to be labeled with a first label of the ordered set subsequent to a label of a parent segment that produced the resultant segment pair and determining which resultant segment of the pair of resultant segments is to be labeled with a second label subsequent to the first label of the ordered set.

3. The computer-implemented method of claim 2, further including determining, using the computer device, that a resultant segment of a pair of resultant segments that is proximate to the first endpoint of the road feature is to be labeled first with the next label when the parent segment is proximate the first endpoint while the other resultant segment of the pair of resultant segments that is distal to the first endpoint is to be labeled with a label subsequent the first label.

4. The computer-implemented method of claim 2, further including determining, using the computer device, that a resultant segment of a pair of resultant segments that is proximate to the second endpoint of the road feature is to be labeled first with the next label when the parent segment is proximate the second endpoint while the other resultant segment of the pair that is distal to the second endpoint is to be labeled with the next label subsequent the first label.

5. The computer-implemented method of claim 1, further including marking, using the computer device, a resultant segment that does not fit a corresponding next label as processed and wherein determining a segment of the road feature to apply a label includes determining whether a segment is marked as processed.

6. The computer-implemented method of claim 1, further including adjusting, using the computer device, the zoom level from the first zoom level to a second different zoom level and repeating steps 1, 2, and 3 for the road feature at the second zoom level.

7. The computer-implemented method of claim 1, wherein placing the next label from the ordered set of labels includes repeating the order of the labels after a last label of the ordered set has been selected as the next label.

8. The computer-implemented method of claim 1, wherein a stop condition is reached when no resultant segment exists whose size is greater than or equal to that of a corresponding sequential label.

9. The computer-implemented method of claim 1, wherein the ordered set of labels are ordered by a priority of each label.

10. The computer-implemented method of claim 1, further including determining, using the computer device, a length of the road feature, being a curved road feature, by calculating the length of the road feature along a center line of the road feature.

11. The computer-implemented method of claim 10, wherein the center line is one of a horizontal line or a vertical line of the viewing window.

12. The computer-implemented method of claim 1, wherein placing the next label from the ordered set of labels at the center of the determined segment includes aligning a center of the next label with the center of the determined segment.

13. The computer-implemented method of claim 12, wherein determining the pair of resultant segments produced by placing the label on the determined segment includes bisecting the determined segment and subtracting half a length of the placed label from each of the segments resulting from the bisection to produce the pair of resultant segments.

14. The computer-implemented method of claim 1, wherein placing the next label includes displaying the next label lengthwise along the road feature.

15. A computing device, comprising:

a communications network interface;

a processor;

a memory coupled to the processor;

a display device coupled to the processor;

a first routine, stored in the memory, that executes on the processor to receive, via the communications network interface, a set of map data comprising data defining at least one road feature of a map and an ordered set of labels associated with the road feature;

a second routine, stored in the memory, that executes on the processor to select a zoom level, a viewing window position, and a viewing window size for rendering the map with the road feature on the display device;

a third routine, stored in the memory, that executes on the processor to determine a segment of the road feature to apply a label, the segment having a length;

a fourth routine, stored in the memory, that executes on the processor to place a next label from the ordered set of labels at the center of the determined segment if a length of the next label is less than the length of the determined segment;

a fifth routine, stored in the memory, that executes on the processor to determine a pair of resultant segments produced by placing the label on the determined segment on which the label is placed with a first one of the pair of resultant segments being on one side of the label along the determined segment and a second one of the pair of resultant segments being on the opposite side of the label with respect to the one side of the label along the determined segment; and

a sixth routine, stored in the memory, that executes on the processor to repeat the third, fourth and fifth routine for each resultant segment produced until a stop condition is reached.

16. The computing device of claim 15, further including a seventh routine, stored in the memory, that executes on the processor to determine that a resultant segment of each pair of resultant segments that is proximate to the first endpoint of the road feature is to be labeled first with the next label when the parent segment is proximate to the first endpoint while the other resultant segment of the pair of resultant segments that is distal the second endpoint is to be labeled with a label subsequent the first label.

17. The computing device of claim 15, further including a seventh routine, stored in the memory, that executes on the processor to determine that a resultant segment of each pair of resultant segments that is proximate to the second endpoint of the road feature is to be labeled first with the next label when the parent segment is proximate to the second endpoint while the other resultant segment of the pair of resultant segments that is distal the second endpoint is to be labeled with a label subsequent the first label.

18. The computing device of claim 15, wherein the sixth routine reaches a stop condition when no resultant segment exists that fits a corresponding sequential label.

19. The computing device of claim 15, further including a seventh routine, stored in the memory, that executes on the processor to determine the length of the road feature by calculating a length of the road feature along a straight center line of the road feature.

20. The computing device of claim 15, further including a seventh routine, stored in the memory, that executes on the processor to adjust the zoom level from the first zoom level to a second different zoom level and to repeat the third, fourth, fifth and sixth routine for the road feature at the second zoom level.

21. A computer-implemented method for rendering a map on a display device comprising:

displaying, using a computer device, a road feature to be displayed on a viewing window at a first zoom level, the road feature having a first and a second endpoint;

displaying, using the computer device, an ordered set of labels on the road feature by;

1) displaying a first label of the ordered set of labels centered at a midpoint of the displayed road feature, thereby creating a first and a second road segment on opposite sides of the first label that do not include the length of the first label;

2) displaying a second label of the ordered set of labels subsequent the first label centered at the midpoint of the first road segment;

3) displaying a third label of the ordered set of labels subsequent the second label centered at the midpoint of the second road segment, wherein displaying the second and the third label create additional pairs of resultant segments;

4) for each resultant segment produced, displaying a next label from the ordered set of labels at the center of the resultant segment if a length of the next label is less than a length of the resultant segment.

22. The computer-implemented method of claim 21, wherein the set of labels are in a sequence of the first label, the second label, and then the third label, and wherein the first label is of a higher priority than the second and the third label.

23. The computer-implemented method of claim 22, further including determining that a resultant segment of a pair of resultant segments that is proximate to the first endpoint of the road feature is to be labeled first with the next label when a parent segment that produced the pair of resultant segments is proximate the first endpoint while the other resultant segment of the pair of resultant segments that is distal to the first endpoint is to be labeled with a label subsequent the label of the proximate resultant segment.

24. The computer-implemented method of claim 22, further including determining that a resultant segment of a pair of resultant segments that is proximate to the second endpoint of the road feature is to be labeled first with the next label when a parent segment that produced the pair of resultant segments is proximate the second endpoint while the other resultant segment of the pair of resultant segments that is distal to the second endpoint is to be labeled with a label subsequent the label of the proximate resultant segment.

25. The computer-implemented method of claim 21, further including adjusting the zoom level from the first zoom level to a second different zoom level and repeating steps 1, 2, 3, and 4 on a different portion of the road feature displayed at the second zoom level.