Method for placing text around polygons and other constraints

• US 6,081,816 A
• Filed: 03/18/1998
• Issued: 06/27/2000
• Est. Priority Date: 03/18/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Agrawal, Siddharth
• Primary Examiner(s): Breene, John E.
• Assistant Examiner(s): KHONG, TRI HOANG
• Application Number:
  US09/040,573
• Time in Patent Office: 832 Days
• Field of Search: 364/900, 707/521, 707/517, 707/518, 707/519, 707/520
• US Class Current: 715/210
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191

Abstract

An object-oriented text layout engine that implements an efficient two-pass text placement procedure. The interface allows the text layout engine to receive parameters that define the document space into which text is to be placed. The interface also allows the text layout engine to receive parameters that define one or more constraints around which the text is to be placed. The text layout engine then places the around the constraint within the document space and returns the text layout to the client program. The text layout engine may be configured in three components, a Fill Constrained Display Rectangle (FCDR) module, a Format Line module, and a Compute Unobstructed Spans (CUS) module. The FCDR module controls the operation of the text layout engine, interacts with the client program, and calls the Format Line and CUS modules as necessary. The CUS module receives a set of parameters that define a candidate rectangle and a constraint that may intersect the candidate rectangle. The CUS module breaks the candidate rectangle to avoid the constraint and returns zero or more unobstructed spans that do not intersect the constraint. The Format Line module receives text characters and a span definition and assigns the text characters to the span.

Claims

1. A computer-readable medium storing computer-executable instructions for performing the steps of:

receiving a first width, a character position, and a vertical position associated with a candidate rectangle;

receiving parameters defining a constraint that intersects with the candidate rectangle;

fitting a first text string to the candidate rectangle;

determining a first height associated with the first text string;

conducting a preliminary text assignment to identify an unobstructed span corresponding to the candidate rectangle, the unobstructed span associated with a second height;

comparing the second height to the first height;

if the second height is equal to the first height, determining whether a second text string fitted to the unobstructed span ends in a delimiter, and if the second text string ends in a delimiter, assigning the second text string to the unobstructed span;

if the second height is greater than the first height, declaring the candidate rectangle invalid and advancing the vertical position by a predetermined amount; and

if the second height is less than the first height refining the unobstructed span.

2. The computer-readable medium of claim 1, wherein the step of conducting a preliminary text assignment comprises the steps of:

identifying the unobstructed span by excluding from the candidate rectangle a portion of the candidate rectangle that intersects with the constraint; and

determining the second height by fitting the second text string to the unobstructed span.

3. The computer-readable medium of claim 1, further comprising the steps of:

if the second text string fitted to the unobstructed span does not end in a delimiter, assigning no text to the unobstructed span.

4. The computer-readable medium of claim 1, wherein the constraint comprises a polygon.

5. The computer-readable medium of claim 1, wherein the constraint comprises a plurality of polygons.

6. The computer-readable medium of claim 1, wherein the constraint comprises an exterior of a polygon such that the second text string is assigned to the interior of the polygon.

7. The computer-readable medium of claim 1, wherein the constraint comprises a smooth curve.

8. The computer-readable medium of claim 1, wherein the step of refining the unobstructed span comprises the steps of:

defining a second candidate rectangle having the first width and the second height;

identifying a second unobstructed span corresponding to the second candidate rectangle by excluding from the second candidate rectangle the portion of the second candidate rectangle that intersects with the constraint;

fitting a third text string to the second unobstructed span;

determining a third height associated with the third text string;

comparing the third height to the second height;

if the third height is equal to or less than the second height, assigning the third text string to the second unobstructed span; and

if the third height is greater than the second height, declaring the second candidate rectangle invalid and advancing the vertical position by a predetermined amount.

9. The computer-readable medium of claim 1, wherein the step of identifying the unobstructed span corresponding to the candidate rectangle comprises the steps of:

determining intersections between the constraint and an infinite horizontal line; and

based on the intersections between the constraint and an infinite horizontal line, excluding interior portions of the constraint from the candidate rectangle.

10. The computer-readable medium of claim 9, wherein the step of determining the unobstructed span corresponding to the candidate rectangle further comprises the steps of:

excluding from the candidate rectangle portions of the candidate rectangle that overlap with edges associated with the constraint.

11. The computer-readable medium of claim 10, wherein the step of determining the unobstructed span corresponding to the candidate rectangle further comprises the steps of:

excluding from the candidate rectangle portions of the candidate rectangle that are within a predefined left clearance criterion from a left edge associated with the constraint; and

excluding from the candidate rectangle portions of the candidate rectangle that are within a predefined right clearance criterion from a right edge associated with the constraint.

12. The computer-readable medium of claim 11, wherein the step of determining the unobstructed span corresponding to the candidate rectangle further comprises the steps of:

determining whether the unobstructed span has a width that is at least as large as a predefined minimum width criterion.

13. The computer-readable medium of claim 9, wherein the step of determining intersections between the constraint and an infinite horizontal line comprises the steps of:

initializing the horizontal line to pass through a bottom side of the candidate rectangle;

initializing an intersection array;

for each of a plurality of line segments defining the polygon, each line segment defined by two adjacent vertices of the polygon,

determining an intersection type between the horizontal line and the line segment;

if the intersection type is a tip intersection, raising the horizontal line a predetermined amount and clearing the intersection array,

if the intersection type is a simple intersection, adding a point of intersection associated with the simple intersection to the intersection array, and

if the intersection type is a collinear intersection, adding the vertices associated with the line segment to the intersection array.

14. The computer-readable medium of claim 13, wherein the step of excluding interior portions of the constraint from the candidate rectangle comprises the step of applying an odd-parity rule to information in the intersection array.

15. The computer-readable medium of claim 14, wherein the step of excluding interior portions of the constraint from the candidate rectangle further comprises the step of:

if the horizontal line passes through a top side associated with the candidate rectangle and the intersection type is a vertex intersection, excluding from the candidate rectangle a portion defined by an extreme left intersection to an extreme right intersection in the intersection array.

16. In or for a computer system, a method for placing text around constraints the steps of:

receiving a first width, a character position, and a vertical position associated with a first candidate rectangle;

receiving parameters defining a constraint that intersects with the first candidate rectangle;

fitting a preliminary text string to the first candidate rectangle;

determining a first height associated with the preliminary text string;

identifying a first set of unobstructed spans corresponding to the candidate rectangle by excluding from the candidate rectangle a portion of the candidate rectangle that intersects with the constraint;

fitting a first set of text strings to the first set of unobstructed spans;

determining a second height associated with the first set of text strings;

comparing the second height to the first height;

if the second height is equal to the first height, assigning the first set of text string to the first set of unobstructed spans and aligning a baseline associated with the first set of text strings;

if the second height is greater than the first height, declaring the first candidate rectangle invalid and advancing the vertical position by a predetermined amount; and

if the second height is less than the first height,

defining a second candidate rectangle having the first width and the second height,

identifying a second set of unobstructed spans corresponding to the second candidate rectangle by excluding from the second candidate rectangle a portion of the second candidate rectangle that intersects with the constraint,

fitting a second set of text strings to the second set of unobstructed spans,

determining a third height associated with the second set of text strings,

comparing the third height to the second height,

if the third height is equal to or less than the second height, assigning the second set of text strings to the second set of unobstructed spans for each unobstructed span of the second set of unobstructed spans by,

determining whether a text string fitted to an unobstructed span ends in a delimiter,

if the fitted text string ends in a delimiter, assigning the text string to the unobstructed span, and

if the fitted text string does not end in a delimiter, assigning no text to the unobstructed span, and

if the third height is greater than the second height, declaring the second candidate rectangle invalid and advancing the vertical position by a predetermined amount.

17. The method of claim 16, wherein the constrain is select from the group comprising:

a polygon;

a plurality of polygons

a smooth curve; and

an exterior of a polygon such that the second text string is assigned to the interior of the polygon.

18. The method of claim 16, wherein each unobstructed span of the second set of unobstructed spans has an associated baseline, further comprising the steps of:

aligning a baselines associated with the unobstructed span of the second set of unobstructed spans.

19. A computer-readable medium storing computer-executable instructions for implementing a text layout engine comprising:

a first module for receiving text characters, constraint parameters, a page width, and a character position from the client module and returning to the client module the text characters placed around the constraint in unobstructed spans with the text characters fitted to each unobstructed span ending in a delimiter;

a second module for receiving the page width and the character position from the first module, fitting a portion of the text characters to a candidate rectangle corresponding to the page width and the character position, and returning to the first module a height associated with the text characters fit to the candidate rectangle; and

a third module for receiving the candidate rectangle and the constraint parameters from the first module, identifying unobstructed spans corresponding to the candidate rectangle by excluding from the candidate rectangle a portion of the candidate rectangle that intersects with the constraint.

20. The text layout engine of claim 19, wherein the third module performs the steps of:

determining intersections between the constraint and an infinite horizontal line;

based on the intersections between the constraint and an infinite horizontal line, excluding interior portions of the constraint from the candidate rectangle;

excluding from the candidate rectangle portions of the candidate rectangle that overlap with edges associated with the constraint;

excluding from the candidate rectangle portions of the candidate rectangle that are within a predefined left clearance criterion from a left edge associated with the constraint;

excluding from the candidate rectangle portions of the candidate rectangle that are within a predefined right clearance criterion from a right edge associated with the constraint; and

determining whether the unobstructed span has a width that is at least as large as a predefined minimum width criterion.