Constrained document layout

• US 7,634,723 B2
• Filed: 08/27/2004
• Issued: 12/15/2009
• Est. Priority Date: 08/29/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Layzell, Paul
• Primary Examiner(s): Hutton; Doug
• Assistant Examiner(s): Tran; Quoc A
• Application Number:
  US10/569,845
• Publication Number:
  US 20070118797A1
• Time in Patent Office: 1,936 Days
• Field of Search: 715/243, 715244-247, 715/225, 715/212, 700/171, 345/660
• US Class Current: 715/243
• 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

A description of document elements to be laid out on a page, include two or more hierarchical levels. Each document element is placed at one of the hierarchical levels. Elements at a lower hierarchical level are associated with a document element at a next higher hierarchical level. Page layout according to such a document description may be optimised discretely at different hierarchical levels without affecting constraints.

Claims

1. A method of laying out a page which is to contain a plurality of discrete document elements, comprising:

receiving a hierarchical page description describing layout of the discrete document elements on the page, wherein the hierarchical page description contains two or more hierarchical levels and, for each hierarchical level, the page description contains a description of discrete documents from the plurality of discrete document elements in the hierarchical level and at least one constraint for arranging the discrete documents in the hierarchical level, and

for a particular hierarchical level of the two or more hierarchical levels, the at least one constraint for that particular hierarchical level is only applicable for that particular hierarchical level;

for each hierarchical level, optimizing layout of the page described by the hierarchical page description, one hierarchal level at a time, by rearranging the plurality of discrete elements in a single hierarchical level at a same time using the at least one constraint for the hierarchical level, to minimize the value of a cost function; and

laying out the discrete document elements on the page for each hierarchal level, one hierarchal level at a time, according to the optimized hierarchical page description layout for each hierarchal level.

2. A method as claimed in claim 1, wherein a discrete document element may consist either of a representation of a group of document elements associated together at a lower hierarchical level or of a primitive document element.

3. A method as claimed in claim 2, wherein the hierarchical page description is representable as a tree with a primitive document element at each leaf node and with a representation of a group of document elements at each branching node.

4. A method as claimed in claim 1, wherein said optimizing comprises carrying-out, at a hierarchical level, rearrangement operations only on document elements forming part of a group represented as a document element at the next higher hierarchical level.

5. A method as claimed in claim 1, wherein optimizing the hierarchical page description layout comprises repeated use of a stochastic process.

6. A method as claimed in claim 5, wherein the hierarchical page description is describable as one or more genes each comprising a series of document elements and operators, and the stochastic process comprises use of a genetic algorithm.

7. A method as claimed in claim 6, wherein the hierarchical page description comprises one or more repeated genes.

8. A method as claimed in claim 7, wherein one or more classes are determined for document elements, a repeated gene is describable in terms of an ordering of element classes, and each expression of a repeated gene is describable in terms of document elements or groups of document elements corresponding to some or all of the element classes in the repeated gene.

9. A method as claimed in claim 1, wherein the hierarchical page description describes a slicing structure.

10. A method as claimed in claim 1, wherein one or more of the rearrangement operations comprises separating a constrained element from one or more unconstrained elements, rearranging the unconstrained elements without rearranging the separated constrained element, and then recombining the rearranged unconstrained elements with the constrained element that has not been rearranged.

11. A computer comprising a processor programmed to perform the method of claim 1.

12. A computer-readable storage medium comprising code adapted to program when executed, a processor of a computer system, to perform the method of claim 1.

13. The method as defined in claim 1, wherein said optimizing is performed, at a single hierarchical level at a time, from the lowest hierarchical level to the highest hierarchical level.

14. A computer-readable storage medium having one or more instructions, which when executed by a processor, to perform operations of laying out a page which is to contain a plurality of discrete document elements comprising:

two or more hierarchical levels;

wherein each document element is placed at one of the hierarchical levels, and for each hierarchical level, the page description contains a description of discrete documents from the plurality of discrete document elements in the hierarchical level and at least one constraint for arranging the discrete documents in the hierarchical level;

for a particular hierarchical level of the hierarchical levels, the constraint for that particular hierarchical level is only applicable for that particular hierarchical level;

said description further comprising, in association with at least one of the document elements, a further constraint individually placed on said at least one document element and specifying how said at least one document element should be laid out on the page; and

the hierarchical levels in the description are representable as a tree with a primitive document element at each leaf node and with a representation of a group of document elements in one of the hierarchical levels at each branching node, and wherein each branching node represents a constraint placed on the elements of the group that is represented at that branching node, and

for each hierarchical level, optimizing layout of the page described by the hierarchical page description, one hierarchal level at a time, by rearranging the plurality of discrete elements in a single hierarchical level at a same time using the at least one constraint for the hierarchical level, to minimize the value of a cost function; and

laying out the discrete document elements on the page for each hierarchal level, one hierarchal level at a time, according to the optimized hierarchical page description layout for each hierarchal level.

15. A computer-readable storage medium as claimed in claim 14, wherein each representation of a group of document elements is describable as a gene comprising one or more operators and one or more operands.

16. A computer-readable storage medium as claimed in claim 15, wherein the hierarchical page description comprises one or more repeated genes.

17. A computer-readable storage medium as claimed in claim 16, wherein one or more classes are determined for document elements, a repeated gene is describable in terms of an ordering of element classes, and each expression of a repeated gene is describable in terms of document elements or groups of document elements corresponding to some or all of the element classes in the repeated gene.

18. A computer-readable storage medium as claimed in claim 14, wherein the description of document elements represents a slicing structure.

19. A method of generating a description of document elements to be laid out on a page, comprising:

identifying primitive document elements to be laid out on the page;

identifying constraints on the layout of the primitive document elements on the page;

constructing a hierarchical page description with a plurality of hierarchical levels, each primitive document element being placed at one of the hierarchical levels, and each document element at a lower hierarchical level being linked by one of the constraints to a document element at a next higher hierarchical level;

storing, in said description and in association with at least one of the document elements, a further constraint individually placed on said at least one document element and specifying how said at least one document element should be laid out on the page; and

for each hierarchical level, optimizing layout of the page described by the hierarchical page description, one hierarchal level at a time, by rearranging the plurality of discrete elements in a single hierarchical level at a same time using the at least one constraint for the hierarchical level, to minimize the value of a cost function; and

laying out the discrete document elements on the page for each hierarchal level, one hierarchal level at a time, according to the optimized hierarchical page description layout for each hierarchal level.

20. The method as defined in claim 19, wherein said further constraint specifies whether said at least one document element should occupy a particular position on the page, or overlap another document element.

21. The method of claim 19, wherein the further constraint is only applicable for the at least one document element in the hierarchical level that the at least one document element is placed.