Method for arranging graphic assemblies

• US 8,056,013 B2
• Filed: 05/13/2005
• Issued: 11/08/2011
• Est. Priority Date: 05/13/2005
• 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: Atkins, Clayton Brian
• Primary Examiner(s): Lo, Weilun
• Assistant Examiner(s): Iturralde, Enrique
• Application Number:
  US11/128,543
• Publication Number:
  US 20060259857A1
• Time in Patent Office: 2,370 Days
• Field of Search: 715/517, 715/243, 715730-732, 715/764, 715/783, 715/788, 715/790, 715/810, 715/838, 715/866
• US Class Current: 715/788
• 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 establishing a candidate tree associated with the set of graphic assemblies; determining if the candidate tree is a feasible candidate tree; and in response to the candidate tree being a feasible candidate tree, arranging the set of graphic assemblies within the area in accordance with the candidate tree.

Claims

1. A machine-implemented method of arranging a set of graphic assemblies within an area, comprising:

establishing a candidate tree having at least one node and at least one leaf, wherein each node corresponds to a respective partition of the area, each leaf defines a relative position of a different respective one of the graphic assemblies in the area, and at least one of the graphic assemblies is a multi-element graphic assembly that comprises a respective group of multiple discrete graphic elements arranged in one of multiple possible relative positional arrangements within the area;

determining if the candidate tree is a feasible candidate tree; and

in response to a determination that the candidate tree is a feasible candidate tree, arranging the set of graphic assemblies within the area in accordance with the candidate tree.

2. The method of claim 1, wherein determining if the candidate tree is a feasible candidate tree comprises:

generating a set of path lengths through the candidate tree; and

verifying a fixed distance term for each path length fits within the area.

3. The method of claim 2, further comprising determining an area of each of the set of graphic assemblies.

4. The method of claim 1, wherein establishing a candidate tree associated with the set of graphic assemblies comprises:

associating 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 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 available location on the candidate tree;

selecting the alternate candidate tree having a best score;

designating the alternate candidate tree to be the candidate tree;

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

5. The method of claim 4, wherein at least one of the set of graphic assemblies has more than one possible presentation, and wherein:

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

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

27. The method of claim 1, wherein the establishing comprising inserting into a binary tree the multi-element graphic assembly with its respective group of graphic elements arranged in different ones of the possible relative positional arrangements to create respective candidate binary trees, and selecting one of the candidate binary trees as the candidate tree.

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

establishing at least one candidate tree having at least one internal node, and at least one terminal node emanating from an internal node, wherein each terminal node is associated with a presentation of a graphic assembly;

determining a set of path lengths through each candidate tree;

comparing a fixed distance term for each path length to a size of the area;

discarding candidate trees where one or more of the fixed distance terms is greater than the size of the area;

computing a score for each remaining candidate tree;

selecting the candidate tree having a best score; and

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

7. The method of claim 6, wherein at least one of the graphic assemblies comprises a plurality of graphic elements.

8. The method of claim 6, wherein each of the graphic assemblies comprise one or more graphic elements, and wherein each graphic element is one of a fixed area graphic element and a variable-area graphic element.

9. The method of claim 8, further comprising determining an area for each variable-area graphic element before computing a score.

10. The method of claim 6, wherein determining a set of path lengths through each candidate tree comprises determining at least one horizontal path length and at least one vertical path length through each candidate tree.

11. The method of claim 10, wherein comparing a fixed distance term for each path length to a size of the area comprises comparing a fixed distance term for each horizontal path length to a width of the area, and comparing a fixed distance term for each vertical path length to a height of the area.

12. The method of claim 6, wherein determining a set of path lengths through each candidate tree comprises determining an exhaustive set of path lengths through each candidate tree.

13. The method of claim 6, wherein the fixed distance term for each path length includes a predetermined space between adjacent graphic assemblies.

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

15. The method of claim 6, further comprising, prior to computing a score, determining an area for variable-area graphic elements within each graphic assembly.

16. The method of claim 15, wherein computing a score comprises summing areas of variable-area graphic elements, and wherein selecting the candidate tree having a best score comprises determining the candidate tree having the largest sum.

17. The method of claim 15, wherein computing a score comprises determining a fraction of the area occupied by graphic elements in the candidate tree.

18. The method of claim 15, wherein computing a score comprises assessing minimum and maximum values for graphic element sizes of graphic elements in the candidate tree, and determining the ratio of minimum graphic element size value divided by maximum graphic element size value.

19. The method of claim 6, further comprising modifying the selected candidate tree to form at least one alternate candidate tree.

20. The method of claim 19, wherein a subtree of the selected candidate tree comprises a location within the selected candidate tree and all internal and terminal nodes emanating from the location, and wherein modifying the selected candidate tree comprises:

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

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

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

inserting a new terminal node into the selected candidate tree emanating from the new internal node;

associating the new terminal node with the subsequent graphic assembly; and

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

21. The method of claim 20, wherein associating the new terminal node with the subsequent graphic assembly comprises associating the new terminal node with a first presentation of the subsequent graphic assembly.

22. The method of claim 21, wherein modifying the selected candidate tree further comprises associating the new terminal node with a subsequent presentation of the subsequent graphic assembly.

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

establishing a candidate tree having at least one node and at least one leaf, wherein each node corresponds to a respective partition of the area, each leaf defines a relative position of a different respective one of the graphic assemblies in the area, and at least one of the graphic assemblies is a multi-element graphic assembly that comprises a respective group of multiple discrete graphic elements arranged in one of multiple possible relative positional arrangements within the area;

determining if the candidate tree is a feasible candidate tree; and

in response to a determination that the candidate tree is a feasible candidate tree, arranging the set of graphic assemblies within the area in accordance with the candidate tree.

24. The computer-readable medium of claim 23, wherein the computer-executable instructions for determining if the candidate tree is a feasible candidate tree comprises:

generating a set of path lengths through the candidate tree; and

verifying a fixed distance term for each path length fits within the area.

25. The computer-readable medium of claim 24, wherein the computer-executable instructions further comprise determining an area of each of the set of graphic assemblies.

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

means for establishing a candidate tree having at least one node and at least one leaf, wherein each node corresponds to a respective partition of the area, each leaf defines a relative position of a different respective one of the graphic assemblies in the area, and at least one of the graphic assemblies is a multi-element graphic assembly that comprises a respective group of multiple discrete graphic elements arranged in one of multiple possible relative positional arrangements within the area;

means for determining if the candidate tree is a feasible candidate tree; and

means for arranging the set of graphic assemblies within the area in accordance with the candidate tree, in response to a determination that the candidate tree is a feasible candidate tree.