Page composition

• US 20040177316A1
• Filed: 08/29/2003
• Published: 09/09/2004
• Est. Priority Date: 08/30/2002
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Goldenberg, Eldan, Lumley, John William, Cliff, David Trevor, Layzell, Paul
• Application Number:
  US10/652,787
• Publication Number:
  US 20040177316A1
• Time in Patent Office: Days
• US Class Current: 715/500
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A page is composed by establishing an arrangement of objects to be fitted on to the page and then carrying out an iterative process to minimise a cost function dependent on properties of the arrangement. Computational advantages are obtained by describing such arrangements as slicing structures.

Claims

1. A method of composing a page, or a portion of a page, of a document, by a programmed processor comprises:

receiving a definition of a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing an arrangement of the plurality of objects such that each object lies within a separate rectangle of a slicing structure dissection of a rectangular area;

receiving and preparing for evaluation for the plurality of objects a function which provides a total cost of an arrangement of the plurality of objects based on one or more properties of the arrangement; and

finding a slicing structure arrangement of the plurality of objects with a minimised total cost by means of an iterative process.

2. A method as claimed in claim 1, wherein the iterative process comprises repeated application of a genetic algorithm.

3. A method as claimed in claim 2, wherein the genetic algorithm is adapted to generate mutations of existing single arrangements and crossovers between pairs of existing arrangements.

4. A method as claimed in claim 1, wherein one or more of the objects in the plurality of objects are fixed either in absolute position in the arrangement, or in position relative to one or more other objects in the plurality of objects.

5. A method as claimed in claim 1, wherein two or more of the objects in the plurality of objects are grouped together into an object group and are constrained to lie within a group rectangle of a slicing structure dissection.

6. A method as claimed in claim 5, wherein the object group is fixed either in absolute position in the arrangement, or in position relative to one or more other groups or objects in the plurality of objects.

7. A method as claimed in claim 5, wherein the iterative process comprises conducting optimising an arrangement of objects within a group and then optimising an arrangement of any groups and ungrouped objects.

8. A method as claimed in claim 7, wherein the iterative process comprises repeatedly conducting the steps of optimising an arrangement of objects within a group and then optimising an arrangement of any groups and ungrouped objects.

9. A method as claimed in claim 7, wherein the iterative process comprises repeated application of a genetic algorithm.

10. A method as claimed in claim 8, wherein the iterative process comprises repeated application of a genetic algorithm.

11. A method as claimed in claim 6, wherein the iterative process comprises optimising an arrangement of objects within a group and then optimising an arrangement of any groups and ungrouped objects.

12. A method as claimed in claim 11, wherein the iterative process comprises repeatedly conducting the steps of optimising an arrangement of objects within a group and then optimising an arrangement of any groups and ungrouped objects.

13. A method as claimed in claim 11, wherein the iterative process comprises repeated application of a genetic algorithm.

14. A method as claimed in claim 12, wherein the iterative process comprises repeated application of a genetic algorithm.

15. A method as claimed in claim 1, wherein one of the one or more properties of the arrangement is the total area occupied by the arrangement.

16. A method as claimed in claim 1, wherein the plurality of objects form two or more groups, and wherein one of the one or more properties is a measure of the proximity to each other of objects which are members of the same group.

17. A method as claimed in claim 16, wherein the proximity is measured by a total distance of lines joining one group member to another group member, such that every member of a group with more than one member has at least one line joined thereto.

18. A method as claimed in claim 17, wherein each group member is joined by one and only one line to every other member of the same group.

19. A method as claimed in claim 1, wherein one of the one or more properties is the aspect ratio of the arrangement.

20. A data carrier having thereon a computer program adapted to program a processor of a computer system to carry out the following steps:

receiving a definition of a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing an arrangement of the plurality of objects such that each object lies within a separate rectangle of a slicing structure dissection of a rectangular area;

preparing for evaluation for the plurality of objects a function which provides a total cost of an arrangement of the plurality of objects based on one or more properties of the arrangement; and

finding a slicing structure arrangement of the plurality of objects with a minimised total cost by means of an iterative process.

21. Computing apparatus comprising a processor programmed to carry out the following steps:

receiving a definition of a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing an arrangement of the plurality of objects such that each object lies within a separate rectangle of a slicing structure dissection of a rectangular area;

preparing for evaluation for the plurality of objects a function which provides a total cost of an arrangement of the plurality of objects based on one or more properties of the arrangement; and

finding a slicing structure arrangement of the plurality of objects with a minimised total cost by means of an iterative process.

22. A method of composing a page, or a portion of a page, of a document, by a programmed processor comprising:

receiving a definition of a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing, for the plurality of objects, evaluation of a function to represent a total area of an arrangement of the plurality of objects;

minimising the function to find a minimised total area arrangement; and

fitting the minimised total area arrangement to the page.

23. A method as claimed in claim 22, wherein the step of minimising the function is constrained such that the minimised total area arrangement has a similar aspect ratio to the page, and wherein the step of fitting the minimised total area arrangement to the page comprises scaling the minimised total area arrangement.

24. A method as claimed in claim 22, wherein the step of minimising the function is constrained such that no dimension of the minimised total area arrangement is greater than a corresponding dimension of the page, and wherein the step of fitting the minimised total area arrangement to the page comprises separating adjacent objects according to a separation rule.

25. A method as claimed in claim 22, wherein the function depends on the aspect ratio of the arrangement, such that minimisation of the function produces a minimised total area arrangement which is a cooptimisation of total area and of the aspect ratio.

26. A method as claimed in claim 22 wherein minimising the function is carried out by means of an iterative process.

27. A method as claimed in claim 26, wherein the iterative process comprises repeated application of a genetic algorithm.

28. A data carrier having thereon a computer program adapted to program a processor of a computer system to carry out the following steps:

receiving a definition of a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing, for the plurality of objects, evaluation of a function to represent a total area of an arrangement of the plurality of objects;

minimising the function to find a minimised total area arrangement; and

fitting the minimised total area arrangement to the page.

29. Computing apparatus comprising a processor programmed to carry out the following steps:

receiving a definition of a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing, for the plurality of objects, evaluation of a function to represent a total area of an arrangement of the plurality of objects;

minimising the function to find a minimised total area arrangement; and

fitting the minimised total area arrangement to the page.

30. A method of providing a customised document having a plurality of pages, comprising:

receiving a plurality of selected objects for inclusion in the document from a database of two-dimensional objects and an assignation of each of the selected objects to one of a plurality of groups, and an assignation of each of the selected objects to one of the pages of the document;

producing a function dependent on a total area of the arrangement and on proximity to each other of objects in the same group and for said one of the pages of the document establishing, for the objects assigned to that page, evaluation of the function;

arranging the objects assigned to the said one of the pages in an arrangement such as to minimise the function.

31. A method as claimed in claim 30, wherein the step of arranging the objects comprises dividing the page into regions and making separate arrangements in each of the regions.

32. A method as claimed in claim 30, wherein said step of arranging the objects comprises establishing an arrangement of the plurality of objects such that each object lies within a separate rectangle of a slicing structure dissection of a rectangular area and finding a slicing structure arrangement of the plurality of objects with a minimised total cost by means of an iterative process.

33. A method as claimed in claim 32, wherein the iterative process comprises repeated application of a genetic algorithm.

34. A data carrier having thereon a computer program adapted to program a processor of a computer system to carry out the following steps:

receiving a plurality of selected objects for inclusion in the document from a database of two-dimensional objects and an assignation of each of the selected objects to one of a plurality of groups, and an assignation of each of the selected objects to one of the pages of the document;

producing a function dependent on a total area of the arrangement and on proximity to each other of objects in the same group and for said one of the pages of the document establishing, for the objects assigned to that page, evaluation of the function;

arranging the objects assigned to the said one of the pages in an arrangement such as to minimise the function

35. Computing apparatus comprising a processor programmed to carry out the following steps:

receiving a plurality of selected objects for inclusion in the document from a database of two-dimensional objects and an assignation of each of the selected objects to one of a plurality of groups, and an assignation of each of the selected objects to one of the pages of the document;

producing a function dependent on a total area of the arrangement and on proximity to each other of objects in the same group and for said one of the pages of the document establishing, for the objects assigned to that page, evaluation of the function;

arranging the objects assigned to the said one of the pages in an arrangement such as to minimise the function

36. A method of composing a page, or a portion of a page, of a document, comprising:

defining a plurality of objects to be fitted on to the page and dimensional attributes of each of the objects;

establishing an arrangement of the plurality of objects such that each object lies within a separate rectangle of a slicing structure dissection of a rectangular area;

establishing a function which provides a total cost of an arrangement of the plurality of objects based on one or more properties of the arrangement; and

finding a slicing structure arrangement of the plurality of objects with a minimised total cost by means of an iterative process.