US6300957B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Mapping a node-link structure to a rendering space beginning from any node
Assignee: SAP America Inc
•
Filing: 1998-07-29
•
Granted: 2001-10-09
•
Expires: 2018-07-29
Abstract
Abstract A node-link structure laid out in a space with negative curvature, such as the hyperbolic plane, is mapped to a rendering space, such as the unit disk, beginning from a starting element that has both a parent and a child. Data identifying the starting element are obtained, such as based on user signals. The starting element can be located at a starting position in the unit disk. Then a set of other elements can be mapped, each reachable from the starting element by a path that leads only through elements in the set. Each element's position in the negatively curved space relative to a preceding element on its path and the position of the preceding element in the rendering space can be used to obtain the element's position in the rendering space. The positions in the unit disk can then be used to present a representation of the node-link structure. The set of elements can include only a mapping root and descendants, where the mapping root is on an upward path from the starting element, but precedes the first element that maps to a position in the unit disk outside a precision horizon. A criterion can be applied to determine whether to map each element's descendants. If the rendering space has an active region within the precision horizon, it may not be necessary to map descendants if an element is outside the precision horizon or is outside the active region but has a parent inside the active region.
Inventors
- 👤 Ramana B. Rao
- 👤 John O. Lamping
- 👤 Tichomir G. Tenev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 21:13
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/26
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
195 words
A method of mapping a node-link structure laid out in a space with negative curvature into a rendering space; the method comprising: (A) obtaining data identifying a starting element within the structure, the starting element being identified from a plurality of possible starting elements in the structure; (B) locating the starting element at a starting position in the rendering space; and (C) for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; the act of mapping in (C) comprising, for each element in the set of other elements, using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 2
Independent Claim
195 words
A method of mapping a node-link structure laid out in a space with negative curvature into a rendering space; the method comprising: (A) obtaining data identifying a starting element within the structure, the starting element being identified from a plurality of possible starting elements in the structure; (B) locating the starting element at a starting position in the rendering space; and (C) for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; the act of mapping in (C) comprising, for each element in the set of other elements, using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 3
Dependent Claim
59 words
A method as in claim 1 , further comprising: (D) using the positions of elements in the rendering space from (B) and (C) to present a representation of the node link structure in a display region, positions in the rendering space corresponding to positions in the display region, the starting position corresponding to a focus of the display region.
Claim 4
Dependent Claim
22 words
A method as in claim 2 in which the display region is a circle, the starting position corresponding to the circle's center.
Claim 5
Dependent Claim
17 words
A method as in claim 1 in which the space with negative curvature is the hyperbolic plane.
Claim 6
Dependent Claim
63 words
A method as in claim 1 in which (A) comprises: presenting a representation of the node-link structure in a display region; receiving a signal from a user indicating a position in the display region; converting the position in the display region to a position in the rendering space; and using the position in the rendering space to obtain data identifying the starting element.
Claim 7
Dependent Claim
32 words
A method as in claim 1 in which (A) comprises: receiving a signal from a user that indicates the starting element; and using the signal to obtain data identifying the starting element.
Claim 8
Dependent Claim
15 words
A method as in claim 6 in which the signal also indicates the starting position.
Claim 9
Dependent Claim
38 words
A method as in claim 1 in which (A) comprises: receiving a signal from a user requesting a change in the node-link structure; and obtaining data identifying a starting element that is not affected by the requested change.
Claim 10
Dependent Claim
22 words
A method as in claim 8 in which (B) comprises locating the starting element at its previous position in the rendering space.
Claim 11
Dependent Claim
89 words
A method as in claim 1 in which the node-link structure is a tree with a root element and in which (B) comprises: walking up from the starting element to the root element to obtain identifiers of elements on a path from the starting element to the root element; and using the identifiers of elements on the path to walk down from the root element to the starting element, using a starting orientation of the root element to obtain an orientation of the starting element in the rendering space.
Claim 12
Dependent Claim
144 words
A method as in claim 1 in which the node-link structure is a directed graph, the rendering space has a bounded precision region within which elements can be mapped with adequate precision, the starting position is within the precision region, and (C) comprises: (C1) walking up from the starting element on an upward path, mapping each element on the upward path to a position in the rendering space until a first element is mapped to a position outside the bounded precision region; (C2) selecting a second element preceding the first element on the upward path as a mapping root, the second element being within the precision region; and (C3) walking downward from the mapping root and mapping the set of other elements to positions in the rendering space; the set of other elements including only the mapping root and descendants of the mapping root.
Claim 13
Dependent Claim
30 words
A method as in claim 11 in which the first and second elements are nodes, the second element being a node immediately preceding the first element on the upward path.
Claim 14
Dependent Claim
33 words
A method as in claim 11 in which (C3) comprises: for each element that is mapped in (C3), applying a criterion to determine whether it is necessary to map descendants of the element.
Claim 15
Dependent Claim
22 words
A method as in claim 13 in which applying the criterion includes determining whether the element has descendants in the node-link structure.
Claim 16
Dependent Claim
21 words
A method as in claim 13 in which applying the criterion includes determining whether the element is in the precision region.
Claim 17
Dependent Claim
51 words
A method as in claim 13 in which the rendering space has a bounded active region within the precision region, the starting position is within the active region, and applying the criterion includes determining whether the element is inside the active region or the element's parent is outside the active region.
Claim 18
Independent Claim
222 words
A system comprising: a processor for mapping a node-link structure laid out in a space with negative curvature into a rendering space; the processor; in mapping the node-link structure: obtaining data identifying a starting element within the structure, the starting element being identified from a plurality of possible starting elements in the structure; locating the starting element at a starting position in the rendering space; and for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path that leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; in mapping the position of each element in the set of other elements, the processor using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the negatively curved space and the position of the preceding element in the rendering space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 19
Independent Claim
222 words
A system comprising: a processor for mapping a node-link structure laid out in a space with negative curvature into a rendering space; the processor; in mapping the node-link structure: obtaining data identifying a starting element within the structure, the starting element being identified from a plurality of possible starting elements in the structure; locating the starting element at a starting position in the rendering space; and for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path that leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; in mapping the position of each element in the set of other elements, the processor using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the negatively curved space and the position of the preceding element in the rendering space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 20
Dependent Claim
269 words
An article of manufacture for use in a system that includes: a storage medium access device; and a processor connected for receiving data accessed on a storage medium by the storage medium access device; the article of manufacture comprising; a storage medium; and instruction data stored by the storage medium; the instruction data indicating instructions the processor can execute; the processor, in executing the instructions, mapping a node-link structure laid out in a space with negative curvature into a rendering space; the processor, in mapping the node-link structure: obtaining data identifying a starting element within the structure, the starting element being identified from a plurality of possible starting elements in the structure; locating the starting element at a starting position in the rendering space; and for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path that leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; in mapping the position of each element in the set of other elements, the processor using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 21
Dependent Claim
269 words
An article of manufacture for use in a system that includes: a storage medium access device; and a processor connected for receiving data accessed on a storage medium by the storage medium access device; the article of manufacture comprising; a storage medium; and instruction data stored by the storage medium; the instruction data indicating instructions the processor can execute; the processor, in executing the instructions, mapping a node-link structure laid out in a space with negative curvature into a rendering space; the processor, in mapping the node-link structure: obtaining data identifying a starting element within the structure, the starting element being identified from a plurality of possible starting elements in the structure; locating the starting element at a starting position in the rendering space; and for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path that leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; in mapping the position of each element in the set of other elements, the processor using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 22
Independent Claim
278 words
A method of transferring data between first and second machines over a network, the second machine including memory and a processor connected for accessing the memory; the memory being for storing instruction data; the method comprising: establishing a connection between the first and second machines over the network; and operating the first and second machines to transfer instruction data from the first machine to the memory of the second machine; the instruction data indicating instructions the processor can execute; the processor, in executing the instructions, mapping a node-link structure laid out in a space with negative curvature into a rendering space; the processor, in mapping the node-link structure: obtaining data identifying a starting element within the structure the starting element being identified from a plurality of possible starting elements in the structure; locating the starting element at a starting position in the rendering space; and for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path that leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; in mapping the position of each element in the set of other elements, the processor using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
Claim 23
Independent Claim
278 words
A method of transferring data between first and second machines over a network, the second machine including memory and a processor connected for accessing the memory; the memory being for storing instruction data; the method comprising: establishing a connection between the first and second machines over the network; and operating the first and second machines to transfer instruction data from the first machine to the memory of the second machine; the instruction data indicating instructions the processor can execute; the processor, in executing the instructions, mapping a node-link structure laid out in a space with negative curvature into a rendering space; the processor, in mapping the node-link structure: obtaining data identifying a starting element within the structure the starting element being identified from a plurality of possible starting elements in the structure; locating the starting element at a starting position in the rendering space; and for each of a set of other elements in the structure, mapping the element's position in the negatively curved space to a position in the rendering space; the set of other elements including at least a parent and a child of the starting element; each element in the set of other elements being reachable from the starting element by a path that leads only through elements in the set; each element's path including a preceding element that immediately precedes the element in the path; in mapping the position of each element in the set of other elements, the processor using the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-10-08 | 2005-04-09 | 2005-10-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-10-08 | 2009-04-09 | 2009-10-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-10-08 | 2013-04-09 | 2013-10-09 | $7700.00 | Window Closed / Lapsed |