Methods of centering nodes in a hierarchical display

• US 5,333,254 A
• Filed: 10/02/1991
• Issued: 07/26/1994
• Est. Priority Date: 10/02/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Robertson, George G.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Breene, John E.
• Application Number:
  US07/770,196
• Time in Patent Office: 1,028 Days
• Field of Search: 395/155-161, 395/137-138, 395/152, 340/709-710, 340/723, 340/747, 345/121-123
• US Class Current: 715/853
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance

Abstract

An image is presented that includes a node-link structure. The nodes are in rows, and each row extends across a centering line. The rows are in sequence along the centering line, with links between nodes in adjacent rows. When a user requests a centering operation for an indicated node, a sequence of images is presented, each including a row that appears to be a continuation of the row with the indicated node and that includes a continued indicated node that appears to be a continuation of the indicated node. The rows appear to be shifted, bringing the continued indicated nodes toward the centering line, until a final shift locks the continued indicated node into position at the centering line. The positions of the indicated node and a subset of the continued indicated nodes together can define an asymptotic path that begins at the position of the indicated node and approaches the centering line asymptotically until the final shift occurs. The displacements between positions can follow a logarithmic function, with each displacement being a proportion of the distance from the preceding position to the centering line. Each step can include an animation loop. If the node-link structure represents a hierarchical body of data with each node representing a data item, the indicated node'"'"'s descendants and ancestors within the hierarchy can also be shifted to the centering line. Each node can be rectangular, and the nodes in each row can be separated by equal offsets to provide compact rows. Each node can be a selectable unit, so that the user can request a centering operation by selecting a node, such as with a mouse click.

Claims

1. A method of operating a processor connected for providing image data to an image output device that includes a display, the image output device presenting images on the display in response to the image data;

the processor further being connected for receiving signals from a user input device;

the method comprising steps of;

providing first image data so that the image output device presents a first image, the first image including a first node-link structure that is perceptible as lying on a plane-like surface;

the first node-link structure including a first set of three or more nodes arranged in two or more rows with at least two nodes in one row and at least one node in a different row;

the first node-link structure having a centering line across which row extends;

the first node-link structure further including a first set of two or more links, each of the first set of links being perciptible as connecting two of the first set of nodes, the two connected nodes being in different rows;

receiving a signal from the user input device indicating one of the first set of nodes in the first node-link structure;

in response to the signal from the user, determining whether the indicated node is at the centering line of the first node-link structure; and

if the indicated node is not at the centering line of the first node-link structure, providing second image data so that the image output device presents a second image, the second image including a second node-link structure that is perceptible as lying on a plane-like surface;

the second node-link structure including a second set of three or more nodes arranged in two or more rows with at least two modes in one row and at least one node in a different row;

the second node-link structure having a centering line across which row extends;

the second node-link structure further including a second set of two or more links, each of the second set of links being perceptible as connecting two of the second set of nodes, the two connected nodes being in different rows;

each of the second set of nodes being perceptible as a continuation of a respective one of the first set of nodes;

the second set of nodes including a continued indicated node that is perceptible as a continuation of the indicated node;

the continued indicated node being at the centering line of the second node-link structure;

the rows of the second node-link structure being perceptible as continuations of the rows of the first node-link structure, with the indicated node'"'"'s row shifted to position the continued indicated node at the centering line of the second node-link structure.

2. The method of claim 1 in which the second node-link structure is perceptible as a continuation of the first node-link structure.

3. The method of claim 1 in which the processor is further connected for accessing a body of data that includes a hierarchy of data items, the hierarchy including two or more levels, each data item being at a respective one of the levels;

the first and second node-link structures each representing the body of data, each node representing a respective one of the data items, each row including nodes representing data items at a respective level of the hierarchy of data items, the links representing hierarchical relationships between data items;

the rows being positioned along the centering line according to the respective levels of the hierarchy of data items.

4. The method of claim 3 in which the levels of the hierarchy of data items include a top level and two or more lower levels, each lower level having a next higher level;

each node in a row representing a lower level having a link to a respective parent node in a row representing the lower level'"'"'s next higher level.

5. The method of claim 4 in which the determining step comprises a substep of determining whether the indicated node has a respective parent node and, if so, whether the indicated node'"'"'s parent node is at the centering line of the first node-link structure;

if the indicated node has a respective parent node, the second set of nodes including a continued parent node that is perceptible as a continuation of the parent node;

the continued parent node being at the centering line of the second node-link structure, so that if the indicated node'"'"'s parent node is not at the centering line of the first node-link structure, the parent node'"'"'s row is perceptible as shifted to position the continued parent node at the centering line of the second node-link structure.

6. The method of claim 4 in which the determining step comprises a substep of determining whether the first node-link structure includes child nodes whose respective parent node is the indicated node;

if the first node-link structure includes child nodes whose respective parent node is the indicated node, the second set of nodes including continued child nodes that are perceptible as continuations of the child nodes;

the continued child nodes being at the centering line of the second node-link structure, so that if the child nodes are not at the centering line of the first node-link structure, the row that includes the child nodes is perceptible as shifted to position the continued child nodes at the centering line of the second node-link structure.

7. The method of claim 1 in which the indicated node is a selectable unit, the signal from the user input device being a signal selecting the indicated node.

8. The method of claim 7 in which the user input device includes a mouse with a button, the user clicking the mouse button to provide the signal.

9. The method of claim 1 in which each node is perceptible as a rectangle, each row extending in a respective first direction across the centering line, each node in each row having a respective first side extending in a respective second direction perpendicular to the row'"'"'s first direction so that the nodes in each row have parallel first sides.

10. The method of claim 9 in which each node has a third side parallel to the first side, the nodes in each row being in a sequence such that the third side of a preceding node in the sequence is next to the first side of a following node in the sequence, each third side being separated from the first side next to it by an equal offset;

11. A method of operating a processor connected for providing image data to an image output device that includes display, the image output device presenting images on the display in response to the image data;

the processor further being connected for receiving signals from a user input device;

the method comprising;

a step of providing initial image data so that the image output device presents an initial image, the initial image including an initial node-link structure that is perceptible as lying on a plane-like surface;

the initial node-link structure including an initial set of three or more nodes arranged in two or more rows with at least two nodes in one row and at least one node in a different row;

the initial node-link structure having a centering line across which each row extends;

the initial structure further including an initial set of two or more links, each of the initial set of links being perceptible as connecting two of the initial set of nodes, the two connected nodes being in different rows;

a step of receiving a signal from the user input device indicating one of the initial set of nodes in the initial node-link structure;

in response to the signal from the user, a step of determining whether the indicated node is at the centering line of the initial node-link structure; and

if the indicated node is not at the centering line of the initial node-link structure, a sequence of image output steps, each image output step providing respective-image data so that the image output device presents a respective image including a respective node-link structure that is perceptible as lying on a plane-like surface;

each image output step'"'"'s node-link structure including a respective set of three or more nodes arranged in two or more rows with at least two nodes in one row and at least one node in a different row;

the node-link structure having a centering line across which each row extends;

each image output step'"'"'s node-link structure further including a respective set of two or more links, each perceptible as connecting two of the respective set of nodes, the two connected nodes being in different rows;

each node in each image output step'"'"'s set of nodes being perceptible as a continuation of a respective one of the initial set of nodes;

the step'"'"'s set of nodes including a respective continued indicated node that is perceptible as a continuation of the indicated node;

the step'"'"'s continued indicated node being shifted toward the centering line of the step'"'"'s node-link structure;

the rows of the step'"'"'s node-link structure being perceptible as continuations of the rows of the initial node-link structure, with the indicated node'"'"'s row shifted to move the step'"'"'s continued indicated node toward centering line of the second node-link structure.

12. The method of claim 11 in which the sequence of image output steps is performed in approximately one second.

13. The method of claim 11 in which the indicated node in the initial image is perceptible as having a respective position and the continued indicated node in the respective image of each image output step is perceptible as having a respective position, the respective positions of the indicated node in the initial image and the continued indicated nodes in the respective images of a subset of the image output steps together defining an asymptotic path.

14. The method of claim 13 in which the asymptotic path begins at the indicated node'"'"'s position in the initial image and is asymptotic with respect to the centering line.

15. The method of claim 13 in which the respective position of each of the continued indicated nodes in the respective images of the subset of the image output steps is displaced by a respective displacement from the respective position of a next preceding step;

the respective displacements of the continued indicated nodes in the respective images of the subset of the image output steps following a logarithmic function.

16. The method of claim 15 in which the respective position of each of the continued indicated nodes in the respective images of the subset of the image output steps is at a respective distance from the centering line;

the respective displacement of each continued indicated node in the respective images of the subset of the image output steps being a proportion of the respective distance of the next preceding step.

17. The method of claim 13 in which the sequence of image output steps includes a last shift step, the last shift step following the subset of the image output steps;

the last shift step'"'"'s continued indicated node being at the centering line so that a next preceding step'"'"'s continued indicated node is perceptible as locking into position at the centering line.

18. The method of claim 11 in which each of the sequence of image output steps comprises a substep of performing an animation loop.

19. A method of operating a processor connected for providing image data to an image output device that includes a display, the image output device presenting images on the display in response to the image data;

the processor further being connected for receiving signals from a user input device;

the method comprising steps of;

providing first image data so that the image output device presents a first image, the first image including a first node-link structure that is perceptible as lying on a plane-like surface;

the first node-link structure including a first set of three or more nodes arranged in two or more rows with at least two nodes in one row and at least one node in a different row;

the first node-link structure having a centering line across which each row extends;

the first node-link structure further including a first set of two or more links, each of the first set of links being perceptible as connecting two of the first set of nodes, the two connected nodes being in different rows;

receiving a signal from the user input device indicating an indicated set of nodes in the first node-link structure;

each of the rows in the first node-link structure including no more than one of the indicated set of nodes;

in response to the signal from the user, determining whether each of the nodes in the indicated set of nodes is at the centering line of the first node-link structure; and

if at least one of the nodes in the indicated set of nodes is not at the centering line of the first node-link structure, providing second image data so that the image output device presents a second image, the second image including a second node-link structure that is perceptible as lying on a plane-like surface;

the second node-link structure including a second set of three or more nodes arranged in two or more rows, each node being in a respective one of the rows withat least two nodes in one row and at least one node in a a different row;

the second node-link structure having a centering line across which each row extends;

the second node-link structure further including a second set of two or more links, each of the second set of links being perceptible as connecting two of the second set of nodes, the two connected nodes being in respective rows that are next to each other in the sequence;

each of the second set of nodes being perceptible as a continuation of a respective one of the first set of nodes;

the second set of nodes including, for each of the indicated set of nodes in the first node-link structure that is not at the centering line, a respective continued node that is perceptible as a continuation of the node;

the continued node being at the centering line of the second node-link structure;

the rows of the second node-link structure being perceptible as continuations of the rows of the first node-link structure, with each row that includes a continued node of one of the indicated set of nodes that is not at the centering line in the first node-link structure shifted to position the continued node at the centering line of the second node-link structure.

20. The method of claim 19 in which the processor is further connected for accessing a body of data that includes a hierarchy of data items, the hierarchy including two or more levels, each data item being at a respective one of the levels;

the first and second node-link structures each representing the body of data, each node representing a respective one of the data items, each row including nodes representing data items at a respective level of the hierarchy of data items, the links representing hierarchical relationships between data items;

the rows being positioned along the centering line according to the respective levels of the hierarchy of data items.

21. The method of claim 20 in which the levels of the hierarchy of data items include a top level and two or more lower levels, each lower level having a next higher level;

each node in a row representing a lower level having a link to a respective parent node in a row representing the lower level'"'"'s next higher level.

22. The method of claim 21 in which the indicated set of nodes includes a root node representing a data item at the top level of the hierarchy and a number of lower level nodes, each lower level node'"'"'s parent node being in the indicated set so that the indicated set includes a lowest node and all ancestors of the lowest node.

23. The method of claim 22 in which the step of determining whether each of the nodes in the indicated set of nodes is at the centering line comprises:

a substep of accessing the lowest node'"'"'s data item to determine whether the lowest node is at the centering line; and

a sequence of substeps, each substep accessing the data item represented by the respective parent node of the node whose data item was accessed in the previous substep to determine whether the parent node is at the centering line;

the sequence of substeps continuing until the root node'"'"'s data item is accessed.

24. The method of claim 22 in which the signal from the user input device indicates a starting node that is in the indicated set of nodes;

the step of determining whether each of the nodes in the indicated set of nodes is at the centering line comprising;

a substep of accessing the starting node'"'"'s data item to determine whether the starting node is the parent node of any other node; and

if the starting node is the parent node of another node, a sequence of substeps, each substep accessing a data item represented by a node whose parent node is the node whose data item was accessed in the previous substep and determining whether the accessed data item is represented by a node that is the parent node of any other node;

the sequence of substeps continuing until a data item is accessed that is represented by a node that is not the parent node of any other node, the lowest node being the node that is not the parent node of any other node.

25. The method of claim 24 in which one of the substeps in the sequence of substeps accesses a data item represented by a node that is the parent node of a children set of two or more other nodes;

the one of the substeps comprising a substep of selecting a center one of the children set of nodes as the node whose data item is accessed in the next substep in the sequence.

26. A method of operating a processor connected for providing image data to an image output device that includes a display, the image output device presenting images on the display in response to the image data;

the processor further being connected for receiving signals from a user input device;

the method comprising;

providing first image data so that the image output device presents a first image, the first image including a first node-link structure that is perceptible as lying on a plane-like surface;

the first node-link structure including a first set of three or more nodes arranged in two or more rows with at least two nodes in one row and at least one node in a different row;

the first node-link structure having a centering line across which each row extends;

the first node-link structure further including a first set of two or more links, each of the first set of links being perceptible as connecting two of the first set of nodes, the two connected nodes being in different rows;

receiving a signal from the user input device indicating one of the first set of nodes in the first node-link structure;

in response to the signal from the user, automatically determining whether the indicated node is at the centering line of the first node-link structure;

if the indicated node is not at the centering line of the first node-link structure, automatically providing second image data so that the image output device presents a second image following the first image in sequence so that the first and second images are presented in succession;

the second image including a second node-link structure that is perceptible as lying on a plane-like surface;

the second node-link structure including a second set of three or more nodes arranged in two or more rows with at least two nodes in one row and at least one node in a different row;

the second node-link structure having a centering line across which each row extends;

the second node-link structure further including a second set of two or more links, each of the second set of links being perceptible as connecting two of the second set of nodes, the two connected nodes being in different rows;

each of the second set of nodes being perceptible as a continuation of a respective one of the first set of nodes;

the second set of nodes including a continued indicated node that is perceptible as a continuation of the indicated node;

the continued indicated node being at the centering line of the second node-link structure;

the rows of the second node-link structure being perceptible as continuations of the rows of the first node-link structure, with the indicated node'"'"'s row shifted to position the continued indicated node at the centering line of the second node-link structure.