Generating bounding boxes for labels

Patent metadata

Field	Value
Publication number	US-9443494-B1
Application number	US-201314135306-A
Country	US
Kind code	B1
Filing date	Dec 19, 2013
Priority date	Dec 19, 2013
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

A computing device can receive, from a map search system and in response to a map search query, map data that describes a geographic region. Each map label includes one or more text characters. A respective bounding box for each map label that is defined by an aspect ratio having a width and a height can be generated. The width of the bounding box is twice that of the height of the bounding box and an area for the bounding box is the same as an area for the map label. Map labels can be selected for display in an interactive geographic map. The interactive geographic map that displays the selected map labels that each describes a feature that is located in the geographic region can be generated. Each selected map label is enclosed by a respective bounding box for the map label.

First claim

What is claimed is:

1. A computer-implemented method for generating a bounding box for a map label, the method comprising:
receiving, from a map search system and in response to a map search query, map data that describes a geographic region, the map data including a collection of map labels that each describe a respective feature that is located in the geographic region, each map label comprising one or more text characters, and wherein each map label is associated with a respective popularity score;
generating, for each map label in the collection of map labels, a respective bounding box having a width and a height, and wherein an area for the bounding box is the same as an area for the map label, wherein each bounding box is associated with a respective initial buffer space that includes the respective bounding box and some additional area beyond the respective bounding box, the initial buffer space defining an area within which other maps labels cannot be placed;
determining that a first map label and a second map label, from the collection of map labels, were displayed in a previously presented frame for a map representing the geographic region;
receiving a request to display a new frame for the map;
determining, for the first map label, a first reduced buffer space, the first reduced buffer space being determined by reducing an initial buffer space of a first bounding box for the first map label by a first predetermined amount, the initial buffer space of the first bounding box including both the first bounding box and a first additional area beyond the first bounding box, the first reduced buffer space including both the first bounding box and a second additional area beyond the first bounding box, the second additional area being less than the first additional area;
determining, for the second map label, a second reduced buffer space, the second reduced buffer space being determined by reducing an initial buffer space of a second bounding box for the second label by a second predetermined amount, the initial buffer space of the second bounding box including both the second bounding box and a third additional area beyond the second bounding box, the second reduced buffer space including both the second bounding box and a fourth additional area beyond the second bounding box, the fourth additional area being less than the third additional area; and
generating, using the map data and the first and the second map labels, the new frame for the map, the new frame including the first and the second map labels, wherein the first map label is disposed within an area defined by the first bounding box, wherein the first bounding box lies within the first reduced buffer space, and
wherein the second map label is disposed within an area defined by the second bounding box, wherein the second bounding box lies within the second reduced buffer space.

2. The computer-implemented method of claim 1 , further comprising:
determining, for each map label in the collection of map labels, a respective width based on a sum of respective widths of each text character in the one or more text characters for the map label, the width including respective widths of whitespace in the map label;
determining, for each map label in the collection of map labels, a respective height based on a height of a tallest text character in the one or more text characters for the map label; and
determining, for each map label in the collection of map labels, a respective area based on a product of the respective width and the respective height.

3. The computer-implemented method of claim 2 , further comprising:
determining, for each map label in the collection of map labels, a respective line wrapping for fitting the one or more characters of the map label within the area of the respective bounding box for the map label.

4. The computer-implemented method of claim 1 , wherein the width of the first bounding box is two times the height of the first bounding box.

5. The computer-implemented method of claim 2 , wherein determining, for the first map label, the first reduced buffer space, the first reduced buffer space being determined by reducing the initial buffer space of the first bounding box for the first map label by the first predetermined amount further comprises:
identifying a feature in the new frame for the map that is being described by the first map label;
determining that the first bounding box does not fit within a boundary of the identified feature in the new frame for the map; and
generating, for the first label, a resized bounding box that fits within the boundary of the identified feature.

6. A computing device comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the computing device to perform operations, comprising:
determining, for a first label, an area for the first label;
determining, for the first label, a first bounding box that satisfies an aspect ratio and that has an area that is the same as the area for the first label, the first bounding box being associated with a first initial buffer space that includes both the first bounding box and a first additional area beyond the first bounding box, the first initial buffer space describing a region surrounding the first bounding box within which other labels cannot be placed;
selecting the first label and a second label to be included in a map representing a geographic region, and the second label having a second bounding box, the second bounding box being associated with a second initial buffer space that includes both the second bounding box and a second additional area beyond the second bounding box, the second initial buffer space describing a region surrounding the second bounding box within which other labels cannot be placed;
determining that there is an overlap between the first initial buffer space and the second initial buffer space;
generating, for the second label, a reduced buffer space using the second initial buffer space of the second label, the reduced buffer space including both the second bounding box and a third additional area beyond the second bounding box, the third additional area being less than the second additional area; and
placing the first and the second labels in the map, wherein the first label is placed in the map based on the first initial buffer space, and wherein the second label is placed in the map based on the reduced buffer space.

7. The device of claim 6 , wherein determining the area for the first further comprises:
determining a width for the first label based on a sum of respective widths of each character in the text for the first label;
determining a height of a tallest character in the text for the first label; and
determining the area for the first label based on a product of the width and the height.

8. The device of claim 7 , further comprising:
determining a layout of text for the first label based on the area of the first bounding box and the aspect ratio of the first bounding box, wherein the layout is determined using a line wrapping technique.

9. The device of claim 6 , wherein generating, for the second label, the reduced buffer space using the second initial buffer space of the second label further comprises:
determining, for the second label, the second reduced buffer space by reducing the second initial buffer space by a first percentage based on a category of a feature that is being described by the second label.

10. The device of claim 6 , wherein generating, for the second label, the reduced buffer space using the second initial buffer space of the second label further comprises further comprises:
identifying a feature in

Assignees

• Amazon Tech Inc

Inventors

• Parish Scott Robert
• Magouyrk Clayton Matthew
• Edelstein David Adam

Classifications

• G09G5/373 Primary

  for modifying the size of the graphic pattern · CPC title

• G01C21/3673 Primary

  Labelling using text of road map data items, e.g. road names, POI names · CPC title

• G09G2340/145

  related to small screens · CPC title

• G09G5/14

  Display of multiple viewports · CPC title

• G09G2340/04

  Changes in size, position or resolution of an image · CPC title