Method for arranging graphic assemblies

• US 20060259856A1
• Filed: 05/12/2005
• Published: 11/16/2006
• Est. Priority Date: 05/12/2005
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Atkins, Clayton Brian
• Granted Patent: US 7,555,730 B2
• Time in Patent Office: Days
• US Class Current: 715/235
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A method for arranging a set of graphic assemblies within an area includes associating a presentation of a first graphic assembly with a tree structure to form a candidate tree; modifying the candidate tree to form at least one alternate candidate tree by associating each presentation of a subsequent graphic assembly with at least one available location in the candidate tree; computing scores for each alternate candidate tree with the subsequent graphic assembly in each possible presentation in the at least one available location on the candidate tree; selecting the alternate candidate tree having a best score; designating the alternate candidate tree having a best score to be the candidate tree; repeating modifying, computing, selecting and designating for all remaining graphic assemblies; and arranging the set of graphic assemblies within the area in accordance with the candidate tree.

Claims

1. A method for arranging a set of graphic assemblies within an area, wherein at least one graphic assembly has more than one presentation, the method comprising:

associating a presentation of a first graphic assembly from the set of graphic assemblies with a tree structure to form a candidate tree;

modifying the candidate tree to form at least one alternate candidate tree by associating each presentation of a subsequent graphic assembly from the set of graphic assemblies with at least one available location in the candidate tree;

computing scores for each alternate candidate tree with the subsequent graphic assembly in each possible presentation in the at least one available location on the candidate tree;

selecting the alternate candidate tree having a best score;

designating the alternate candidate tree having a best score to be the candidate tree;

repeating modifying, computing, selecting and designating for all remaining graphic assemblies; and

arranging the set of graphic assemblies within the area in accordance with the candidate tree.

2. The method of claim 1, further comprising generating a set of paths through each alternate candidate tree, and determining if each alternate candidate tree is feasible by verifying a fixed distance term for each path fits within the area.

3. The method of claim 1, further comprising prior to arranging the set of graphic assemblies, generating a set of paths through the candidate tree, and determining if the candidate tree is feasible by verifying a fixed distance term for each path fits within the area.

4. The method of claim 2, wherein computing scores comprises computing scores only of feasible alternate candidate trees.

5. The method of claim 3, wherein the fixed distance term for each path includes a fixed spacing between adjacent graphic assemblies.

6. The method of claim 4, wherein the fixed distance term for at least one path includes dimensions of at least one graphic assembly having a fixed area.

7. The method of claim 1, wherein at least one of the set of graphic assemblies comprises a collection of graphic elements.

8. The method of claim 1, wherein the tree structure, candidate tree and each alternate candidate tree each comprise:

at least one node; and

at least one leaf emanating from one node

wherein a subtree of the candidate tree comprises a location within the candidate tree and all nodes and leaves emanating from the location.

9. The method of claim 8, wherein modifying the candidate tree comprises:

removing a subtree of the candidate tree associated with one location;

inserting a new node into the candidate tree at said location;

associating one of a horizontal division and a vertical division with the new node;

inserting a new leaf into the candidate tree emanating from the new node;

associating the new leaf with the subsequent graphic assembly; and

inserting the subtree into the candidate tree, said subtree emanating from the new node.

10. The method of claim 9, wherein associating the new leaf with the subsequent graphic assembly comprises associating the new leaf with a first presentation of the subsequent graphic assembly.

11. The method of claim 10, wherein modifying the candidate tree further comprises associating the new leaf with a subsequent presentation of the subsequent graphic assembly.

12. The method of claim 9, wherein the location is selected from one of a node in the candidate tree and a leaf in the candidate tree.

13. The method of claim 1, wherein computing scores comprises determining a fraction of the area occupied by graphic elements in the alternate candidate tree.

14. The method of claim 1, wherein computing scores comprises assessing minimum and maximum values for graphic element sizes of graphic elements in each alternate candidate tree, and determining the ratio of minimum graphic element size value divided by maximum graphic element size value.

15. A method for arranging graphic assemblies within an area, at least one graphic assembly having more than one possible presentation;

comprising;

(a) associating each presentation of a first graphic assembly with a tree structure to form at least one candidate tree;

(b) computing a score for each candidate tree;

(c) selecting the candidate tree having a best score;

(d) modifying the candidate tree to form at least one alternate candidate tree by associating each presentation of a subsequent graphic assembly with each available location in the candidate tree;

(e) computing a score for each alternate candidate tree with the subsequent graphic assembly in each possible presentation in each available location on the candidate tree;

(f) selecting the alternate candidate tree having a best score;

(g) designating the alternate candidate tree having a best score to be the candidate tree;

(h) repeating (d), (e), (f) and (g) for all remaining graphic assemblies; and

(i) arranging the graphic assemblies within the area in accordance with the candidate tree.

16. The method of claim 15, wherein the tree structure, candidate tree and each alternate candidate tree each comprise:

at least one node; and

at least one leaf emanating from one node

wherein a subtree of the candidate tree comprises a location within the candidate tree and all nodes and leaves emanating from the location.

17. The method of claim 16, wherein modifying the candidate tree comprises:

removing a subtree of the candidate tree associated with one location;

inserting a new node into the candidate tree at said location;

associating one of a horizontal division and a vertical division with the new node;

inserting a new leaf into the candidate tree emanating from the new node;

associating the new leaf with a presentation of the subsequent graphic assembly; and

inserting the subtree into the candidate tree, said subtree emanating from the new node.

18. The method of claim 17, wherein the location is selected from one of a node in the candidate tree and a leaf in the candidate tree.

19. A computer-readable medium having computer-executable instructions for performing a method for arranging a set of graphic assemblies in an area, the instructions comprising:

associating a presentation of a first graphic assembly from the set of graphic assemblies with a tree structure to form a candidate tree;

modifying the candidate tree to form at least one alternate candidate tree by associating each presentation of a subsequent graphic assembly from the set of graphic assemblies with at least one available location in the candidate tree;

computing scores for each alternate candidate tree with the subsequent graphic assembly in each possible presentation in each available location on the candidate tree;

selecting the alternate candidate tree having a best score;

designating the alternate candidate tree having a best score to be the candidate tree;

repeating modifying, computing, selecting and designating for all remaining graphic assemblies; and

arranging the set of graphic assemblies within the area in accordance with the candidate tree.

20. The computer-readable medium of claim 19, wherein the computer-executable instructions for computing scores comprise determining a fraction of the area occupied by graphic elements in the alternate candidate tree.

21. The computer-readable medium of claim 19, wherein the computer-executable instructions for computing scores comprise assessing minimum and maximum values for graphic element sizes of graphic elements in each alternate candidate tree, and determining the ratio of minimum graphic element size value divided by maximum graphic element size value.

22. A system for arranging a set of graphic assemblies within an area, the method comprising:

means for forming a candidate tree by associating a presentation of a first graphic assembly from the set of graphic assemblies with a tree structure;

means for forming at least one alternate candidate tree by modifying the candidate tree by associating each presentation of a subsequent graphic assembly from the set of graphic assemblies with at least one available location in the candidate tree;

means for computing scores for each alternate candidate tree with the subsequent graphic assembly in each possible presentation in the at least one available location on the candidate tree;

means for selecting the alternate candidate tree having a best score;

means for designating the alternate candidate tree having a best score to be the candidate tree; and

means for arranging the set of graphic assemblies within the area in accordance with the candidate tree.