Polygon labeling by dominant shapes

• US 10,204,431 B1
• Filed: 07/15/2014
• Issued: 02/12/2019
• Est. Priority Date: 07/15/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hou, Tingbo, Hagemark, Bent
• Primary Examiner(s): Xiao, Ke
• Assistant Examiner(s): Shin, Andrew
• Application Number:
  US14/331,574
• Time in Patent Office: 1,673 Days
• Field of Search: 345581, 345619, 345622, 345629, 345441-443, 345467, 345468, 382113, 382286, 382288, 382291, 382292, 715764, 715765
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2219/004 Annotating, labelling
• CPC Class Codes: G06T 2219/2004 Aligning objects, relative positioning of parts
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

A method for generating label positions for labeling polygons includes receiving a description of a polygon, determining an inscribed circle within the polygon, and determining a single-branch shape that fits completely within the polygon. The method also includes generating an indication of a first candidate label position, based on the inscribed circle, and generating an indication of a second candidate label position, based on the centerline. Still further, the method includes providing the indication of the first candidate label position and the indication of the second candidate label position to a rendering component for positioning a label for the polygon in accordance with at least one of the first candidate label position and the second candidate label position.

Claims

1. A method for generating label positions for labeling polygons, the method comprising:

receiving, by one or more processors, a description of a polygon;

generating, by the one or more processors, a Voronoi diagram based on vertices of the polygon,

determining, by the one or more processors, a substantially largest inscribed circle that fits within the polygon based on the Voronoi diagram, including;

calculating a respective radius of each of a plurality of segments of the Voronoi diagram that is enclosed within a boundary of the polygon, and

selecting a largest radius from among the calculated radii, wherein the largest radius is a radius of the substantially largest inscribed circle;

determining, by the one or more processors based on the Voronoi diagram, a single-branch shape that fits completely within the polygon, wherein a centerline of the single-branch shape is a polyline that has;

(i) only one branch, and (ii) a largest coverage of the polygon;

generating, by the one or more processors, an indication of a first candidate label position, based on the inscribed circle;

generating, by the one or more processors, an indication of a second candidate label position, based on the centerline; and

providing, by the one or more processors, the indication of the first candidate label position and the indication of the second candidate label position to a rendering component for positioning a label for the polygon in accordance with at least one of the first candidate label position and the second candidate label position.

2. The method of claim 1, further comprising:

generating, by the one or more processors, a bounding box for the inscribed circle;

wherein generating the indication of the first candidate label position is based on the bounding box.

3. The method of claim 1, wherein determining the largest coverage based on the Voronoi diagram includes:

for each of a plurality of segments of the Voronoi diagram, calculating, by the one or more processors, an area that covers the respective segment and that covers a radius corresponding to the respective segment,

determining, by the one or more processors, the largest coverage corresponding to the centerline of the single-branch shape by identifying a continuous subset of the plurality of segments having an accumulated area greater than other continuous subsets of the plurality of segments, the accumulated area calculated by summing the area corresponding to each of the subset of the plurality of segments.

4. The method of claim 1, wherein the single-branch shape covers an area including the inscribed circle.

5. The method of claim 1, further comprising:

generating, by the one or more processors, a line based on the centerline of the single-branch shape, wherein the line based on the centerline of the single-branch shape is not self-intersecting, and wherein generating the indication of the second candidate label position is based on the line.

6. The method of claim 5, further comprising:

detecting, by the one or more processors, that the centerline of the single-branch shape includes a loop,

wherein generating the line based on the centerline of the single-branch shape includes breaking the centerline of the single-branch shape to cause the line based on the centerline to not self-intersect.

7. The method of claim 1, further comprising:

generating, by the one or more processors, a line based on the centerline of the single-branch shape, wherein generating the line based on the centerline includes smoothing the centerline of the single-branch shape to produce the line based on the centerline, and wherein generating the indication of the second candidate label position is based on the line.

8. A computing device comprising:

one or more processors; and

a non-transitory computer readable medium storing instructions thereon that, when executed by the one or more processors, cause the computing device to;

receive a description of a polygon,

determine an inscribed circle within the polygon,

determine a single-branch shape that fits completely within the polygon, wherein a centerline of the single-branch shape is a polyline that has;

(i) only one branch, and (ii) a largest coverage of the polygon, wherein the centerline of the single-branch shape intersects a center point of the inscribed circle,

generate an indication of a first candidate label position, based on the inscribed circle,

generate an indication of a second candidate label position, based on the centerline, and

provide the indication of the first candidate label position and the indication of the second candidate label position to a rendering component for positioning a label for the polygon in accordance with at least one of the first candidate label position and the second candidate label position.

9. The computing device of claim 8,

wherein the received description of the polygon includes a received plurality of vertices,

wherein the instructions further cause the computing device to generate a resampled plurality of vertices representing the polygon based on the received plurality of vertices, the resampled plurality of vertices being fewer in number than the received plurality of vertices, and

wherein determining the inscribed circle and the single-branch shape includes determining the inscribed circle and the single-branch shape based on the resampled plurality of vertices.

10. The computing device of claim 9,

wherein the instructions further cause the computing device to generate a Voronoi diagram based on the resampled plurality of vertices representing the polygon, and

wherein determining the inscribed circle and the single-branch shape includes determining the inscribed circle and the single-branch shape based on a plurality of segments of the Voronoi diagram.

11. The computing device of claim 9, wherein generating the resampled plurality of vertices includes simplifying the received plurality of vertices to a pre-defined number of the resampled plurality of vertices.

12. The computing device of claim 8, wherein the instructions further cause the computing device to:

generate a line based on the centerline of the single-branch shape, wherein generating the line based on the centerline includes smoothing the centerline of the single-branch shape to produce the line based on the centerline, and wherein generating the indication of the second candidate label position is based on the line,

detect that the line based on the centerline has a length below a threshold, and

replace the line based on the centerline with a horizontal diameter of the inscribed circle.

13. The computing device of claim 8, wherein a boundary of the single-branch shape includes portions of a boundary of the polygon connected by one or more arcs.

14. A method for generating label positions for labeling polygons, the method comprising:

receiving, by one or more processors, a description of a polygon;

determining, by the one or more processors, an inscribed circle within the polygon

determining, by the one or more processors, a single-branch shape that fits completely within the polygon, wherein a centerline of the single-branch shape is a polyline that has;

(i) only one branch, and (ii) a largest coverage of the polygon;

detecting, by the one or more processors, that the centerline of the single-branch shape includes a loop,

generating, by the one or more processors, a line based on the centerline of the single-branch shape, including breaking the centerline of the single-branch shape to cause the line based on the centerline to not self-intersect;

generating, by the one or more processors, an indication of a first candidate label position, based on the inscribed circle;

generating, by the one or more processors, an indication of a second candidate label position, based on the line; and

providing, by the one or more processors, the indication of the first candidate label position and the indication of the second candidate label position to a rendering component for positioning a label for the polygon in accordance with at least one of the first candidate label position and the second candidate label position.