Label placement for complex geographic polygons

Patent metadata

Field	Value
Publication number	US-9245366-B1
Application number	US-201414147451-A
Country	US
Kind code	B1
Filing date	Jan 3, 2014
Priority date	Jan 3, 2014
Publication date	Jan 26, 2016
Grant date	Jan 26, 2016

Abstract

Embodiments of the subject technology provide for determining a set of points that form a perimeter of a polygon included in an interactive geographic map. The determined set of points of the perimeter of the polygon is reduced based on a line simplification algorithm. An area, based on the reduced set of points, of the polygon is then reduced by performing a buffering operation on the area that creates an inner buffer zone for the polygon. The subject technology determines whether an area of the inner buffer zone satisfies a predetermined threshold area. Responsive to determining that the predetermined threshold area is satisfied, a centroid of the inner buffer zone may be determined. The subject technology provides, for display to a user, a label at a coordinate position corresponding to the centroid of the inner buffer zone on the interactive geographic map.

First claim

What is claimed is:

1. A computer-implemented method comprising:
determining a polygon that bounds a geographic feature included in an interactive geographic map, wherein the geographic feature comprises a state or country;
determining a set of points that comprises a perimeter of the polygon;
reducing the determined set of points of the perimeter of the polygon into a reduced set of points based on a line simplification algorithm, wherein the reducing includes discarding a subset of points from among the determined set of points, wherein distance of each point, in the subset of points, from a first line connecting two respective endpoints is below a tolerance distance, the two respective endpoints comprising a starting point and an ending point of the subset of points;
dividing a first value of the area of the polygon by a second value of the perimeter of the polygon to determine a first radial distance value;
creating an intermediate buffer zone for the polygon, wherein creating the intermediate buffer zone comprises extending inwards, by the first radial distance value, from the reduced set of points to a center of the polygon to form a respective perimeter of the intermediate buffer zone;
dividing a value of the area of the intermediate buffer zone by a value of the perimeter of the intermediate buffer zone to determine a second radial distance value;
reducing the area, based on the reduced set of points, of the polygon by creating an inner buffer zone for the polygon, wherein creating the inner buffer zone comprises extending inwards, by the second radial distance value, from the perimeter of the intermediate buffer zone to the center of the polygon to form a respective perimeter of the inner buffer zone, and the inner buffer zone comprises a smaller area within the area of the polygon corresponding to a center of the polygon;
determining that a third value of an area of the inner buffer zone is less than or equal to a fourth value of a minimum threshold area;
determining a centroid of the inner buffer zone; and
including a label at the centroid of the inner buffer zone in map data, the label having text or graphical data describing the geographic feature.

2. The computer-implemented method of claim 1 , further comprising:
responsive to determining that the third value is greater than the fourth value, repeating the step of reducing an area of the polygon by creating a respective inner buffer zone for the polygon until a respective area of the respective inner buffer zone is less than or equal to the minimum threshold area.

3. A system comprising:
a processor; and
a memory device including instructions that, when executed by the processor, cause the processor to:
identify a geographic feature included in an map;
determine a polygon that bounds the geographic feature;
determine a first radial distance value by dividing a first area of the polygon by a first value of a perimeter of the polygon;
extend inwards, by the first radial distance value, from the perimeter of the polygon to a center of the polygon to form a perimeter of an intermediate region;
determine a second radial distance value by dividing a second area of the intermediate region by a second value of a perimeter of the intermediate region;
extend inwards, by the second radial distance value, from the perimeter of the intermediate region to the center of the polygon to form a perimeter of an inner region having a third are;
determine that the third area of the inner region is less than or equal to a threshold area;
determine a center point of the inner region of the polygon; and
place a label at the center point of the inner region of the polygon.

4. The system of claim 3 , wherein the instructions further cause the processor to:
determine a set of points that comprises the perimeter of the polygon; and
reduce the determined set of points of the perimeter of the polygon.

5. The system of claim 4 , wherein to reduce the determined set of points of the perimeter of the polygon further causes the processor to:
discard a subset of points from among the determined set of points.

6. The system of claim 5 , wherein:
distance of each point, in the subset of points, from a first line connecting two respective endpoints is below a tolerance distance, the two respective endpoints comprising a starting point and an ending point of the subset of points.

7. The system of claim 3 , wherein the instructions further cause the processor to:
determine a centroid of the inner region;
place the label at the centroid of the inner region; and
provide the map including the label at the centroid of the inner region.

8. The system of claim 3 , wherein the label includes text or graphical data describing the geographic feature.

9. The system of claim 3 , wherein the instructions further cause the processor to:
determine that the polygon is a partial polygon, wherein the partial polygon does not include at least a portion of the geographic feature;
determine a first shape centered within the polygon;
determine a first set of points associated with a first portion of the perimeter of the polygon where the first portion is within the first shape;
determine a second set of points associated with a perimeter of the first shape where a second portion of the perimeter of the polygon is outside of the first shape;
determine a second perimeter of the polygon including the first set of points and the second set of points; and
substitute the second perimeter for the perimeter of the polygon.

10. The system of claim 9 , wherein the instructions further cause the processor to:
determine a first corner corresponding to a top left of the polygon;
determine a second corner corresponding to a bottom left of the polygon;
determine a third corner corresponding to a bottom right of the polygon;
determine a fourth corner corresponding to a top right of the polygon;
determine a first line between the first corner and the third corner;
determine a second line between the second corner and the fourth corner; and
center the first shape at the intersection of the first line and the second line.

11. The system of claim 9 , wherein the instructions further cause the processor to:
determine a center point of the first shape;
determine a first offset in a first direction;
determine a second offset in a second direction perpendicular to the first direction; and
determine a perimeter of the first shape using the center point, the first offset and the second offset.

12. A non-transitory computer-readable medium including instructions stored therein that, when executed by at least one computing device, cause the at least one computing device to:
identify a geographic feature included in an map;
determine a polygon that bounds the geographic feature;
determine a first radial distance value by dividing a first area of the polygon by a first value of a perimeter of the polygon;
extend inwards, by the first radial distance value, from the perimeter of the polygon to a center of the polygon to form a perimeter of an intermediate region;
determine a second radial distance value by dividing a second area of the intermediate region by a second value of a perimeter of the intermediate region;
extend inwards, by the second radial distance value, from the perimeter of the intermediate region to the center of the polygon to form a perimeter of an inner region having a third area;
determine that the third area of the inner region is less than or equal to a threshold area;
determine a center point of the inner region of the polygon; and
place a label at the center point of the inner region of the pol

Assignees

• Amazon Tech Inc

Inventors

• Magouyrk Clayton Matthew
• Parish Scott Robert

Classifications

• G06T11/00 Primary

  Two-dimensional [2D] image generation · CPC title

• G06T11/60 Primary

  Creating or editing images; Combining images with text · CPC title

• G06F16/29

  Geographical information databases · CPC title